접근 주어진 문자열의 각 문자를 결과 문자열(ans)에 추가한다. 만약 ans[-1] 이 폭발 문자열의 마지막 bomb[-1] 과 같다면 ans[-len(bomb):] 과 bomb[:] 을 비교하여 같으면 폭발시킨다. 사고 worst case time complexity 가 10**6 이길래 O(n) 으로 되는 문제인가 고민했다. 넉넉히 된다. 조건을 이해했을때 ‘모든 폭발 문자열이 폭발하고 새로운 문자열이 생긴다’ 여서 폭발 문자열을 발견할때마다 폭발하는거랑 결과가 혹시 다른가 고민해보았다. 반례가 떠오르지 않아 O(n) 스택으로 풀었다. 한가지 처음에 arr = arr[0:arr - len(bomb)] 이렇게 넣었다가 TLE 떴다. 저렇게 넣어도 파이썬이 optimization 하지 않을까 했는데 정직하게 주어진 인덱스만큼 복사하는것 같다. pop으로 뒤에 있는 문자열을 날리는 방법으로 풀어야 한다. ...
접근, 사고 확실히 푼 문제 수가 쌓일수록 유형별로 나눠서 생각하기가 수월한것 같다. 이 유형의 베이스는 Two Sum 이다 (무려 리트코드의 첫번째 문제!!). 배열을 탐색하며 두 개의 합의 target 이 되는 쌍을 찾는 문제인데 해쉬를 이용해 한 번 linear 로 훑는 것으로 풀 수 있다. 대략적인 풀이과정은 set 선언 배열 지나가며 각각 원소 i에 대해 target - i 가 set 에 있으면 해당 쌍 리턴, 없으면 set.add(i) 해준다. 본 문제도 이와 크게 다르지 않다. ...
접근 s 와 e 를 받아서 2차원 배열로 각각의 질문에 O(1) 에 답하는 것이 목표이다. 2000 X 2000 배열을 미리 초기화 한다면 초기화에 O(N ^ 2), 질문에 답하는 데 O(1) 이다. 점화식으로 top-down 으로 접근해서 풀었다. 이때 질문과 답하면서 배열을 조정한다. dp[s][e] 는 dp[s + 1][e - 1] 이 팰린드롬이라면 칠판배열[s] == 칠판배열[e] 에 따라 갈린다. base case 는 s == e 와 s == e - 1 인 경우 (s + 1, e - 1을 조회할 수 없기 때문에) 로 뒀다. 사고 이렇게 대놓고 배열로 풀어주세요 하는 건 어느정도 익숙하다. DP 중에 무엇을 메모이제이션해야 할 지 감이 안 오는 문제들이 훨씬 어려운 것 같다. ...
접근 열 길이가 기차의 수 + 1이고, 행 길이가 3인 dp 행렬로 접근한다. 13번째 행은 각각 현재 인덱스에서 13번째 열차가 골라졌다면 실을 수 있는 최대 손님의 수다. 입력으로 받은 train 리스트를 탐색하며 window 만큼 떨어져 있는 dp 를 업데이트 한다. dp 업데이트는 dp[현재 열 - window][현재행 - 1] 과 dp[현재 열 - 1][현재 행] 중 큰 것을 고른다. 사고 반복되는 연산을 최소화하는 DP 문제를 연습하는 중이니 다른 최적화도 가능하다면 시도해보자. 문제에서 소형 기관차의 길이가 길다면 겹치는 구간을 반복해서 구해야 할 것이다. ...
접근 방문 기록을 리스트로 기억한다. DFS 에 현재 탐색 중인 좌표들이 담긴 큐와 현재 위치를 인자로 받는다. 방문마다 방문 기록을 업데이트 해주고 DFS 를 진행한다. 방문한 곳을 마주하면 경우는 두 가지이다. Safe zone 으로 나갈 수 있는 경우, 만들어줘야 하는 경우. 사고 제약 조건이 적어 쉽게 접근할 수 있었다. 사이클을 찾으면 그 사이클과 사이클에 들어올 수 있는 모든 경로는 Safe Zone 하나로 도망 가능하다. 이 원칙 하나로 구현하면 큰 어려움 없이 풀 수 있다. ...
접근 위상 정렬을 이용해 현재 접근 가능한 수 중 가장 작은 값을 출력한다 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)