이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 시간복잡도 O(log N) 만에 찾아내는 탐색하는 방법입니다.오름차순으로 정렬된 사이즈가 N인 배열 D에서 원하는 값 k(k = 11)를 찾는 방법은 다음과 같습니다.먼저 탐색할 데이터의 범위를 두 개의 인덱스(왼쪽, 오른쪽)로 지정하고 이를 L, R이라고 하겠습니다. 정렬되어있기 때문에 D[L]은 최솟값, D[R]은 최대값이 됩니다.L M R01234567-3014791116당연히 처음 탐색 시에는 전체영역이므로 L = 0, R = N - 1 입니다. 이중 중앙값(Median)을 찾아 찾으려는 값 k와 비교합니다. 중앙값 M은 (L+R)/2 로 구할 수 있습니다.중앙값인 D[M]과 K를 비교하였을 시, K가 더 크므로 [0, M]..
알고리즘
에라토스테네스의 체는 특정 범위의 수들이 소수(Prime)인지 아닌지를 판별하는 알고리즘입니다. 예를 들어 1부터 50까지 수 중에서 소수를 구하고자 한다면 다음과 같은 배열이 필요합니다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950먼저 가장 작은 소수인 2부터 시작합니다. 그리고 2의 배수에 해당하는 수들은 모두 소수가 아닙니다. 따라서 범위 안의 2의 배수들을 소수가 아니라고 체크해줍니다.(일반적으로 boolean타입이나 int형 변수를 만들어주어 체크) 아래에서 색이 칠해진 수는 소수가 아님을 나타냅니다.12345678910111213141516171819202122232425262..
거품정렬(Bubble Sort)은 인접한 원소들의 대소관계를 비교하여 일정한 대소관계를 만족하지 않을 시, 인접한 원소를 교환하는 방법으로 진행되는 정렬입니다. 다음은 버블 정렬을 쉽게 시각화 한 내용입니다.더보기버블 정렬을 쉽게 도식화 한 그림과 설명을 보면 한번 위치 교환을 통해 가장 큰 원소가 마지막으로 가는 것을 확인할 수 있습니다. 이를 통해 마지막 원소가 정렬되었다고 볼 수 있고, 이를 N-1번 반복한다면 버블 정렬이 끝납니다.N개의 원소가 있다면, N-1번의 교환을 통해 정렬할 수 있습니다. 이를 시간 복잡도로 나타내면 (정렬해야 할 원소의 개수 - 1) *(최대 교환 수) 이므로 O(N²)이 됩니다.힙 정렬, 퀵 정렬과 같은 정렬보다 비효율적이므로 자주 쓰지 않습니다.다음은 C++로 나타낸..
삽입정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 원소를 순차적으로 탐색하면서 해당 원소를 정렬이 된 부분에 끼워 넣는 정렬입니다.맨 처음 원소(1)를 정렬되었다고 가정한 후, 정렬되지 않은 다음 원소(2)를 정해 최근에 정한 원소(1)와 비교한 후 크다면 (1)의 오른쪽에 그렇지 않다면 그 자리에 그대로 정렬합니다.시간복잡도는 각 원소에 대해 적당한 위치를 찾아주어야 하므로 총 원소의 개수 O( N ), 순차적으로 삽입 위치를 찾는데 O( N )이 들므로 O(N²)으로 힙정렬이나 합병정렬에 비해 비효율적(O(N log N))으로 잘 쓰이지 않습니다.다음은 C++로 나타낸 코드입니다.더보기#include #define MAX 5005using namespace std;int d[MAX],..
선택 정렬은 매 차례마다 정렬되지 않은 원소들을 모두 확인하여 각 인덱스에 맞는 원소를 선택하여 해당 인덱스의 원소와 교환해주는 정렬입니다. 매 차례마다 남은 원소들을 모두 확인하기 때문에 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2)입니다.그림을 통해 각 순서에 대해 설명하도록 하겠습니다. 먼저 가장 작은 값을 첫 번째 값인 15로 지정하고, minimum index를 0으로 놓습니다.그 수의 뒤에 있는 모든 수와 비교하면서, minimum index에 있는 수보다 작은 수일 경우 minimum index를 해당 수의 인덱스로 바꿔줍니다.연산이 끝나면 마지막 수인 1이 minimum index가 되고 해당 수와 처음 인덱스를 바꿔줍니다.첫 번째 수는 제대로 정렬된 수이..
