본문 바로가기

Algorithm(BOJ, Python)100

[백준_9657] 돌게임 3 python 나만 이문제 어려웠나 dp[5]를 상근이가 지는줄 알았다가 간단히 수학으로 해결가능한줄 알았다.. ㅋㅋ 이런날도있는거겠지,, # n 입력 n = int(input()) # dp 설계 dp = [ 0 for _ in range(1001) ] # dp 초기설정 (상근이가 이기는 경우를 1로 설정) dp[1] = 1 dp[3] = 1 dp[4] = 1 # dp 채워넣기 for i in range(5, n+1): if dp[i-1] == 0 or dp[i-3] == 0 or dp[i-4] == 0: dp[i] = 1 # 출력 if dp[n]: print('SK') else: print('CY') 2022. 7. 20.
[백준_1699] 제곱수의 합 python dp[12],, 그를조심해,, # 입력 속도 개선 import sys input = sys.stdin.readline # n 입력 n = int(input()) # dp 설계 dp = [ 0 for _ in range(n+1) ] # 제곲값들 넣어줄 리스트 만들기 s = [i**2 for i in range(1, 317)] # dp 채워넣기 for i in range(1, n+1): # 최솟값 담아줄 리스트 min_list = [] # 1 ~ i 사이까지의 j 값 중 for j in s: # 뺄 제곱수가 i보다 크다면 if j > i: break # 뺄 제곱수가 i보다 작다면 # 최솟값 후보리스트에 올리기 min_list.append(dp[i-j]) # dp에 추가해줄 값 선정 후 + 1 dp[i] = .. 2022. 7. 19.
[백준_14494] 다이나믹이 뭐예요? python 너무 쉬운 문제를 고른 것 같다. 초등학교 길찾기 문제에서 대각선 경로가 하나 추가된 수준 # n, m 입력 n, m = map(int, input().split()) # dp 설계 dp = [ [0] * m for _ in range(n) ] # 초기설정 for i in range(n): dp[i][0] = 1 for i in range(m): dp[0][i] = 1 # dp 채워넣기 for i in range(1, n): for j in range(1, m): dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1]) % 1000000007 # 출력 print(dp[-1][-1] % 1000000007) 이런거 나머지 처리 안해주면 컴퓨터 날라갈수 있으니 조심 ^^ 2022. 7. 19.
[백준_15989] 1,2,3더하기 4 python 이런류의 문제를 여럿 풀어보았지만, 이건 아무리 봐도 규칙을 찾기가 어려웠다. 특히 dp를 풀때는 내가 지금 찾는 dp의 값이, 어디서 오는지를 찾아야하는데, 감이 잡히지 않았다. 결국 구글링을 통해 힌트를 얻었다. 앞으로 이런 문제를 만났을 때는, 어거지로 규칙을 찾아낼 수 있도록 해야할 것 같다. # dp 설계 dp = [ 0 for _ in range(10001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 dp[3] = 3 # dp 채워넣기 for i in range(4, 10001): dp[i] = dp[i-1] + (dp[i-2] - dp[i-3]) # 보너스점수 if i % 3 == 0: dp[i] += 1 # t 입력 t = int(input()) for _ in range(t.. 2022. 7. 18.
[백준_16194] 카드 구매하기2 python 최솟값들의 후보자들을 조사하는 과정을 구현하는 것이 i-j라고 생각하는데 왜 이렇게 많은 시간을 들였을까 자만하지말자,,, # n 입력 n = int(input()) # p 설계 p = [0] # p 입력 p.extend(list(map(int, input().split()))) # dp 설계 dp = [ 0 for _ in range(n + 1) ] # dp 초기설정 dp[1] = p[1] # dp 채워넣기 for i in range(2, n + 1): # 최솟값 설정 m = 10001 # 최솟값의 후보자들을 조사하면서, for j in range(1, i + 1): # 최솟값을 찾으면, if dp[i-j] + p[j] < m: # 최솟값 갱신 m = dp[i-j] + p[j] # dp 값 추가 dp[.. 2022. 7. 17.
[백준_9655] 돌게임 python 베스킨라빈스31,, 술게임 열심히 했더니 이런 도움이 ㅋㅋ # n 입력 n = int(input()) # 출력 if n % 2 == 0: print('CY') else: print('SK') 2022. 7. 16.
[백준_1965] 상자넣기 python 처음에 헷갈려서 한번 틀렸던 부분이 증가하는 상황에서 전 dp에 단순히 1을 더해주면 끝이아닌가,,? 하면서 더 빠른 코드를 작성할 수 있겠다는 기대감에 부풀었었다. 또한 백준이 제공한 테스트코드도, 위와같은 상황에 적절하게 빠지기 쉬운 테스트 코드를 제공했다 사악하다. 그러나 이전까지의 모든 케이스 중에서 현재보다 작은 상자의 디피 최댓값 + 1을 해줘야 한다. 시간복잡도 측면에서 n = 1000인데, 1초라는것은 n^2의 시간복잡도는 허용한다는 뜻이다. # 입력 속도 개선 import sys input = sys.stdin.readline # n 입력 n = int(input()) # box_list 입력 box_list = list(map(int, input().split())) # dp 설계 dp.. 2022. 7. 15.
[백준_11048] 이동하기 python 대각선, 위, 아래를 모두 생각해 줄 필요는 없다. 모든 사탕은 양수이기 때문이다. 초기 설정만 잘 해주면 쉽게 해결할 수 있다. 근데 이거 그리디 아닌가,,? # n, m 입력 n, m = map(int, input().split()) # grid 설계 grid = [ list(map(int, input().split())) for _ in range(n) ] # dp 설계 dp = [ [0] * m for _ in range(n) ] # 초기 설정 dp[0][0] = grid[0][0] # 가로 줄 초기설정 for i in range(1, m): dp[0][i] = dp[0][i-1] + grid[0][i] # 세로 줄 초기설정 for i in range(1, n): dp[i][0] = dp[i-1].. 2022. 7. 14.
[백준_1904] 01타일 python 이런 문제를 마주할 때마다 귀납적으로 이런 규칙이 있구나하고 발견은 하겠으나 연역적으로 왜 이런 규칙이 나오는지는 잘 모르겠다. 처음에 나눈 값으로 저장 안했다가 맥북 메모리 박살날뻔했다. # dp 설계 dp = [ 0 for _ in range(1000001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 # dp 채워넣기 for i in range(3, 1000001): dp[i] = (dp[i-2] + dp[i-1]) % 15746 # n 입력 n = int(input()) # 출력 print(dp[n] % 15746) 2022. 7. 13.
[백준_11051] 이항 계수 2 python dp로 해결하지 말자 이런건 고등학교때 확률과 통계 열심히 배워놓자 다 도움이 된다. # math 라이브러리 사용 import math # n, k 입력 n, k = map(int, input().split()) # 출력 print((math.factorial(n) // (math.factorial(k) * math.factorial(n-k))) % 10007) 2022. 7. 12.
[백준_1010] 다리놓기 python dp로 풀어도 되는 문제지만, 조합이라는 수학적 지식이 조금만 있다면 훨씬 편하게 풀 수 있는 문제였다. # math 라이브러리 사용 import math # t 입력 t = int(input()) for _ in range(t): # n, m 입력 n, m = map(int, input().split()) # output = 조합의 수 output = math.factorial(m) // (math.factorial(n) * math.factorial(m-n)) # 출력 print(output) 2022. 7. 12.
[백준_15988] 1, 2, 3 더하기 3 python 처음 문제를 풀었을 때 메모리 초과에 걸렸다. 왜일까 고민하다가 '방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.'에서 힌트를 얻었다. 디피를 채울 때 나머지만 넣어 줘도 상관이 없지 않을까 하는 생각을 했다. # dp 설계 dp = [ 0 for _ in range(1000001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 dp[3] = 4 # dp 채워넣기 for i in range(4, 1000001): dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009 # t 입력 t = int(input()) # n 입력 for _ in range(t): n = int(input()) print(dp[n] % 1000000009) 2022. 7. 11.
[백준_15486] 퇴사2 python 퇴사1과 뭐가 다른건지 잘 모르겠다. 수학책 풀고 수학익임책 푼 듯한 느낌,,? # n 입력 n = int(input()) # T, P 설정 T, P = [], [] # t, p 입력 for _ in range(n): t, p = map(int, input().split()) T.append(t) P.append(p) # dp 설정 dp = [ 0 for _ in range(n+1) ] # dp 초기설정 dp[n] = 0 # dp 채우기 for i in range(n-1, -1, -1): if i + T[i] > n: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1], dp[i+T[i]] + P[i]) # 출력 print(dp[0]) 2022. 7. 10.
[백준_11722] 가장 긴 감소하는 부분 수열 python 컴퓨터는 1초에 1억번까지의 연산이 가능하다고 생각하면 된다. 이는 시간복잡도를 계산할 때 유용하게 사용하는 꿀팁이다. 이 문제의 경우 n이 1000개까지 입력되므로, n 제곱까지의 시간복잡도는 허용된다고 생각하면 된다. # n 입력 n = int(input()) # a 입력 a = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(n) ] # dp 초기설정 dp[0] = 1 # 점화식 활용, dp 채워넣기 for i in range(1, n): # 최댓값 설정 M = 0 # i-1 까지 탐색하면서 for j in range(i): # a[i] 보다 크고, 현재 최댓값보다 dp값이 크다면, if a[j] > a[i] and dp[j] > M.. 2022. 7. 9.
[백준_1620] 나는야 포켓몬 마스터 이다솜 python 딕서녀리를 이용하면 매우 쉽게 풀리는 문제이다. 근데 좀 걸렸다. 어이가 없는게 입력 복사하고 돌리면 자꾸 라이츄와 마주칠 것이다. 입력시 나타나는 오류인데, 줄바꿈 문제인 것 같다. 모두들 나처럼 피해입지말길,, 라이츄가 정답이다,ㅡ, # n, m 입력 n, m = map(int, input().split()) # 도감 p_book = {} # 도감 채워넣기 for i in range(1, n+1): name = input() p_book[name] = i p_book[i] = name # 출력 for _ in range(m): order = input() if order.isdigit(): print(p_book[int(order)]) else: print(p_book[order]) 2022. 7. 8.
[백준_11047] 동전 0 python 그리 어렵지 않게 해결할 수 있는 그리디 알고리즘이였다. # 입력 속도 개선 import sys input = sys.stdin.readline # n, k 입력 n, k = map(int, input().split()) # coin_list 설계 coin_list = [] # coin_list 채우기 for _ in range(n): coin_list.append(int(input())) # def find_max(k) def find_max(k): # 최댓값 초기설정 M = 0 # 코인리스트를 돌며 for coin in coin_list: # 코인이 현재 k값보다 작거나 같으면 if coin 2022. 7. 8.
[백준_14501] 퇴사 python dp를 거꾸로 뒤집어서 생각할 수도 있어야 한다는 교훈을 얻게 해 준 문제였다. 처음에 갈피를 잘못 잡아 애를 먹다가 구글링을 통해 아이디어를 얻었다. 역시 아직 멀었다. # n 입력 n = int(input()) # t, p 설계 t = [] p = [] # a, b 입력 for _ in range(n): a, b = map(int, input().split()) t.append(a) p.append(b) # dp 설계 dp = [ 0 for _ in range(n+1) ] # dp 채워넣기 for i in range(n-1, -1, -1): if t[i] + i > n: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1], p[i] + dp[i + t[i]]) # 출력 prin.. 2022. 7. 8.
[백준_2193] 이친수 python dp문제를 풀다보면, 마치 고딩때 모의고사에서 규칙 찾듯 쭉 나열하다보면 설마,,? 싶은것들이 나타나는 경우가 있다. 피보나치는 그 중 가장 흔한 케이스이다. 물론 매우 위험한 풀이이다. # dp 설계 dp = [ 0 for _ in range(91) ] # 초기설정 dp[1] = 1 # dp 채워넣기 for i in range(2, 91): dp[i] = dp[i-2] + dp[i-1] # n 입력 n = int(input()) # 출력 print(dp[n]) 2022. 7. 7.

티스토리툴바