EXCELSIOR

1. 단순 선택법 개념 이해하기단순 선택법은 졍렬되어 있지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해 나가는 알고리즘으로써 '선택 정렬(Selection sort)' 라고도 한다. 예를 들어 아래의 표 처럼 5개의 배열(array)에 [12, 13, 11, 14, 10]이 있다고 해보자. 위의 배열을 선택 정렬 알고리즘을 이용하여 오름차순으로 정렬해보자. 선택 정렬 알고리즘은 먼저, 가장 작은 숫자를 찾는다. 그런 다음 가장 작은 숫자를 첫 번째 index의 공과 위치를 바꿔 준다. 위의 두 가지 동작을 반복하면서 모든 숫자가 정렬될 때까지 반복하는 알고리즘이다. 다음 그림을 통해 선택 정렬 알고리즘을 알아보도록 하자. 위의 그림 처럼 해당 단계마다 가장 작은 숫자를 찾아 정..

1. 해시 탐색법 개념 이해하기앞에서 배운 선형 탐색법이나 이진 탐색법의 전제 조건은 어떤 데이터가 어느 index에 들어 있는지 전혀 모르는 상태에서 검색을 시작한다는 것이었다. 하지만, 이번에 배울 해시 탐색법 은 데이터의 '내용' 과 저장한 곳의 'index' 를 미리 연결해 줌으로써 짧은 시간에 탐색할 수 있도록 고안된 알고리즘 이다. 해시 탐색법은 '데이터를 데이터와 같은 index에 넣어 두면 한 번에 찾을 수 있지 않을까?' 라는 생각에서 시작된다. 예를 들어, ​ 인 데이터는 index ​ 에 넣어 두고, ​ 은 index ​ 에 넣어두는 방법이다. 이러한 방법은 원하는 데이터를 확실히 쉽게 찾을 수 있지만, 위의 예시 처럼 ​ 의 데이터를 보관하기 위해서는 최소한 index가 ​ 까지인 ..

1. 이진 탐색법 개념 이해하기이진 탐색법은 탐색의 대상인 데이터가 미리 오름차순 또는 내림차순으로 정렬되어 있는 경우에 사용할 수 있는 알고리즘이다. 예를 들어, 7개의 칸으로 나누어진 상자(0 ~ 6이라고 적힌)가 있다고 하자. 그리고 이 상자 안에는 각각 숫자가 적힌 공이 하나씩 들어 있다. 단, 이 상자에 들어 있는 공은 오름차순으로 정렬되어 들어 있다. 이를 표로 나타내면 다음과 같다.index0123456숫자가 적힌 공11131719232931이제 17 이라고 적힌 공 을 이진 탐색법으로 찾아보자. 이진 탐색법은 탐색하는 범위를 반으로 나누어 즉, 둘로 나누어 절반씩 좁혀 나가면서 탐색을 진행하는 알고리즘이다. 가운데에 있는 공의 숫자를 살펴본다.위의 표에서 가운데에 있는 공은 index가 3..

1. 선형 탐색법 개념 이해하기예를 들어 아래의 표와 같이 5개의 칸으로 나누어진 상자(0~4 라고 적힌)가 있고, 숫자가 적힌 공이 상자에 하나씩 들어있다고 해보자. 이 상자들 중 5라고 적힌 공 을 선형 탐색법을 이용하여 찾으려고 한다. 방법은 매우 간단하다! 왼쪽에서 부터 오른쪽( 상자 0 ​ 4 방향) 방향으로 순서대로 하나씩 확인해 가면 된다. index01234숫자가 적힌 공42351이렇듯 선형 탐색법은 매우 간단 하지만 단점이 있다. 만약 찾는 공이 앞쪽에 있으면 (위의 예시의 경우 4라고 적힌 공) 짧은 시간에 탐색할 수 있지만, 만약 찾고자 하는 공이 뒤에 있거나 없는 경우 탐색하는데 시간이 오래 걸리게 된다. 따라서, 선형 탐색법은 이해하기에는 쉬운 알고리즘이지만, 효율은 좋지 못하다...

1. 개념 Merge sort는 분할정복법을 사용하여 정렬하는 알고리즘이다.1) 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할2) 정복: 각각의 작은 문제를 순환적으로 해결3) 합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 2. Pseudocodemerge(A[ ], p, r){ ▷ A[p...r]을 정렬한다.if(p < r) then {q ← (p+q)/2; ---------------① ▷ p, q의 중간 지점 계산mergeSort(A, p, q); --------② ▷ 전반부 정렬mergeSort(A, q+1, r); --------③ ▷ 후반부 정렬merge(A, p, q, r); -----------④ ▷ 합병} } merge(A[ ], p, q, r..

1. Selection Sort1) 개념각 루프마다 - 최대의 원소르 찾는다. - 최대의 원소와 맨 오른쪽 원소를 교환한다. - 맨 오른쪽 원소를 제외한다. 하나의 원소만 남을 때 까지 위의 루프를 반복한다.[출처: 권오흠, 영리한 프로그래밍을 위한 알고리즘 강좌] 2) PseudocodeselectionSort(A[ ], n){ ▷배열 A[1...n]을 정렬한다.for last ← n downto 2 { -------------------------------①A[1...last] 중 가장 큰 수 A[k]를 찾는다 -----------------------②A[k] ↔ A[last] ▷ A[k]와 A[last]의 값을 교환 -------------------------③}} 3) 수행시간①의 for 루..

멱집합 주어진 집합의 모든 부분집합의 집합을 멱집합이라 한다. 예를 들어 집합 A = {a, b, c, d}일 때, 멱집합의 개수는 이다. 즉, n개의 원소에 대해 자신을 포함하는지 아닌지, 2가지 경우의 수가 있으므로 집합의 원소의 개수가 n개일 때 멱집합의 개수는 개이다. Recursion을 이용한 멱집합 구하기1) Recursion을 사용하여 멱집합을 구하는 방법은 다음과 같은 과정을 반복하면 된다. 예를 들어, {a, b, c, d, e, f}의 멱집합을 구하려면 a를 제외한 {b, c, d, e, f}의 멱집합을 나열하고, {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. {b, c, d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하려면 {c, d, e,..

1. N - Queens Problem ( 8 - Queens Problem )어떠한 행, 열, 대각선에 말이 겹치지 않도록 놓는 방법 1) 상태공간트리(State-Space Tree)상태공간트리란 찾는해를 포함하는 트리를 말한다. 즉 해가 존재한다면 그것은 반드시 이 트리의 어떠 한 노드에 해당한다.→ 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아니다. 2) 되추적 기법(Backtracking)상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다. [출처: https://ko.wikipedia.org] 2. Design Recursion1) 전체 pseudocode int [ ] cols = new int [N+1];return-type(boolean) queens( argum..