본문 바로가기

분류 전체보기

 (698)
04. 탐욕법 [1. 개요] 탐욕법은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다. 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없으나, 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다는 것이 다르다. 그래서, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다. 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있다. => 모든 단계를 고려하는 동적 계획법이 틀릴 이유가 없기 때문 그럼에도, 탐욕법을 사용하는 이유는 동적 계획법에 필요한 메모리나 시간이 너무 크기 때문이다. 탐욕적 알고리즘을 설계하는 좋은 방법은 간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것 [2. 사용되는 경우] A. 탐욕법을 사용..
03. 동적계획법 - 예제4 [1. 문제 설명] 2xN 크기의 직사각형을 2x1 크기의 타일로 채울 때 좌우 대칭으로 채우지 않는 경우의 수를 구한다. 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지 (1e9 + 7) [2. 풀이 접근] A. 여사건 방식 전체 타일링 방법에서 대칭 타일링 방법의 수를 빼서 구한다. 대칭 타일링 수는 n 이 짝수인 경우와 홀수인 경우를 나누어서 생각한다. n 이 짝수인 경우 => 가운데를 가로 타일링으로 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식 => 절반 한쪽을 채우고, 나머지 한쪽을 마찬가지로 동일하게 채우는 방식 n 이 홀수인 경우 => 가운데러르 세로 타일링을 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식 == 전체 계산 후 주의할 점 =..
03. 동적계획법 - 예제3 [1. 문제 설명] 수열을 s 가지의 자연수만을 이용하여 양자화 하였을 때, 각 숫자별 오차 제곱의 합을 최소 값을 출력한다. 양자화 => 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현 [161, 164, 178, 184] => 160, 170, 180 으로 표현.. [2. 풀이 접근] A. 잘못된 접근 주어진 수열 A 이 첫번째 수자를 어떤 숫자로 표현할 것인지 결정하고 나머지 수열에 대해 재귀 호출하는 방식 => 양자화에 사용 할 숫자에 제한이 있어서, 현재 까지의 결정이 앞으로의 결정에 영향을 준다 => 최적 부분 조건이 성립하지 않는다. => 메모이제이션에 필요한 메모리 확보도 어려울 것. ==> 입력 상, 1000 이하의 숫자 중 10 개의 숫자를 선택하는 경우를 고려해보면...
트리. [5639] [1. 문제 설명] 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. (재귀적임) 이진 트리의 전위 순회 결과가 있을 때, 후위 순회 결과를 출력한다. [2. 풀이 접근] 전위 순회 결과가 주어졌을 때, 트리의 구조를 대강 알 수 있다. Root [... Left sub tree....] [....Right sub tree....] 여기서 Right sub tree 의 시작점은 root 보다 큰 값이 시작하는 위치이므로, 간단한 탐색으로 알 수 있다. Left sub tree 와 Right sub tr..
트리. [2263] [1. 문제 설명] n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 중위 순회와 후위 순회가 주어졌을 때, 전위 순회를 구한다. [2. 풀이 접근] 각 순회를 보면 트리의 대략적인 구조를 알 수 있다. 중위 순회: [.... Left sub tree...] Root [.... Right sub tree....] 후위 순회: [.... Left sub tree...] [.... Right sub tree....] Root 후위 순회의 마지막 원소는 전체 tree 의 root 임을 알 수 있다. 이렇게 알아낸 root 를 통해 중위 순회에서 해당 root 의 left sub tree 와 right sub tree 를 알 수 있다. 이제, Left..
트리. [1991] [1. 문제 설명] 이진 트리를 입력 받아 전위 순회, 중위 순회, 후위 순회 결과를 출력하도록 한다. (tree 에서 node 의 값은 알파벳이며, child 가 없는 경우 '.' 으로 표시한다.) [2. 풀이 접근] A. 재귀로 푸는 방법 전위 순회(inorder traverse) 를 예로 들면, root left_sub_tree right_sub_tree root 를 먼저 방문하고, 왼쪽 sub tree 를 그 다음으로 방문하며, 오른쪽 sub tree 를 가장 마지막에 방문한다. 여기서, left_sub_tree, right_sub_tree 에 대해서 동일하게 각 sub tree 에 root 를 먼저 방문해야 하는데, 이는 전체 문제의 부분 문제로 다룰 수 있다. 따라서 재귀적으로 접근 할 수 있..
트리. [1967] [1. 문제 설명] Tree 는 Cycle 이 없는 무방향 그래프이다. Tree 에서는 어떤 두 노드 간 경로는 항상 하나만 존재한다. 트리의 지름은 트리에 존재하는 모든 경로 중 가장 긴 것의 길이이다, [2. 풀이 접근] 다음과 같은 문제 (https://testkernelv2.tistory.com/351) [3. 코드]
트리. [1167] [1. 문제 설명] 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것의 길이를 출력한다. (트리의 지름을 구한다.) [2. 풀이 접근] A. 잘못된 접근 방식 1 => 모든 노드에서 DFS 를 수행한다. => 당연히 시간 초과 발생 (정점의 최대 개수는 200,000 개이므로, V^3 의 시간은 2초내에 풀 수 없다.) B. 잘못된 접근 방식 2 => 모든 edge 중 가중치가 가장 긴 것을 찾는다. => 이 edge 에 속한 노드 중 하나를 root 로 하여, bfs 수행 ## 보통 트리의 지름은 leaf 에서 leaf 이므로, 가장 긴 edge 가 이 지름에 속할 것으로 생각함 ## bfs 순회 중, root 에서 가장 먼 정점을 구할 수 있다. ## 방문 순서가 늦을 수록 root 에서 멀리 존재..
트리. [11725] [1. 문제 설명] 루트가 1인 트리가 입력으로 주어질 때, 각 노드의 부모노드를 구하도록 한다. [2. 풀이 접근] Tree 자료구조 특징) A. 하나의 노드는 여러 개의 자식을 가질 수 있어도, 부모는 하나만 가질 수 있다. => 아래와 같은 형태는 트리가 아니다. => B, C, D 는 A 라는 하나의 노드를 부모로 갖지만, => E, F 는 여러개의 부모 노드를 갖는다. => 이로 인해 아래 성질을 만족하지 못한다. B. 루트에서 어떤 노드로 가는 경로는 유일하다. => 임의의 두 노드 간의 경로도 유일 하다 => 두 개의 정점 사이에 반드시 1개의 경로만을 갖는다. C. Root 노드는 다른 모든 노드들을 자손으로 갖는 노드로, Tree 에서 딱 하나 존재 D. Leaf 노드는 자식이 하나도 없..
최단 경로. [1956] [1. 문제 설명] 임의의 방향 그래프 내 Cycle 경로 중 길이가 가장 짧은 것을 출력하도록 한다. 없을 경우 -1 을 출력 [2. 풀이 접근] A. Cycle => 그래프에서 Cycle 은 시작점에서 출발하여 다시 자기자신으로 돌아오는 것을 말한다. 문제에서 지정한 출발지점이 없으니, 모든 시작정점에서 사이클이 있는지 없는지 판별하고, 있다면 그 중 최소 경로를 반환해야 하는데, 사이클을 찾는 것은 둘째치고, 각 시작정점에서 최단 경로를 찾는 것만으로도 시간초과가 발생할 수 있다. (관련 예제=> https://testkernelv2.tistory.com/348) 문제 입력에서 정점의 개수가 400 개이므로 플로이드-와샬 알고리즘 사용을 고려해볼 수 있다. 플로이드-와샬 알고리즘 사용 시 사이클을 ..

티스토리툴바