Problem Solving/BOJ - Python (23) 썸네일형 리스트형 [Python | 파이썬] 백준 1068 트리 [Python | 파이썬] 백준 1068 트리 0번부터 n-1번 노드에 대해서 루트노드이면 -1, 그렇지 않으면 부모노드의 번호가 입력으로 한 줄에 주어진다. -1이면 root에 저장해주고, -1이 아니라면 부모노드가 있는 노드이다. 이 문제에서 트리의 간선은 양방향 간선이므로 s[i][arr[i]] = True, s[arr[i]][i] = True로 초기화해준다. 그리고 지울 노드의 번호와 연결된 간선들은 모두 False로 갱신해준다. 이후 dfs를 이용해 모든 노드를 탐색하는데 방문하는 노드의 visit배열을 True로 설정해준다. 그리고 flag 불리언 값을 False로 초기화하고, 현재 노드에 자식노드가 한개라도 있고 그 자식노드를 방문하지 않았으면 flag를 True로 바꿔주고, 재귀적으로 탐색.. [Python | 파이썬] 백준 9252 LCS2 [Python | 파이썬] 백준 9252 LCS2 앞서 풀은 LCS와 기본 풀이는 비슷하지만 이 문제는 그 최장 공통 수열까지 출력해야하기 때문에 각 dp의 원소에 길이를 저장하는 것이 아니라 수열자체를 저장해야한다. 인덱스를 어떻게 다루느냐에 따라 두가지 방법으로 풀 수 있다. 첫 번째 방법은 dp는 입력으로 주어진 수열a 의 길이 + 1 을 행의 길이로 하고 수열b의 길이 + 1을 열의 길이로 하며 처음에 빈문자열로 초기화한다. 이때 처음에 주어진 각 수열 a,b의 맨앞에 [0]이라는 원소를 추가해주어 인덱스를 편하게 할 수 있게 한다. 두번째 방법은 이전문제에서 풀었던 방법과 같은 방법이다. 이때 중요한 점은 어떤 방법으로 풀더라도 dp의 행과 열은 입력으로 주어진 문자열보다 각각 1씩 크게 행, .. [Python | 파이썬] 백준 9251 LCS [Python | 파이썬] 백준 9251 LCS LCS Longest Common Subsequence 최장 공통 부분수열 문제는 dp를 이용해서 풀 수 있다. 두 개의 문자열에 대해서 최대한 겹치는 문자열의 길이를 출력하는 문제이다. b문자열을 열 - 가로로 일직선 방향에 두고 a문자열을 행 - 세로로 일직선 방향에 두고 인덱스를 증가시키면서 확인한다. 우선 0 [Python | 파이썬] 백준 12015 가장 긴 증가하는 부분 수열2 [Python | 파이썬] 백준 12015 가장 긴 증가하는 부분 수열2 이 문제는 제한 시간 1초 안에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)을 만족하도록 풀기 위해서는 이진 탐색을 이용해야 한다. 또한 문제에서 요구하는 것은 부분 수열의 길이이지 부분수열 전체를 출력하는 것이 아니기 때문에 이러한 풀이가 가능하다. 참고한 블로그 => https://suri78.tistory.com/199 https://sihyungyou.github.io/baekjoon-12015/ 수열의 각 원소는 1이상의 양수이므로 처음에 0을 stack에 넣는다. 그리고 수열 A의 각 아이템에 대해서 stack의 최상단 원소보다 더 크다면 stack에 삽입한다. 그리고 최상단 원소보다 작거나 같다면 각 아이템이.. [Python | 파이썬] 백준 14002 가장 긴 증가하는 부분 수열4 [Python | 파이썬] 백준 14002 가장 긴 증가하는 부분 수열4 이 문제는 dynamic programming을 이용해 풀어야하는 문제이고, 가장 긴 증가하는 부분 수열의 길이와 함께 그 부분 수열을 출력해야한다. 따라서 각 인덱스에 현재 부분 수열의 길이와 현재 인덱스에서 가장 긴 부분 수열을 담은 배열을 저장하고 있어야한다. 처음에는 각각 num[i] 원소 한 개를 배열로 하여 부분 수열의 원소로 갖는 것으로 dp를 초기화해준다. dp = [[1, [num[i]]] for i in range(x)] 그리고 1번부터 x-1번까지 증가하는 i 인덱스에 대해서 0번부터 i-1번까지 증가하는 j 인덱스를 탐색하며 조건을 만족하면 dp[i]를 갱신한다. 이때 num[i]가 num[j]보다 커야하고, .. [Python | 파이썬] 백준 11722 가장 긴 감소하는 부분 수열 [Python | 파이썬] 백준 11722 가장 긴 감소하는 부분 수열 이문제는 dynamic programming을 이용하여 풀 수 있는 문제이다. 0번부터 n-1까지 증가하는 인덱스 각각에서 현재 인덱스보다 작은 인덱스까지의 부분 수열을 확인한다. 즉 0번 인덱스 => 확인 안한다. 1번 인덱스 => 0번인덱스를 확인하여 0번인덱스의 수가 1번 인덱스보다 크다면 dp[1] = max(dp[1], dp[0]+1) 을 실행한다. 2번 인덱스 => 0번 인덱스를 확인하고 0번 인덱스가 2번 인덱스보다 크다면 dp[2] = max(dp[2], dp[0]+1)을 실행한다. 1번 인덱스를 확인하고 1번 인덱스가 2번 인덱스보다 크다면 dp[2] = max(dp[2], dp[1]+1)을 실행한다. 또한 처음에 각.. [Python | 파이썬] 백준 11725 트리의 부모 찾기 [Python | 파이썬] 백준 11725 트리의 부모 찾기 루트 없는 트리가 주어질 때 이 트리의 루트를 1이라고 정한다면 2번 노드부터 n번 노드까지의 루트 노드를 출력하는 문제. 이 문제에서 루트 노드란 자신의 바로 위에 있는 노드를 루트 노드로 정의한다. 일반 트리에서의 루트와 개념이 다르다. 루트노드의 정의가 헷갈릴 수 있지만 테스트케이스를 꼼꼼히 읽으면 이해할 수 있었다. 즉 1-2, 2-4 간선이 있다면 4의 루트노드는 1이 아니라 2임 노드의 개수가 최대 100,000개이므로 dfs 재귀방식을 이용해서 풀때에 recursionlimit을 100,000으로 설정해준다. 간선의 방향은 상관없기 때문에 maps배열에 maps[a].append(b), maps[b].append(a) 두번 추가해준.. 이전 1 2 3 다음
