코린이의 소소한 공부노트

1. Problem - 크루스칼 알고리즘을 사용하여 모든 노드를 연결하는 최소 비용을 구해보자. - 최소 비용 신장 트리(minimum cost spanning tree)를 만드는 대표적인 알고리즘이다. - 각 노드를 연결하는 간선의 정보(연결된 노드, 비용)를 이용해 간선을 정렬한 후 사이클을 만들지 않게 적은 비용의 간선부터 차례대로 선택해 나간다. - 최소한의 비용으로 모든 노드를 이어야 하기 때문에, 사이클을 만드는 것은 비용 낭비가 된다. - 간선을 선택하기 전에 사이클 테이블을 확인해야 하는데, 이는 이미 연결된 노드인지 알아보기 위함이다. 사이클 테이블은 union-find(합집합 찾기) 알고리즘을 이용한다. 2. Input 1) int[][] graph - 연결된 노드를 표현 2) int[..

1. Problem - 여러 개의 노드 중 2개를 선택했을 때, 두 노드가 같은 그래프에 있는지 알아보자. - 합집합 찾기(union find) 알고리즘은 i번 노드에 대한 부모 노드의 값을 arr[i]에 저장해서 m번 노드와 n번 노드의 부모가 같다면 같은 그래프에 있다고 판단하는 알고리즘이다. - 한 그래프의 노드들을 연결할 때 부모 노드가 여러개가 생긴다면 더 작은 값으로 저장한다. 이 과정을 합침(union) 과정이라 한다. - 합침 과정에서 최종 부모를 찾기 위해 재귀적으로 메서드를 호출하게 된다. - 찾기(find) 과정에서는 두 노드의 부모를 찾아 같은지 확인한다. 2. Input 1) int[][] graph - 연결된 노드를 표현 2) int a, b 3. Output 1) a, b가 같..

1. Problem - root에 대하여 깊이 우선 탐색을 실행해보자. - 깊이 우선 탐색은 너비보다 깊이를 우선적으로 탐색하는 알고리즘이다. - 탐색 결과는 root에서 최하단까지 갔다가 다시 root에서 다른 최하단까지 가는 형식으로 나온다. - 주로 스택으로 구현한다. 2. Input 1) int[][] graph - 노드 간의 연결성 표현 2) int root - root 노드의 값 3. Output 1) root에 대하여 깊이 우선 탐색을 실행한 결과 4. Example // 예시: 위 그래프가 주어졌을 때, 1부터 차례대로 방문한다. // 한 번 방문한 노드는 다시 방문하지 않는다. liststack // 첫 번째로, 1을 방문한다. [1][] // 1과 연결 되어 있는 노드 중 방문하지 않은..

1. Problem - root에 대하여 너비 우선 탐색을 실행해보자. - 너비 우선 탐색은 깊이보다 너비(같은 레벨의 노드)를 우선적으로 탐색하는 알고리즘이다. - 탐색 결과는 root에서 가까운 것부터 나오게 된다. - 최단 경로를 보장해야 할 때 사용한다. - 주로 큐로 구현한다. 2. Input 1) int[][] graph - 노드 간의 연결성 표현 2) int root - root 노드의 값 3. Output 1) root에 대하여 너비 우선 탐색을 실행한 결과 4. Example // 예시: 위 그래프가 주어졌을 때, 1부터 차례대로 방문한다. // 한 번 방문한 노드는 다시 방문하지 않는다. listqueue // 첫 번째로, 1을 방문한다. [1][] // 1과 연결 되어 있는 노드 중 ..

1. Problem - 배열의 요소를 오름차순으로 정렬해보자. - 정렬할 데이터의 범위를 알고 있다면 데이터의 개수를 세어서 정렬할 수 있다. 2. Input 1) int[] arr 3. Output 1) arr를 오름차순으로 정렬한 결과 4. Example // 예시: 5 5 4 4 3 3 3 2 2 1 // 배열의 앞에서부터 읽어가며 카운팅을 한다. // 5 -> count[5]++; // 5 -> count[5]++; // 4 -> count[4]++; // ... // 1 -> count[1]++; // count = [0, 1, 2, 3, 2, 2] // 이것을 바탕으로 정렬된 결과를 출력하면 // 1 2 2 3 3 3 4 4 5 5 5. Code int[] arr = {1,2,3,4,5,5,4..

