전체 글

Prim 알고리즘

프림 알고리즘(Prim's Algorithm)이란? 최소 신장 트리(Minimum Spanning Tree) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다. 프림 알고리즘의 동작 프림 알고리즘은 매 순간 최선의 조건을 선택하는 그리디 알고리즘을 바탕에 둔다. 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택한다. 시작 단계는 시작 노드만이 MST 집합에 속한다. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 MST 트리 집합에 넣는다. (사이클을 막기 위해 연결된 정점이 이미 트리가 속한다면 그 다음 순서를 넣는다.) 2번 과정을 MST 집합의 원소 개수..

[백준 / Java] 17144번 : 미세먼지 안녕!

문제 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. 인접..

[백준 / Java] 11053번 : 가장 긴 증가하는 부분 수열

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1 복사 6 10 20 10 30 20 50 예제 출력 1 복사 4 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가..

[백준 / Java] 1991번 : 트리 순회

문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로..

[백준 / Java] 5639번 : 이진 검색 트리

문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다. 이진 검색 트리를 전위 순회한 결과가 ..

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리의 필요성 탐색은 프로그램에서 가장 시간이 많이 걸리는 연산 중 하나이기에 효율적인 탐색을 구현하는 것은 굉장히 중요하다. 앞서 살펴본 스택, 큐, 배열, 리스트 구조는 모두 선형적인 구조를 갖고 있다. 선형적인 구조는 탐색 연산시 일일이 순차적으로 접근하여 데이터를 찾는 방식으로 탐색을 진행해야 하기에 탐색에 비효율적이다. 다음과 같이 배열과 연결리스트 모두 앞에서부터 순차적으로 탐색해야 값을 찾을 수 있고 최악의 경우 해당 값이 맨 마지막에 있다면 O(n)의 시간복잡도를 갖는다. 이러한 선형적인 구조의 탐색 비효율성은 데이터의 크기가 증가할수록 선형적으로 증가한다. 이러한 선형구조가 갖는 탐색의 비효율성을 개선한 것이 바로 이진 탐색 트리(Binary Search Tree)이다. 배열을..