백준 - 17070 : 파이프 옮기기 1 (G5)

🧠 Algorithm

1N = int(input()) 2 3L = [list(map(int, input().split())) for _ in range(N)] 4result = 0 5 6def dfs(x, y, direc): 7 global result 8 if x == N-1 and y == N-1: 9 result += 1 10 return 11 12 if x+1 < N and y+1 < N and L[y+1][x] == 0 and L[y][x+1] == 0 and L[y+1][x+1] == 0: 13 dfs(x+1, y+1, 2) 14 15 if (direc == 0 or direc == 2) and x+1 < N and L[y][x+1] == 0: 16 dfs(x+1, y, 0) 17 18 if (direc == 1 or direc == 2) and y+1 < N and L[y+1][x] == 0: 19 dfs(x, y+1, 1) 20 21dfs(1, 0, 0) 22print(result) 별거 아닌게.

백준 - 1965 : 상자넣기 (S2)

🧠 Algorithm

1N = int(input()) 2L = list(map(int, input().split())) 3dp = [0]*N 4 5for i in range(1, N): 6 for j in range(i): 7 if L[j]<L[i] and dp[i]<dp[j]+1: 8 dp[i] = dp[j]+1 9print(max(dp)+1) LIS를 구하는 문제이다

백준 - 16194 : 카드 구매하기 2 (S1)

🧠 Algorithm

1N = int(input()) 2P = list(map(int, input().split())) 3dp = [10000000]*(N) 4 5for i in range(N): 6 for j in range(i): 7 dp[i] = min(dp[i], dp[j]+P[i-j-1]) 8 dp[i] = min(dp[i], P[i]) 9 10print (dp[N-1])

백준 - 1495 : 기타리스트 (S1)

🧠 Algorithm

1N, S, M = map(int, input().split()) 2P = list(map(int, input().split())) 3dp = [[False]*(M+1) for _ in range(N+1)] 4 5dp[0][S] = True 6 7for i in range(1, N+1): 8 for j in range(M+1): 9 if dp[i-1][j]: 10 if 0 <= j-P[i-1] <= M: 11 dp[i][j-P[i-1]] = True 12 if 0 <= j+P[i-1] <= M: 13 dp[i][j+P[i-1]] = True 14result = -1 15for i in range(M+1): 16 if dp[N][i]: 17 result = i 18print (result) 인터넷에서 접근을 참고했다

백준 - 2011 : 암호코드 (G5)

🧠 Algorithm

1L = list(input()) 2N = len(L) 3MOD = 10**6 4 5def solution(): 6 if L[0] == '0': 7 return 0 8 9 dp = [1, 1]+[0]*(N-1) 10 11 for i in range(2, N+1): 12 if L[i-1] != '0': 13 dp[i] = (dp[i]+dp[i-1]) % MOD 14 if 10 <= int(L[i-2]+L[i-1]) <= 26: 15 dp[i] = (dp[i]+dp[i-2]) % MOD 16 17 return dp[N] 18 19 20print (solution()) 인터넷을 참고하여 풀었다

백준 - 10164 : 격자상의 경로 (S1)

🧠 Algorithm

1N, M, K = map(int, input().split()) 2K -= 1 3ox = K % M 4oy = K // M 5def solve(sx, sy, ex, ey): 6 dp = [[0]*M for _ in range(N)] 7 dp[sy][sx] = 1 8 for i in range(sy, ey+1): 9 for j in range(sx, ex+1): 10 if i-1 >= 0: 11 dp[i][j] += dp[i-1][j] 12 if j-1 >= 0: 13 dp[i][j] += dp[i][j-1] 14 return dp[ey][ex] 15 16if K !

백준 - 5557 : 1학년 (G5)

🧠 Algorithm

1N = int(input()) 2L = list(map(int, input().split())) 3dp = [[0]*21 for _ in range(N-1)] 4 5dp[0][L[0]] = 1 6 7for i in range(0, N-2): 8 for j in range(21): 9 if dp[i][j] != 0: 10 k = L[i+1] 11 if k != 0: 12 if 0 <= j+k <= 20: 13 dp[i+1][j+k] += dp[i][j] 14 if 0 <= j-k <= 20: 15 dp[i+1][j-k] += dp[i][j] 16 else: 17 dp[i+1][j] = dp[i][j]*2 18print (dp[N-2][L[-1]]) 혼자 힘으로 풀었다!