1. Problem - 힙을 이용해 배열의 값을 오름차순으로 정렬해보자. // 완전 이진 트리(complete binary tree): 자식 노드가 왼쪽부터 채워지는 이진 트리. 같은 레벨의 중간 부분이 비어있지 않다. // 힙: 최댓값/최솟값을 빠르게 찾기 위해 완전 이진 트리를 기반으로 만들어진 트리 // 최대 힙: 부모 노드가 자식 노드보다 큰 값을 갖는 힙 // 힙 생성(heapify) 알고리즘: 특정 노드를 최대 힙에 넣는 알고리즘. 특정 노드의 두 자식 중 더 큰 자식과 자기 자신의 위치를 바꾸면서 자리를 찾아 간다. 2. Input 1) int[] heap 3. Output 1) heap을 오름차순으로 정렬한 결과 4. Example // 위쪽 그림에서의 최대 힙: 6 5 2 4 1 // 6..

1. Problem - n개의 정수가 담긴 배열을 오름차순으로 정렬해보자. - 삽입 정렬은 요소를 적절한 위치에 삽입하는 방법으로 정렬한다. - i번째의 요소를 정렬할 차례가 됐을 때, [0, i-1]까지는 정렬된 상태라고 가정한다. - 필요할 때만 요소의 위치를 바꾼다. 2. Input 1) int[] arr 3. Output 1) 오름차순으로 정렬된 배열을 반환 4. Example // 예시: 2 3 6 1 5 4 // 0번째: 삽일할 위치가 없다. -> (2) 3 6 1 5 4 // 1번째: 3은 2보다 크다. -> (2 3) 6 1 5 4 // 2번째: 6은 3보다 크다. -> (2 3 6) 1 5 4 // 3번째: 1은 2보다 작다. -> (1 2 3 6) 5 4 // 4번째: 5는 3보다 크고..

1. Problem - n개의 정수를 담은 배열을 오름차순으로 정렬해보자. - 버블 정렬은 바로 옆에 있는 두 요소 중 더 작은 요소를 앞으로 보내면서 정렬한다. - 맨 끝까지의 비교가 1번씩 일어날 때마다 가장 큰 요소가 맨 뒤로 간다. 2. Input 1) int[] arr 3. Output 1) 정렬된 배열을 반환 4. Example // 예시: {2 3 6 1 5 4} // 2는 바꾸지 않는다. -> {2 3 6 1 5 4} // 3은 바꾸지 않는다. -> {2 3 6 1 5 4} // 1과 6을 바꾼다. -> {2 3 (1 6) 5 4} // 6과 5를 바꾼다. -> {2 3 1 (5 6) 4} // 6과 4를 바꾼다. -> {2 3 1 5 (4 6)} -> {2 3 1 5 4} 6 // 다시 ..

1. Problem - n개의 정수가 담긴 배열을 오름차순으로 정렬해보자. - 선택 정렬은 가장 작은 요소를 찾아 자리를 바꾸면서 정렬한다. - 맨 끝까지의 비교가 1번씩 일어날 때마다 가장 작은 요소가 앞으로 간다. 2. Input 1) int[] arr 3. Output 1) 오름차순으로 정렬된 배열 4. Example // 예시: (2 3 6 1 5 4) // 가장 작은 수: 1 -> 1과 2를 바꾼다. -> 1 (3 6 2 5 4) // 가장 작은 수: 2 -> 2와 3을 바꾼다. -> 1 2 (3 6 5 4) // 가장 작은 수: 3 -> 바꾸지 않는다. -> 1 2 3 (6 5 4) // 가장 작은 수: 4 -> 4와 6을 바꾼다. -> 1 2 3 4 (5 6) // 가장 작은 수: 5 -> ..

1. Problem - n개의 2차원 행렬이 주어졌을 때, 곱셈 연산을 최소화하는 방법을 찾아보자, // 두 행렬의 곱셈 A*B을 수행할 때, A의 열의 개수와 B의 행의 개수가 같아야하기 때문에 교환 법칙은 성립하지 않지만, 결합 법칙은 성립한다. // 예를 들어, 2*3 행렬과 3*4 행렬을 곱해서 2*4 행렬을 얻을 때, 총 8개의 항이 나오고, 각 항마다 필요한 곱셈 연산의 수는 3개이므로 2 * 4 * 3 = 24번의 곱셈 연산이 필요하다. 2. Input 1) 곱해야 하는 행렬의 개수 n - 여기서는 예시로 주어진 6개의 행렬을 곱하고자 한다. 2) 행렬의 크기를 담은 int배열 d (0-indexed) - i번째 행렬의 크기 == d[i-1] * d[i] 3. Output 1) 최소 곱셈 연..