접근 위상 정렬을 이용해 현재 접근 가능한 수 중 가장 작은 값을 출력한다 N 사이즈의 풀 수 있는 다음 문제가 담긴 2차원 리스트, 접근하기 위해 풀어야 하는 선행 문제의 갯수가 담긴 int 리스트를 선언한다. M 개의 조건문을 받고 A -> B 를 바라보도록 리스트에 추가해준다. B 의 선행문제 갯수는 하나 올라간다. 선행문제 카운트 리스트를 훑으며 지금 진입 가능한 (선행문제가 0인) 문제 번호들을 Priority Queue 에 넣는다. Priority Queue 에서 값을 뽑는다. 이 문제가 바라보는 다음 문제들을 훝으며 각각의 선행 문제 갯수를 하나씩 뺀다. 이 과정에서 선행 문제 갯수가 0이 된 문제들을 Queue 에 추가해준다. 사고 혹시나 나처럼 헷갈리는 이들이 있을까 싶어 문제 조건을 확실히 해두고 싶다. ...
접근 처음 두 줄의 LCS 를 찾고, 그 결과와 마지막 줄의 LCS 를 찾는 순차적인 방법으로도 가능하다. 하지만 3차원 dp 로 처리하는 방법이 확장 가능성이 있기에 더 좋은 접근법이라 생각한다. import sys input = sys.stdin.readline f = input().strip() s = input().strip() t = input().strip() fl = len(f) sl = len(s) tl = len(t) dp = [[[-1] * tl for i in range(sl)] for j in range(fl)] def LCS(a, b, c): if a < 0 or b < 0 or c < 0: return 0 if dp[a][b][c] == -1: dp[a][b][c] = 0 if f[a] == s[b] == t[c]: dp[a][b][c] = LCS(a - 1, b - 1, c - 1) + 1 else: dp[a][b][c] = max(max(LCS(a, b - 1, c), LCS(a - 1, b, c)), LCS(a, b, c - 1)) return dp[a][b][c] print(LCS(fl - 1, sl - 1, tl - 1))
접근 dfs로 탐색을 하다 탐색한 부분이 다시 발견되면 cycle 이 성립한다. directed-graph 이기에 가능한 성질이다. 사고 단방향 그래프를 많이 다뤄보지 않아서 시간이 걸렸다. 처음에는 깊이 우선으로 탐색하다 방문한 곳이 나온다면 그 자리부터 한 바퀴를 세 주는 방법을 고려했다. 하지만 하나의 방문 확인 리스트로는 그 자리가 사이클 탐색까지 완료한 자리인지 아니면 사이클이 시작되는 자리인지 판단할 수 없다. 그래서 각각의 dfs가 시작될 때 temp_visited 를 따로 선언해주고 dfs 가 끝나면 temp_visited 에 들어간 자리들을 global_visited 에서도 업데이트해주었다. 우회적인 방법이라 판단되어 더 좋은 접근법이 얼마든지 있을 것 같다. ...
접근 정해진 길이가 없기에 사이즈가 자유로운 윈도우 사이즈로 수열을 탐색한다. 앞의 포인터를 post, 뒤를 pre라 할때 윈도우의 합이 S 보다 커질때까지 post가 앞으로 움직인다. 윈도우 합이 S 보다 작을때까지 pre가 앞으로 움직인다. 움직임이 끝나면 현재 윈도우 길이가 최소 길이보다 짧은지 비교한다. 사고 O(N) 풀이법이 쉽게 떠오른데 비해 정답률이 낮아서 의아했다. 하지만 나도 코너 케이스와 조건문 처리에서 몇번 틀려서 다시 제출했다. 몇번 고쳐서 넣으면 답이 나오긴 하는데 처음 접근에서 더 많은 경우의 수를 고려하는 연습이 필요한 것 같다. ...
solved.ac class 5의 essential 문제로, 위상 정렬에 대한 이해가 있다면 어렵지 않게 풀수 있다. 위상 정렬에 대해서는 따로 알고리즘 포스팅에 정리해놓겠다. 문제를 풀때 사고방식은 이랬다. 특정 건물 K를 짓기 시작하는 시점은 이전에 지어야 하는 건물들 중 가장 오래 걸리는 건물들을 선택해서 도달한 시점이다. 여기에서 dp 개념이 필요하며, 나머지는 백준 2252 줄 세우기 문제의 위상 정렬 접근법을 이용한다. import sys from collections import deque input = sys.stdin.readline T = int(input()) for test in range(T): N, K = map(int, input().split()) time = list(map(int, input().split())) cnt_enter_link = [0] * (N) graph = [[] for _ in range(N)] dp_build_time = [0] * (N) for _ in range(K): a, b = map(int, input().split()) graph[a - 1].append(b - 1) cnt_enter_link[b - 1] += 1 q = deque() for i in range(N): if cnt_enter_link[i] == 0: q.append(i) w = int(input()) - 1 while(q): c = q.popleft() if c == w: print(dp_build_time[c] + time[c]) for i in graph[c]: cnt_enter_link[i] -= 1 dp_build_time[i] = max(dp_build_time[i], dp_build_time[c] + time[c]) if cnt_enter_link[i] == 0: q.append(i)