백준 - 5582 : 공통 부분 문자열 (G5)

🧠 Algorithm

1S1 = list(input()) 2S2 = list(input()) 3L1 = len(S1)+1 4L2 = len(S2)+1 5 6dp = [[0]*L1 for _ in range(L2)] 7result = 0 8 9for i in range(1, L2): 10 for j in range(1, L1): 11 if S1[j-1] == S2[i-1]: 12 dp[i][j] = dp[i-1][j-1]+1 13 result = max(result, dp[i][j]) 14 15print (result) 혼자 힘으로 해결! 깔끔한 풀이가 나와 기분이 좋다

백준 - 10942 : 팰린드롬? (G4)

🧠 Algorithm

1import sys 2input = sys.stdin.readline 3 4N = int(input()) 5L = list(map(int, input().split())) 6 7dp = [[0]*N for _ in range(N)] 8 9for i in range(N): 10 dp[i][i] = 1 11 if i < N-1 and L[i] == L[i+1]: 12 dp[i][i+1] = 1 13 14for i in range(N, -1, -1): 15 for j in range(i+1, N): 16 if dp[i+1][j-1] and L[i] == L[j]: 17 dp[i][j] = 1 18 19for i in range(int(input())): 20 S, E = map(int, input().

백준 - 9252 : LCS 2 (G4)

🧠 Algorithm

1S1 = list(input()) 2S2 = list(input()) 3 4N1 = len(S1)+1 5N2 = len(S2)+1 6 7dp = [[0]*(N1) for _ in range(N2)] 8 9for i in range(1, N2): 10 for j in range(1, N1): 11 if S2[i-1] == S1[j-1]: 12 dp[i][j] = dp[i-1][j-1] + 1 13 else: 14 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 15i = N2-1 16j = N1-1 17print (dp[i][j]) 18if dp[i][j] == 0: 19 exit() 20 21result = '' 22while True: 23 if i==0 or j==0: 24 break 25 26 if dp[i][j] == dp[i-1][j]: 27 i -= 1 28 elif dp[i][j] == dp[i][j-1]: 29 j -= 1 30 else: 31 result = S1[j-1] + result 32 i -= 1 33 j -= 1 34 35print (result) 점화식을 잘못 세웠었다 문자가 같은 경우에 max(dp[i-1][j], dp[i][j-1])+1이 아닌 dp[i-1][j-1]+1이다.

백준 - 1918 : 후위 표기식 (G2)

🧠 Algorithm

1string = list(input()) 2 3priority = {'(':0, ')':0, '+':1, '-':1, '*':2, '/':2} 4operator = [] 5result = '' 6 7for c in string: 8 if c.isalpha(): 9 result += c 10 elif c == '(': 11 operator.append(c) 12 elif c == ')': 13 while operator: 14 op = operator.pop() 15 if op == '(': 16 break 17 result += op 18 else: 19 if operator: 20 if priority[operator[-1]] < priority[c]: 21 operator.

백준 - 1915 : 가장 큰 정사각형 (G4)

🧠 Algorithm

1N, M = map(int, input().split()) 2 3L = [list(map(int, input())) for _ in range(N)] 4 5dp = [[0]*(M+1) for _ in range(N+1)] 6 7result = 0 8 9for i in range(1, N+1): 10 for j in range(1, M+1): 11 dp[i][j] = L[i-1][j-1] 12 13 if L[i-1][j-1]: 14 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1 15 result = max(result, dp[i][j]) 16 17for i in dp: 18 print (i) 19print (result**2) 조금 시간이 걸렸지만 혼자 힘으로 풀었다 점화식은 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1이다.

백준 - 2631 : 줄세우기 (G4)

🧠 Algorithm

1N = int(input()) 2L = [] 3for i in range(N): 4 L.append(int(input())) 5 6dp = [1]*N 7 8for i in range(N): 9 for j in range(i): 10 if L[j] < L[i]: 11 dp[i] = max(dp[i], dp[j]+1) 12 13print (N-max(dp)) LIS를 활용한 문제이다 풀이 유도는 잘했으나 LIS가 헷갈려서 전에 풀었던 코드를 참고하였다

백준 - 15486 : 퇴사 2 (G5)

🧠 Algorithm

1import sys 2input = sys.stdin.readline 3N = int(input()) 4T = [] 5P = [] 6dp = [0]*(N+1) 7 8for _ in range(N): 9 a, b = map(int, input().split()) 10 T.append(a) 11 P.append(b) 12 13for i in range(N-1, -1, -1): 14 if i+T[i] > N: 15 dp[i] = dp[i+1] 16 else: 17 dp[i] = max(P[i]+dp[i+T[i]], dp[i+1]) 18 19print (dp[0]) dp라는 변수를 만들어야하는데 안 만들고 리스트 P만 가지고 memoization 하려다 실패했다 점화식은 잘 적었으나 조건문이 잘 못되어서 다른 풀이를 참고했다

백준 - 13398 : 연속합 2 (G5)

🧠 Algorithm

1N = int(input()) 2L = list(map(int, input().split())) 3res = 0 4dp = [[-1000]*N for _ in range(2)] 5dp[0][0] = L[0] 6for i in range(1, N): 7 dp[0][i] = max(dp[0][i-1]+L[i], L[i]) 8 dp[1][i] = max(dp[1][i-1]+L[i], dp[0][i-1]) 9 10print (max(max(dp[0]), max(dp[1]))) 이번 문제에서 사용할 dp 배열의 크기는 N X 2 이다. 배열은 최솟값인 -1000으로 초기화하여야 한다

백준 - 2502 : 떡 먹는 호랑이 (S1)

🧠 Algorithm

1D, K = map(int, input().split()) 2L = [(1, 0), (0, 1)] 3 4for i in range(2, D): 5 L.append((L[i-2][0]+L[i-1][0], L[i-2][1]+L[i-1][1])) 6 7A = 1 8B = 2 9 10while True: 11 if A*L[D-1][0] + B*L[D-1][1] == K: 12 break 13 14 if A+1 == B: 15 B += 1 16 A = 1 17 else: 18 A += 1 19 20print (A,'\n',B, sep='') 해결방법 N번째날 떡 개수를 구하기 위해 첫째날 떡, 둘째날 떡을 각각 몇번 더해야하는지 리스트에 구한다 첫째, 둘째 날 떡을 하나하나 넣어보면서 브루트 포스를 수행한다

백준 - 15681 : 트리와 쿼리 (G5)

🧠 Algorithm

1import sys 2sys.setrecursionlimit(10**6) 3input = sys.stdin.readline 4N, R, Q = map(int, input().split()) 5G = [[] for _ in range(N)] 6cnt = [1]*N 7visited = [False]*N 8 9for _ in range(N-1): 10 a, b = map(int, input().split()) 11 G[a-1].append(b-1) 12 G[b-1].append(a-1) 13 14def dfs(node): 15 visited[node] = True 16 17 for i in G[node]: 18 if not visited[i]: 19 cnt[node] += dfs(i) 20 return cnt[node] 21 22dfs(R-1) 23 24for _ in range(Q): 25 print (cnt[int(input())-1]) 혼자 풀었다!

백준 - 1967 : 트리의 지름(G4)

🧠 Algorithm

1import sys 2sys.setrecursionlimit(10**6) 3M = int(input()) 4G = [[] for _ in range(M)] 5 6for _ in range(M-1): 7 a, b, c = map(int, input().split()) 8 G[a-1].append((b-1, c)) 9 G[b-1].append((a-1, c)) 10 11n1 = 0 12tmp = 0 13 14def dfs(node, length): 15 global n1, tmp 16 visit[node] = True 17 if length > tmp: 18 tmp = length 19 n1 = node 20 for child, v in G[node]: 21 if not visit[child]: 22 dfs(child, length+v) 23 24visit = [False]*M 25dfs(0, 0) 26tmp = 0 27visit = [False]*M 28dfs(n1, 0) 29print (tmp) 인터넷에서 접근 방법을 참고했다 해결 방법 아무 정점에서 가장 먼 어떤 정점을 N이라고 하자 정점 N에서 가장 먼 정점 사이의 거리가 트리의 지름과 같다 느낀 점 루트를 구할 필요가 없다는 것을 깨달았다

백준 - 1167 : 트리의 지름 (G2)

🧠 Algorithm

1import sys 2sys.setrecursionlimit(10**6) 3input = sys.stdin.readline 4 5V = int(input()) 6G = [[] for _ in range(V)] 7for _ in range(V): 8 token = list(map(int, input().split()))[:-1] 9 for i in range(1, len(token), 2): 10 G[token[0]-1].append((token[i]-1, token[i+1])) 11 12def dfs(node, dist): 13 global max_node, max_dist 14 visited[node] = True 15 if dist > max_dist: 16 max_node = node 17 max_dist = dist 18 for n_node, n_dist in G[node]: 19 if not visited[n_node]: 20 dfs(n_node, dist+n_dist) 21 22max_node = 0 23 24max_dist = 0 25visited = [False]*V 26dfs(0, 0) 27max_dist = 0 28visited = [False]*V 29dfs(max_node, 0) 30 31print (max_dist) 최근에 푼 “1967: 트리의 지름” 덕분에 쉽게 해결할 수 있었다 기억하자 트리의 지름 = (어떤 한 정점에서 가장 먼 점 P)에서 가장 먼 점 사이의 거리

백준 - 14938 : 서강그라운드 (G4)

🧠 Algorithm

1N, M, R = map(int, input().split()) 2 3item = list(map(int, input().split())) 4G = [[] for _ in range(N)] 5for _ in range(R): 6 a, b, c = map(int, input().split()) 7 G[a-1].append((b-1, c)) 8 G[b-1].append((a-1, c)) 9 10def dfs(node, dist): 11 global result 12 if dist > M: 13 return 14 if not visit[node]: 15 result += item[node] 16 visit[node] = True 17 18 for n_node, n_dist in G[node]: 19 dfs(n_node, dist+n_dist) 20 21max_result = 0 22 23for i in range(N): 24 result = 0 25 visit = [False]*N 26 dfs(i, 0) 27 max_result = max(max_result, result) 28 29print (max_result) 분류에 다익스트라, 플로이드-워셜로 되어있지만 DFS로 풀었다 풀이 방법 여기서는 재방문 했다고 해서 탐색을 하지 않으면 안된다 재방문했을때 전에 방문했을 때보다 더 짧은 통로로 들어왔다면 더 많은 아이템을 얻을 수 있기 때문이다 다만, 아이템은 방문할 때마다 얻을 수 있는 것이 아니기 때문에 주의하여야 한다 위의 내용을 질문게시판을 보다가 깨닫고 풀 수 있었다

• ««
• «
• 5
• 6
• 7
• 8
• 9
• »
• »»

🧠 Algorithm (104) 🌊 C/CPP (2) ☕ Java (8) 🍌 Javascript (9) 🐍 Python (9) 🍃 Spring (30) 🔨 개발 도구 (2) 🎸 기타 (5) 👨‍💻 모각코 (38) 🤖 인공지능 (2) 🏫 학과 공부 (27)

🏷️ boj (53) 🏷️ c (5) 🏷️ c++ (4) 🏷️ celery (2) 🏷️ cs (16) 🏷️ django (3) 🏷️ docker (2) 🏷️ docker-compose (1) 🏷️ elk (1) 🏷️ fastapi (4) 🏷️ git (2) 🏷️ github-actions (5) 🏷️ hackerrank (3) 🏷️ https (2) 🏷️ java (37) 🏷️ javascript (2) 🏷️ jwt (1) 🏷️ kubernetes (4) 🏷️ nginx (2) 🏷️ ocaml (1) 🏷️ open-source (2) 🏷️ programmers (48) 🏷️ pytest (1) 🏷️ python (111) 🏷️ rabbitmq (2) 🏷️ rag (3) 🏷️ react (6) 🏷️ security (3) 🏷️ software-engineering (3) 🏷️ spring (31) 🏷️ sql (5) 🏷️ ssl (1) 🏷️ testing (4) 🏷️ typescript (1) 🏷️ vercel (1) 🏷️ websocket (1)