전체 글

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Array 배열에서 요소의 탐색(* Search), 삽입(* Insert), 삭제(* Delete)는 매우 중요한 이슈입니다. 이에 그 배열이 Packed 되었는지 Unpacked 인지, Sorted 되었는지 Unsorted 되었는지에 따라 SID 의 성능의 차이가 발생합니다. 이에 Packed 의 유무와 Sorted 의 유무에 따라 4 가지 경우의 Array 들을 따져보겠습니다. (* 편의를 위해 중복된 값은 허용하지 않는다고 가정합니다.) 1. Packed, Unsorted 아마도 가장 간단한 방법이 아닐까 싶습니다. index 0 1 2 3 4 5 6 value 5 2 3 8 11 1.1 Search 해당 배열이 정렬이 되어있지 않기 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2178 미로 찾기와 비슷한 input 이라서 "DFS BFS 를 활용하면 되지 않을까" 먼저 생각했습니다. 2178 번 문제와 비슷하게 시작하는 노드에서 부터 동 서 남 북으로 이동 가능한데, 한 번 방문한 곳은 더이상 방문하지 않는다. 0이 적혀있는 곳은 방문하지 않는다. 를 지켜가며 DFS 든 BFS 든 해서 노드의 개수를 구하는 방식으로 풀었습니다. 2178 번 문제와 달리 해당 문제에서는 ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 1. 재귀 이진 탐색 앞서 반복문을 통한 이진탐색을 보았는데 아래는 재귀를 통한 이진탐색입니다. // binary search with Recursion int binarySearch(int a[], int n, int target) { // Base if(n target) return binarySearch(a, m - 1, target); else return m + binarySearch(a + m + 1, n - m, target); ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 알고리즘의 완전성을 증명하는 것은 중요합니다. 완전성을 증명하는 방법에는 여러가지가 있습니다. 알고리즘의 단계별로 하나하나 들어가서 이해하고 완전성을 확인하는 방법도 있습니다. 하지만 이는 그리 좋은 방법은 아닙니다. 해당 글에서는 수학적 귀납법을 사용하겠습니다. 1. 수학적 귀납법 임의의 공리 P가 존재한다고 할 때, 수학적 귀납법의 기본형은 다음과 같습니다. P(0) 가 성립한다. (* Base) 임의의 n 에 대하여 만약 P(n) 이 성립한다면, P(n+1) 역시 성립한다. (* Step) 수학적 귀납법의 강한 형태도 존재합니다. P(0), P(1), P(2) ... P(n-1) 이 성립한다. P(n) 이 성립한다면, P(n+1) 역시 성립..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색의 경우 BFS 를 사용해야 한다는 것은 아는데... 어떻게 구현해야 할지 몰랐습니다. 우선 Node 클래스를 만들었습니다. 그리고 미로에 해당하는 행렬을 입력받아 maze 변수에 넣어줍니다. 처음 시작하는 노드(* 0,0) 를 생성하고 그 노드에 인접 리스트에 (0,0)에 대해 상, 하, 좌, 우에 1이 있고 방문한 적이 없다면 노드를 추가해주는 방식을 사용했습니다. (* 상, 하, 좌, 우로 움직였을 때 행렬의 in..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제를 보면 첫 번째 줄에 동전 종류의 개수와 맞춰야 하는 돈의 가치를 받을 수 있고, 두 번째 줄부터 N 개의 줄로 각 동전의 가치를 받을 수 있습니다. 이때 동전의 가치는 오름차순으로 주어집니다. 우선 동전의 개수가 가장 적으려면 맞춰야 하는 돈(* K) 에 대해 나눠서 얻을 수 있는 몫이 0보다는 크지만 다른 동전들에 비해 몫이..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이 문제를 풀기 전에 DFS 와 BFS 가 뭔지 몰랐기 때문에 이에 대해 검색먼저 했습니다. 0. 그래프 그래프는 간선과 노드로 이루어진 관계도라고 볼 수 있습니다. DFS 와 BFS 는 이 그래프에서 어떤 노드를 찾는 방법들입니다. 1. DFS DFS, 깊이 우선 탐색은 최대한 깊게 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하며 노드를 찾습니..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제를 보자 사람의 수가 주어지고 각 사람이 인출하는데 걸리는 시간을 다음 줄에 준다. 이때 사람의 순서를 잘 배치하여 각 사람이 돈을 인출하는데 걸리는 시간이 최소가 되는 시간을 계산하면 된다. 각 사람이 인출하는데에 걸리는 시간이 최소가 되려면 어떻게 해야할까? 문제에 주어진 예시를 보자 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 일 때 최소 시간이 소요되는 순서는 [2, 5, 1, 4, 3] 이..