보호되어 있는 글입니다.

접근 1. dp를 이용하여 dp[i]를 길이가 i일때 i번째 수로 만들 수 있는 증가하는 부분 수열의 길이로 둔다. dp[i+1]를 구하기 위해 i+1보다 더 작은 수들을 찾는다. 이 수들 중 dp의 값이 가장 큰 수를 j라고 한다면 dp[j]+1 이 dp[i+1] 이 된다. 2. 직접 가장 긴 증가하는 부분 수열을 만든다. 10 12 20 8 9 10 15 30 50 이라는 수열이 있다고 생각해보자. arr = [0] 를 두고 arr[-1] 보다 크면 추가, 작으면 기존 수와 교체하여 구한다. arr = [0 10 12 20] 이면 다음 수가 8이다. 이때 기존수 10과 교체한다. 이 문제는 부분 수열의 길이를 구하는 문제이기 때문에 중간에 끝나더라도 길이 자체는 그대로 출력되게 된다. 나의 코드(직접..

접근 일단 LCS가 어떤건지 기억이 안나 관찰하면서 감을 잡았다. ACAYK와 CAPCAK에 대한 LCS로 ACAK라고 한다. 두문자열이 있을때 첫번째 문자의 1,2,3,5 인덱스에서 ACAK를 찾을 수 있고 2,4,5,6 인덱스에서 ACAK를 찾을 수 있다. 그리고 2개의 문자열을 놓고 각 자리까지의 LCS를 직접구해보았다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K 1 2 3 3 4 4 이렇게 직접 구했는데 점화식을 알기가 너무 어려웠다. 같을 때 1이 올라가고 다를때는 옆과 밑에서 값을 가져오면 된다는건 직접 구하면서 느꼈는데 코딩으로 옮길때 1행과 1열쪽이 어떻게 구해야하는지 감이 오지않았다..

접근 문제를 보고 일반적인 그래프 탐색 문제라고 생각했다. 여기서 어려웠던점은 벽을 한개까지 부술수있다는 점인데 이 부분이 너무 까다롭다고 느껴졌다. 처음 생각은 bfs를 한번 돌리고 그러면서 닿는 벽들의 좌표를 set에 저장하고 벽을 빼고 넣으면서 계속 bfs를 돌리려는 생각을 했다. 또 두번째 생각은 처음과 끝에서 bfs를 돌려서 각각 맞닿는 벽을 set에 저장하고 이 두 set의 교집합을 통해 뺄 벽을 정하는 방법을 생각했다. 하지만 두 방법 모두 시간이 오래걸려 결국 실패했다. 그리고 마지막에 할 수 있었던 생각이 visit을 3차원으로 만드는 것이었다. bfs는 각 visit[i][j][0] 가 있다면 항상 가장 빠르게 도달하는 횟수가 visit[i][j][0]에 저장된다. visit[y][x]..

접근 입력이 문자로 들어오니 dict 을 사용해서 트리를 구성해야겠다. 나의 코드 import sys input = sys.stdin.readline T = {} n = int(input()) for _ in range(n): s,*string = list(map(str,input().split())) T[s] = string def pre(start): if start != '.': print(start,end='') pre(T[start][0]) pre(T[start][1]) def inorder(start): if start != '.': inorder(T[start][0]) print(start,end='') inorder(T[start][1]) def po(start): if start != '..

접근 트리에서 임의의 한점이 선택된다고 생각하자. 그렇다면 거기서부터 어떻게 트리의 최대 거리를 구할 수 있을까? 최대 거리는 가장 먼 2개의 점을 고르는 것과 같다. 임의의 한점에서 가장 먼 노드로 간다면, 가장 먼 2개의 점중 한점에 가게된다. 그리고 그 두개의 점중에서 가장 먼 노드를 구한다면 어떤 점으로 처음 출발하더라도 가장 긴 지름을 구할 수 있다. 가장 먼 노드를 구하는 방법은 bfs, dfs(다익스트라) 모두 가능하다. 전에 1167 트리의 지름으로 이미 풀어본 문제인데 복습할겸 다양한 방법으로 풀어봤다. 요즘 다익스트라가 너무 익숙해져서 힙을 이용한 다익스트라로도 풀었는데 heappop은 시간복잡도가 O(logn)이고 모든 노드가 한번씩 방문되기 때문에 queue를 쓰는것과 계산상 다를게..