코딩기록

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net n = int(input()) prime = [0, 0] + [1] * 9999 # 소수 리스트 # 에라토스테네스의 체를 이용하여 소수 구하기 for i in range(2, int(10000 ** 0.5)+1): if prime[i]: for j in range(i*2, 10001, i): prime[j] = 0 # 두 소수의 차이가 가장 작은 골드바흐 파티션 구하기 for ..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제에 점화식이 다 나와있어서 점화식을 따로 구할 필요는 없었다. 동적계획법 문제이기 때문에 재귀함수의 결과만 리스트에 저장해두면 됐었다! dp = [[[0] * 21 for _ in range(21)] for _ in range(21)] def w(a, b, c): if a 20: return w(20, 20, 20) if dp[a][b][c] != 0: return dp[a][b][c] if a ..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net import math while True: n = int(input()) if n == 0: break prime = [0, 0] + ([1] * (2*n-1)) # 소수 여부 저장 리스트, 0 - 소수X / 1 - 소수O # 소수 찾기 - 에라토스테네스의 체 for i in range(2, int(math.sqrt(2*n+1))+1): if prime[i]: for j in range(i..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 동적계획법 문제였다. 동적 계획법 문제는 "규칙성"을 찾는 것이 중요하다. "규칙성"이 문제를 해결하는 핵심이 된다. 이 문제에서는 규칙성에 대해 친절히 설명해주어서 규칙성을 찾을 필요는 없었다. 피보나치의 규칙성은 f(n) = f(n-1) + f(n-2) 이다. N = int(input()) zero = [1, 0, 1] # 0의 개수 리스트 one = [0, 1, 1] # 1의 개수 리스트 for _ in range(N): n = int(input()) # n번째를 의미하는 변수..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net import sys sudoku = [list(map(int, sys.stdin.readline().split())) for _ in range(9)] # 스도쿠 숫자 리스트 zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0] # 해결해야 할 칸 리스트 flag = False # 답이 출력되었는지 확인하는 변수 # 가..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 백트래킹 문제로 DFS를 사용하여 해결할 수 있었다. 근데 시간초과 문제 때문에 어려웠던 문제였다. 시간 초과를 해결하기 위해서는 1. 퀸을 배치할 수 있는지 확인할 때 break 를 사용하여 시간이 덜 걸리게 한다 2. pypy3 를 사용한다 (python3는 시간초과가 난다) def queen(n, N) : global result if n == N: # 더 이상 탐색할 수 없는 경우 재귀함수를 빠..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net import sys n = int(sys.stdin.readline()) # 사람 수 graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] # 능력치 리스트 visited = [False] * n # 방문 여부 리스트 answer = 1e9 # 능력치 차이의 최소값 # DFS 수행 def dfs(depth, now): global answer..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net n = int(input()) # 수의 개수 nums = list(map(int, input().split())) # 숫자 리스트 op = list(map(int, input().split())) # 연산자 리스트 r_max, r_min = -1e9, 1e9 # 식의 최대값, 최소값 # DFS 수행 def dfs(depth, result, p..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net [처음 코드] n = int(input()) nums = list(map(int, input().split())) comp = sorted(list(set(nums))) for num in nums: print(comp.index(num), end = ' ') 처음엔 index() 를 사용해서 리스트에서의 인덱스를 찾아 출력하도록 하였다. 그랬더니..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 단어 길이 기준으로 정렬하는 조건을 넣어 정렬하면 길이 순으로 정렬되고 같은 길이 안에서는 사전 순으로 정렬된다고 생각했다. 별다른 조건없이 정렬했을 때 사전 순으로 정렬되니까! 근데 결과를 출력해보니 같은 길이 안에서 사전 순으로 정렬되지 않았다... ㅜ import sys n = int(sys.stdin.readline()) words = [] for _ in range(n): wo..