본문 바로가기

알고리즘

(405)
KMP. [1786] [1. 문제 설명] https://www.acmicpc.net/problem/1786 [2. 풀이 접근] KMP 알고리즘 (Text 에서 Pattern 이 존재하는 모든 시작위치를 반환) T[i...] 에서 P[...n] 이 일치하지만, P[n+1] 에서 불일치 한 경우 다음 탐색 위치를 좀 더 효율적으로 설정하여 탐색 속도를 빠르게 한다. P[...n] 이 일치하였으므로, P[...n] 에서 접두사와 접미사가 같은 곳이 있다면, 탐색 위치를 접두사 길이 만큼 점프할 수 있다. [3. 코드]
BFS. [14502] [1. 문제 설명] https://www.acmicpc.net/problem/14502 [2. 풀이 접근] 그래프 순회가 필요한 이유 이차원 배열에서 바이러스가 퍼져나간다. BFS 를 통해 이러한 과정을 모델링 할 수 있다. 완전 탐색 지도의 최대 크기는 8x8 이며, 여기서 반드시 벽을 놓을 위치 세곳을 정해야 한다. 전체 경우의 수는 64C3 으로 대략 41,664 로 현실적인 경우의 수 인 것을 알 수 있다. => 현실적인 경우의 수 라면, 완전 탐색이 가장 안전한 풀이가 가능하다. 중복문제 벽을 놓을 위치를 정하는 것은 재귀 함수로 구현 할 수 있다. 문제는 벽을 놓을 때, 중복으로 놓은 경우를 막아야 한다는 것이다. 보통 중복으로 세는 경우를 방지하기 위해서는 항상 특정 형태로 답을 세는 것이다..
구간 트리 솔루션 [1. 개요] 구간 트리란? 보통 일차원 배열을 대상으로 특정 구간에 대한 쿼리를 O(logn) 에 할 수 있다. 구간 트리를 대상으로 하는 연산은 크게 3가지로 아래와 같다. 1. init() 2. query() 3. update() 구간 트리 존재 의의 특정 구간의 합은 부분합으로 더 빠르게 O(1) 만에 구할 수 있지만, 어떤 원소의 값이 바뀌면 O(n) 의 시간을 들여 부분 합을 다시 만들어야 한다. 구간 트리는 O(logn) 으로 update 하고, 구간의 합을 O(logn) 으로 구할 수 있다. 구간 트리 구현을 아래와 같이 한가지 패턴으로 작성하도록 한다. u # 구간 트리의 노드 번호, (Root 의 노드 번호는 1 이다.) left # u 의 포함되는 구간의 가장 왼쪽 right # u ..
우선 순위 큐 관련 솔루션 [1. 개요] 우선 순위 큐(=편의 상 힙으로 표기) 는 정렬 상 우선순위가 높은 원소를 먼저 꺼낼 수 있는 큐이다. 최대 힙 최소 힙 힙을 대상으로 하는 push 와 pop 모두 O(logn) 으로 동작한다. 힙 내부 데이터 변경으로 인해 heapify 가 필요할 수도 있지만, 이런 경우에 자주 없다. 다익스트라에서 특정 노드에 대한 가중치가 바뀌는 경우가 대표적이지만, 이 때에는 힙에 다시 푸쉬하는 편이 더 간단하다. heapify 는 보통 O(n) 으로 동작하여 다소 느려, 오히려 더 안 좋을 수 있다(?). 보통의 문제는 크게 최대 힙, 최소 힙 둘 중 하나만 사용하는 경우가 다수이지만, 두 가지 힙 모두 사용하여 풀어야 하는 문제도 간혹 존재한다. 대표적으로 Running median 같은 문제..
이진 검색 트리 솔루션 [1. 개요] 자료 구조 구현 이진 트리는 그 특성 상 배열을 이용하여 구현한다. index 0 은 사용하지 않고, index 1 을 루트로 사용한다. leaf node 는 왼쪽 노드가 maxNode 보다 큰 경우이다. => 왼쪽 노드가 없으면 오른쪽 노드도 당연히 없다. => 보통 노드 개수가 문제에 주어진다. (완전 이진 트리가 아닌 이상, 마지막 노드 id 를 유추 할 수 없으므로?) 완전 이진 트리 모든 레벨에 노드가 가득찬 이진 트리이다. 트리의 깊이가 K 일 때, 노드의 개수가 2K-1 개를 갖는다. maxNode id 는 2^k 이다. => k == 2, 트리에 존재 할 수 있는 노드 id 는 1, 2, 3 => maxNode == 4 각 레벨 별 노드 id 범위를 쉽게 구할 수 있다. =>..
이진트리. [9934] [1. 문제 설명] https://www.acmicpc.net/problem/9934 [2. 풀이 접근] 먼저 문제에서 주어지는 트리는 완전 이진 트리이다. 완전 이진 트리는 이진 트리의 한 형태로, 트리의 깊이가 K 일 때, 노드의 개수가 2K-1 개를 갖는다. 즉, 모든 레벨에 노드가 꽉 차있는 이진 트리이다. 트리의 방문 순서를 통해서 트리 구성을 역추적하는 문제는 트리가 재귀적인 특성이라는 것을 이용하도록 한다. 즉, 방문하는 함수를 재귀로 구현하면 된다는 것이다. 방문 순서가 문제에 조건으로 주어져 있으므로, 문제 조건을 그대로 함수에 구현하되, 재귀적으로 작성하면 된다. 재귀 함수는 보통 아래와 같이 작성하도록 한다. 재귀의 종료 조건 재귀 호출 [3. 코드]
트리 관련 문제 솔루션 [1. 개요] Tree 자료 구조의 특징 하나의 노드는 여러개의 자식을 가질 수 있어도, 부모는 하나만 가질 수 있다. 루트에서 어떤 노드로 가는 경로는 유일하다. => 부모가 반드시 하나만 있다는 점을 생각해보자. => leaf 에서 위로 올라가는 경로는 유일하다. Root 는 트리에서 딱 하나 존재한다. Leaf 는 자식이 없는 노드이다. Cycle 이 존재하지 않는 연결그래프 (무방향) 이다. => 어떤 그래프에서 DFS 를 한번 수행하면, DFS 스패닝 트리가 된다. => 어떤 그래프에서 BFS 를 한번 수행하면, 역시 트리가 된다. => 이러한 점을 고려하도록 한다. Tree 의 지름 재귀적인 성질을 갖는다. => 재귀적인 방식으로 코드를 작성해야 하는 이유이다. => 전위, 중위, 후위 순회...
트리. [1086] [1. 문제 설명] https://www.acmicpc.net/problem/1068 [2. 풀이 접근] leaf node 는 자식 노드가 없는 노드이므로, 문제에서 요구한 대로, tree 에서 노드를 제거 한 뒤, 자식 노드가 없는 노드의 개수를 세면 된다. 다음은 tree 에서 노드를 제거하는 방법이다. 아래 그림에서 a 노드를 제거해야 할 때, a 와 연결된 그 자식 노드만 제거한다면 (그 연결을 끊는다면), d, e 노드가 제거되지 않는다. 즉, 제거할 노드를 root 로 하는 서브 트리를 전체 tree 에서 제거해야 한다. tree 는 재귀적인 성질을 갖고 있으므로, 이 sub tree 역시 재귀적인 방법으로 제거하면 된다. 다음은 제거할 노드와 그 부모노드간의 연결성이다. 아래 그림에서 a 노..
큐 관련 문제 솔루션 [1. 개요] [2. 예제] https://testkernelv2.tistory.com/467 https://testkernelv2.tistory.com/426 https://testkernelv2.tistory.com/415 => queue 를 교차하여 사용하지 않고, (이 방법은 다소 시간이 걸림) => 세그먼트 트리를 이용해서 풀 수 있다. d e f
큐. [2161] [1. 문제 설명] https://www.acmicpc.net/problem/2161 [2. 코드] [3. 자바에서 큐 사용]