본문 바로가기

Algorithm(BOJ, Python)100

[백준_14607] 피자(Large) python 처음에 dp로 해결하려 하였으나, 그대로 냈더니 메모리초과에 걸려버렸다. 고민하다 구글링 한 결과, 숫자들을 천천히 보면 수학적으로도 바로 해결 가능함을 알 게 되었다. # n 입력 n = int(input()) # 출력 print(n * (n-1) // 2) 2022. 8. 8.
[백준_1788] 피보나치 수의 확장 python 설계를 짜고 보니 f와 g가 짝수 홀수 기준으로 대칭을 이루고 있다는 사실을 발견했다. # f 설계 f = [ 0 for _ in range(1000001) ] # f 초기설정 f[0] = 0 f[1] = 1 # f 채워넣기 for i in range(2, 1000001): f[i] = (f[i-2] + f[i-1]) % 1000000000 # n 입력 n = int(input()) # n == 0 일 경우 if n == 0: print(0) print(0) # n > 0 일 경우 elif n > 0: print(1) print(f[n]) # n < 0 일 경우 else: # n이 짝수이면, if n % 2 == 0: # 음수 print(-1) # 값 출력 print(f[n * -1]) # n이 홀수이면.. 2022. 8. 7.
[백준_14495] 피보나치 비스무리한 수열 python 코테 캠프가 빡센 관계로,, 오늘은 날먹,, # fib 설정 fib = [ 0 for _ in range(117) ] # fib 초기 설정 fib[1] = 1 fib[2] = 1 fib[3] = 1 # fib 채워넣기 for i in range(4, 117): fib[i] = fib[i-3] + fib[i-1] # n 입력 n = int(input()) # 출력 print(fib[n]) 2022. 8. 6.
[백준_15624] 피보나치 수 7 python n == 0일 경우를 따로 처리해 주지 않으면, dp길이가 맞이 않아 런타임 에러에 빠진다. # n 입력 n = int(input()) # n = 0 일 경우 if n == 0: print(0) # n >= 1 일 경우 else: # dp 설계 dp = [ 0 for _ in range(n + 1) ] # dp 초기설정 dp[0] = 0 dp[1] = 1 # dp 채워넣기 for i in range(2, n+1): dp[i] = (dp[i-2] + dp[i-1]) % 1000000007 # 출력 print(dp[n]) 2022. 8. 5.
[백준_1063] 킹 python 돌이 있는 경우를 or이 아닌 and로 조건처리했다가 계속 틀렸었다. 조심,, # k, s, n 입력 k, s, n = input().split() n = int(n) # mapping mapping = { 'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6, 'G': 7, 'H': 8, } # mapping 이용하여 좌표 반환 kx = mapping[k[0]] ky = int(k[1]) sx = mapping[s[0]] sy = int(s[1]) # R L B T RT LT RB LB dx = [1, -1, 0, 0, 1, -1, 1, -1] dy = [0, 0, -1, 1, 1, 1, -1, -1] # def in_range(x, y): def in_range(x, y.. 2022. 8. 4.
[백준_8911] 거북이 python dx, dy테크닉을 이용하여 문제를 해결해 보았다. # 북 동 남 서 순으로 dx, dy 설정 dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # t 입력 t = int(input()) for _ in range(t): # 북쪽 바라보고 시작 dir_num = 0 # x, y 초기설정 x, y = 0, 0 # 최소 최댓값 설정 min_x, max_x, min_y, max_y = 0, 0, 0, 0 # order 입력 orders = input() for order in orders: # 전진 if order == 'F': x, y = x + dx[dir_num], y + dy[dir_num] # 후진 elif order == 'B': x, y = x + dx[(dir_num + 2) .. 2022. 8. 3.
[백준_15991] 1,2,3 더하기 6 python 규칙 찾는데 진짜 시간 오래걸린다 이런문제는 개인적으로 이런류는 그냥 무지성 냅다 n = 10 까지 지르고 그리고 어거지로 규칙 찾는게 답인 듯 하다. # dp 설계 dp = [ 0 for _ in range(100001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 dp[3] = 2 dp[4] = 3 dp[5] = 3 dp[6] = 6 # dp 채워넣기 for i in range(7, 100001): dp[i] = (dp[i-2] + dp[i-4] + dp[i-6]) % 1000000009 # t 입력 t = int(input()) for _ in range(t): # n 입력 n = int(input()) # 출력 print(dp[n] % 1000000009) 2022. 8. 1.
[백준_13239] Combinations python 사실 30분간 풀었던 dp문제가 틀려서 짜증나서 급선회했다. 마찬가지로 nCk 즉 조합을 고등학교 수학시간에 배웠다면 쉽게 해결할 수 있는 문제였다. # math 라이브러리 사용 import math # t 입력 t = int(input()) for _ in range(t): # n, k 입력 n, k = map(int, input().split()) # 출력 print((math.factorial(n) // (math.factorial(k) * math.factorial(n-k))) % 1000000007) 2022. 7. 31.
[백준_4883] 삼각 그래프 python dp자체보다 입력 형식, 그리고 무엇보다 비용이 음수일수도 있다는 점을 주의해야 하는 문제였다. 따라서 각 dp 칸에 오는 모든 경우의 수를 고려하여 점화식을 세워야 한다. # k 설정 k = 0 while True: # n 입력 n = int(input()) # 만약 n이 0이라면, if n == 0: # 테스트 종료 break # n이 0이 아니라면, 진행 else: # 테스트 번호 부여 k += 1 # grid 설계 grid = [ list(map(int, input().split())) for _ in range(n) ] # dp 설계 dp = [ [0] * 3 for _ in range(n) ] # dp 초기설정 dp[0][1] = grid[0][1] dp[0][2] = dp[0][1] + gr.. 2022. 7. 30.
[백준_9711] 피보나치 python 미안 오늘까지만 좀 쉬자 그래도 문자열 포매팅 하나는 복습하고 갈 수 있는 문제잖아? # fib 설계 fib = [ 0 for _ in range(10001) ] # fib 초기설정 fib[1] = 1 fib[2] = 1 # fib 채워넣기 for i in range(3, 10001): fib[i] = fib[i-2] + fib[i-1] # t 입력 t = int(input()) # 출력 for i in range(1, t+1): p, q = map(int, input().split()) print('Case #%d: %d'%(i, fib[p] % q)) 2022. 7. 29.
[백준_1793] 타일링 python 문제는 쉽다. 근데 처음 보는 입력 형식에서 당황했다. 그리고 n=0일때 0가지 아닌가,,,? 1가지로 풀어야 한단다,, 그리고 try except 안써주면 런타임 에러 뜬다. # dp 설계 dp = [ 0 for _ in range(251) ] # dp 초기설정 dp[0] = 1 dp[1] = 1 dp[2] = 3 # dp 채워넣기 for i in range(3, 251): dp[i] = dp[i-2] * 2 + dp[i-1] while True: try: # n 입력 n = int(input()) # 출력 print(dp[n]) except: break 2022. 7. 28.
[백준_8394] 악수 python 천천히 세어보면 어렵지 않게 피보나치 라는 것을 알 수 있다. # dp 설계 dp = [ 0 for _ in range(10000001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 # dp 채워넣기 for i in range(3, 10000001): dp[i] = ((dp[i-2] % 10) + (dp[i-1] % 10))% 10 # n 입력 n = int(input()) # 출력 print(dp[n]) 2022. 7. 27.
[백준_17175] 피보나치는 지겨웡~ python 시간이 없어서 급하게 풀다가 자기 자신의 호출 횟수 1을 더해줘야 한다는 것을 까먹었다. f(i) = f(i-2) + f(i-1) + 1이다 # fib 설계 fib = [ 0 for _ in range(51) ] # fib 초기설정 fib[0] = 1 fib[1] = 1 fib[2] = 3 fib[3] = 5 # fib 채워넣기 for i in range(4, 51): fib[i] = fib[i-2] + fib[i-1] + 1 # n 입력 n = int(input()) # 출력 print(fib[n] % 1000000007) 2022. 7. 26.
[백준_9507] Generation of Tribbles python 거 너무 문제 꽁으로 먹는거 아니오 라고 나도 생각하지만, 이번주는 좀 봐줘라,, 못해먹겠다 기본적인 dp의 메모이제이션 개념만 알고 있다면 쉽게 해결할 수 있다. # koong 설계 koong = [ 0 for i in range(68) ] # koong 초기설정 koong[0] = 1 koong[1] = 1 koong[2] = 2 koong[3] = 4 # koong 채워넣기 for i in range(4, 68): koong[i] = koong[i-1] + koong[i-2] + koong[i-3] + koong[i-4] # t 입력 t = int(input()) for _ in range(t): # n 입력 n = int(input()) # 출력 print(koong[n]) 2022. 7. 25.
[백준_9658] 돌게임 4 python 처음에 or 개념으로 조건을 생각했다가, 다 상근이가 이겨버리는 말도안되는 결과가 도출되었다. 돌게임 시리즈 생각보다 어렵다. # n 입력 n = int(input()) # dp 입력 dp = [ 0 for _ in range(1001) ] # dp 초기설정 dp[1] = 0 dp[2] = 1 dp[3] = 0 dp[4] = 1 # dp 채워넣기 for i in range(5, 1001): if dp[i-1] and dp[i-3] and dp[i-4]: dp[i] = 0 else: dp[i] = 1 # 출력 if dp[n]: print('SK') else: print('CY') 2022. 7. 24.
[백준_17216] 가장 큰 감소하는 부분수열 python 이런 류의 문제에 이젠 익숙해진 기분이다. 마찬가지로 n의 범위가 1000이하이니 n^2까지의 시간복잡도는 인정해준다. # n 입력 n = int(input()) # a 입력 a = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(n) ] # dp 초기설정 dp[0] = a[0] # dp 채워넣기 for i in range(1, n): # 최댓값 설정 M = 0 # 이전까지 돌면서 for j in range(i): # 감소하는 수열 중 dp값이 가장 큰 것을 찾아 if a[j] > a[i] and dp[j] > M: # 최댓값 갱신 M = dp[j] # dp 넣어주기 dp[i] = M + a[i] # 출력 print(max(dp)) 2022. 7. 23.
[백준_2491] 수열 python 어제 과음한 관계로 오늘은 쉬운문제를,, # n 입력 n = int(input()) # n_list 입력 n_list = list(map(int, input().split())) # dp1 (연속해서 같거나 커지는 최댓값 구하기 위한 dp) dp1 = [ 0 for _ in range(n) ] # dp1 초기설정 dp1[0] = 1 # dp1 채워넣기 for i in range(1, n): # n_list[i] 가 n_list[i-1]보다 크거나 같으면, if n_list[i] >= n_list[i-1]: # 전 dp + 1 dp1[i] = dp1[i-1] + 1 # 작으면 else: # 1로 초기화 dp1[i] = 1 # dp2 (연속해서 같거나 작아지는 최댓값 구하기 위한 dp) dp2 = [ 0 f.. 2022. 7. 22.
[백준_11660] 구간 합 구하기 5 python grid 굳이 저렇게 받지 않아도 된다. 입력 어케해야 저렇게 앞에 0을 넣을 수 있을까 고민해봤는데 굳이 그럴 필요가 없었다. dp만 그렇게 만들어주면 된다. # 입력 속도 개선 import sys input = sys.stdin.readline # n, m 입력 n, m = map(int, input().split()) # grid grid = [ list(map(int, input().split())) for _ in range(n) ] # dp 설계 dp = [ [0] * (n+1) for _ in range(n+1) ] # dp채워넣기 for i in range(1, n+1): for j in range(1, n+1): dp[i][j] = dp[i][j-1] + grid[i-1][j-1] # x.. 2022. 7. 21.

티스토리툴바