Kwin's Development Diary.

색인 순차 검색(Index Sequential Search) - 정렬되어 있는 자료에 대한 *인덱스 테이블(Index Table)을 추가로 사용하여 탐색 효율을 높인 검색 방법 * 인덱스 테이블 : 배열에 정렬되어 있는 자료 중 일정한 간격으로 떨어져 있는 원소들을 저장한 테이블 ㄴ 자료가 저장되어 있는 배열의 크기가 n이고 인텍스 테이블의 크기가 m일 때, 배열에서 n/m간격으로 떨어져 있는 원소와 그의 인덱스를 인덱스 테이블에 저장 검색 방법 - indexTable[i].key ≤ key ≤ indexTable [i+1].key를 만족하는 i를 찾아 배열의 어느 범위에 있는지 알아낸 후 해당 범위에 대해서만 순차 검색 수행 Ex) 리스트 = {1, 3, 10, 23, 29, 33, 45, 50} 1 ..

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 ..

문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력..

문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 ..

문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm짜리 랜선에서 140cm짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 ..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 문..

Kruskal 알고리즘 : 최소 비용 신장 부분 트리를 찾는 알고리즘 최소 비용 신장 트리(MST, Minimum Cost Spanning Tree)의 의미를 모른다면 다음 게시물을 참고하길 바란다. [자료구조] 최소 비용 신장 트리 (Minimum Cost Spanning Tree) [자료구조] 신장 트리 (Spanning Tree : ST) 와 최소 비용 신장 트리 (Minimum Cost Spanning Tree : MST) 신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) / 너비 우선 신장 트리(Bre.. kwin0825.tisto..

프림 알고리즘(Prim Algorithm) : 가중치가 있는 무향(방향X) 그래프의 최소 비용 신장 트리(MST)를 찾는 알고리즘 최소 비용 신장 트리(MST, Minimum Cost Spanning Tree)의 의미를 모른다면 다음 게시물을 참고하길 바란다. [자료구조] 최소 비용 신장 트리 (Minimum Cost Spanning Tree) [자료구조] 신장 트리 (Spanning Tree : ST) 와 최소 비용 신장 트리 (Minimum Cost Spanning Tree : MST) 신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) ..

신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) / 너비 우선 신장 트리(Breadth First Spanning Tree) 최소 비용 신장 트리(Minimum Cost Spanning Tree : MST) - 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 - 최소 비용 신장 트리를 만드는 알고리즘 ㄴ Kruskal 알고리즘 [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) - JAVA / 자바 ㄴ Prime 알고리즘 [알고리즘] 프림 알고리즘(Prim Algorithm) - JAVA ..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 문제 접근 방법 이번 문제는 다이나믹 프로그래밍(Dynamic Programming)을 이용하여 쉽게 해결해 줄 수 있는 문제이다. 수를 1로 만드는 방법은 총 3가지가 있다. (-1, /2, /3) 따라서 다이내믹 프로그래밍에 사용할 1차원 배열을 입력으로 들어올 수만큼 ..