2023년 8월 25일 알고리즘 문제풀이 문제 1 백준 3055 문제 링크 1차 시도 나의 생각 물을 따로 생각하지 말고 이미 방문해서 방문할 수 없는 곳으로 처리한다면 크게 복잡하지 않을 수도 있겠다는 생각을 했다. 따라서 고슴도치가 이동할 곳을 BFS로 탐색하되, 방문처리를 통해 물이 있는 곳과 바위가 있는 곳을 표시하면 되겠다고 생각했다. 주어진 예시는 답을 출력했는데, 고슴도치가 다음 턴에 물이 찰 곳으로 이동할 수 없는 조건이 적용되지 않았다. 따라서 이동할 수 없는 경우가 누락되어 오답처리되었다. ...
2023년 8월 24일 알고리즘 문제풀이 문제1 백준 1916 문제 링크 1차 시도 나의 생각 이전에 공부한 다익스트라로 풀면 되겠다고 생각했다. 출발지부터 각 도착지까지 비용을 표시하는 배열을 만들고 최소값으로 업데이트하였다. 그런데 이상하게 오답처리가 된다. 이유를 찾아봐야겠다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) graph = [[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): s, a, c = map(int, sys.stdin.readline().split()) graph[s][a] = c start, arrive = map(int, sys.stdin.readline().split()) def search(x): cost = [10**9 for _ in range(n+1)] cost[x] = 0 arr = [] heappush(arr,[0, x]) while arr: price, now = heappop(arr) if price > cost[now]: continue for i in range(1, n+1): if not graph[now][i]: continue new_money = price + graph[now][i] if new_money < cost[i]: cost[i] = new_money heappush(arr,[new_money, i]) return cost ans = search(start) print(ans[arrive]) 2차 시도 나의 생각 원인을 찾아냈다. 나는 두 도시간의 비용을 인접행렬로 표현했다. 즉 행렬의 값이 두 도시의 이동 비용이다. 하지만 문제에서 각 도시 간의 노선이 하나라는 보장이 없다.. 그래서 두 도시간의 버스 비용이 중복해서 주어진다면 내 코드는 가장 마지막에 입력된 것만 나타내게 된다. 하지만 먼저 입력된 버스비용이 더 작다면? 내 코드에선 정답을 도출할 수 없었다. ...
4.분할정복 4.4 점화식을 풀기 위한 재귀 트리 방법 **재귀 트리(recursion tree)**에서는 각 노드가 재귀 호출되는 하위 문제 하나의 비용을 나타낸다. 트리의 각 레벨마다 그 비용을 합한 후 모든 레벨당 비용을 합한다. 예시: T(n) = 3T(n/4)+cn^2 T(n) 은 cn^2 + T(n/4) 3개로 이루어진다. 각 T(n/4)는 c(n/4)^2 + T(n/16) 3개로 이루어 진다. 즉 맨 위부터 각 레벨은 cn^2 1개, c(n/4)^2 3개, c(n/16)^2 9개 .. 로 반복됨을 알 수 있다. 이것이 어느정도 깊이까지 반복될까? 크기를 살펴보면 n -> n/4 -> n/16 이므로 레벨 i 에서는 n/(4^i) 임을 유추할 수 있다. 따라서 4^i = n 일때까지 반복되므로 i = log_4(n) 이라는 정수일때 까지 반복된다. i는 0단계부터 였으므로 총 횟수 log_4(n) + 1개 이다. 레벨 i = log_4(n) 이다. ...
2023년 8월 19일 알고리즘 문제풀이 문제 1 백준 1158 문제 링크 1차 시도 나의 생각 요세푸스 문제. deque을 사용해 왼쪽에서 하나씩 꺼내면서 K번째에는 다시 오른쪽으로 넣어주지 않고 정답을 위한 배열에 추가했다. 몇번째인지는 loop가 반복될 떄마다 1씩 더해주고 K로 나눈 나머지를 통해 표시했다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import sys from collections import deque n,k = map(int,sys.stdin.readline().split()) arr = deque() for i in range(1,n+1): arr.append(str(i)) ans = [] cnt = 0 while arr: tmp = arr.popleft() cnt += 1 if cnt%k: arr.append(tmp) else: ans.append(tmp) ans = ', '.join(ans) print('<',ans,'>',sep='') 문제 2 백준 13116 문제 링크 ...
2023년 8월 18일 알고리즘 문제풀이 문제 1 백준 15652 문제 링크 1차 시도 나의 생각 처음엔 조합(combination)을 이용해야하나 생각했다. 하지만 문제가 수를 구하는게 아니라 모든 결과를 출력해야 하기 때문에 조합은 의미가 없을 것이라 생각했다. 어떻게 해야할까 고민하다가 모든 경우를 탐색해야하니 dfs로 풀면 좋겠다는 생각을 했다. 실마리를 찾으니 푸는건 쉬웠다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys sys.setrecursionlimit(10**6) n, m = map(int, sys.stdin.readline().split()) arr = [i for i in range(n+1)] def dfs(x, tmp): if len(tmp) == m: print(*tmp) return for i in range(x,n+1): tmp.append(i) dfs(i,tmp) tmp.pop() for i in range(1, n+1): tmp = [] tmp.append(i) dfs(i, tmp) 문제 2 백준 2357 문제 링크 ...
2023년 8월 17일 알고리즘 문제풀이 문제 1 올바른 괄호 문제 링크 1차 시도 나의 생각 문자열을 앞부터 한글자씩 스택에 넣는다. 여는 괄호’(‘는 무조건 넣고, 닫는 괄호’)‘는 경우가 나누어진다. 스택에 마지막으로 들어가있는 원소가 여는 괄호면 합쳐서 올바른 괄호니 마지막에 들어간것을 pop해준다. 스택이 비어있으면 올바른 괄호가 아니라는 의미이다. 단어의 모든 글자를 순회했는데 아직 스택에 괄호가 남아있다면 올바르지 못한 괄호이다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from collections import deque def solution(s): answer = True arr = list(s) q = deque() for i in range(len(s)): if arr[i] == '(': q.append(arr[i]) else: if not q or q[-1] != '(': return False elif q[-1] == '(': q.pop() continue if q: return False else: return answer 문제 2 디스크 컨트롤러 문제 링크 ...
2023년 8월 15일 알고리즘 문제풀이 문제 1 백준 1697 문제 링크 1차 시도 나의 생각 처음엔 재귀나 피보나치 등 여러 방법을 고민했다. 결국 다이나믹 프로그래밍으로 푸는게 적절하다고 생각했다. 맨처음 n에서 1초후 갈 수 있는 곳은 2n, n+1, n-1 이다. 이들을 큐에 저장하고 이들까지 도달하는데 걸린 시간도 같이 저장한다. 이 큐에서 하나씩 순회하며 2배한 좌표, +1, -1 한 좌표에 시간을 업데이트하고 큐에 다시 저장하는 것을 반복했다. 하지만 예시를 입력하면 올바른 정답이 나오지 않았다. 디버깅해봐야겠다. ...
4.분할정복 4.3 점화식을 풀기 위한 치환 치환(Substitution)법 : 귀납 가정을 더 작은 문제에 적용할 때 추측한 해로 치환한다. 해의 모양을 추측한다. 상수들의 값을 찾아내기 위해 수학적 귀납법을 사용하고 그 해가 제대로 동작함을 보인다. 이 책에서는 결과로 나올 해의 모양을 추측하여 치환하는 것에 대한 설명이 많다. 하지만 실제로 양 변에서 공통된 모양을 추출하여 새로운 수열로 치환함으로서 풀 수 있는 점화식 이많다. 예시
2023년 8월 12일 알고리즘 문제풀이 문제 1 백준 18352 문제 링크 1차 시도 나의 생각 도시까지의 최단거리만 생각해야 하므로, bfs를 통해 도착한 도시에 얼마나 걸렸는지를 표시하고, 이를 방문표시로 이용하면 되겠다는 생각을 했다. 출발한 도시 와 도착지가 같을때는 0으로 표시하게 되는데, 이것 때문에 아직 방문처리하지 않은 것으로 취급되어 여러가지로 헷갈렸다. 따라서 제자리 거리를 1로 표시하여 모든 도시의 거리를 구하고 모두 1 만큼 감소시켜주었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import sys from collections import deque n, m, k, x = map(int, sys.stdin.readline().split()) graph = [[]for _ in range(n+1)] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) ans = [] visited = [0 for _ in range(n+1)] def bfs(s): visited[s] = 1 arr = deque() arr.append(s) while arr: now = arr.popleft() for next in graph[now]: if not visited[next]: arr.append(next) visited[next] = visited[now]+1 bfs(x) ans = [] if k == 0: print(x) else: for i in range(1, n+1): visited[i] -= 1 if i == x: continue if visited[i] == k: print(i) ans.append(i) if not ans: print(-1) 문제 2 백준 2178 문제 링크 ...
2023년 8월 11일 알고리즘 문제풀이 문제 1 백준 1010 문제 링크 1차 시도 나의 생각 결국 서쪽에 있는 사이트는 모두 사용 되야 하므로 첫번째 사이트부터 고를 수 있는 상황에 대해 dfs를 적용하고 모든 다리가 결정될 때마다 카운트하는 방법을 생각했다. 그런데 가만 생각해보니 다리끼리 교차될 수 없으므로 동쪽의 사이트 중 서쪽의 사이트의 갯수만큼 선택하면 다리가 연결되는 경우의 수는 한개 뿐이다. 따라서 조합(Combination)을 사용하면 되겠다고 판단했다. 모듈을 까먹어서 그냥 직접 구현했다. 결과 정답 ...