정렬이 이미 되어 있다는 것을 가정하고 이를 통해서 [start, mid, end] 3포인트를 지정한다. mid는 배열의 크기를 2로 나누었을때 소수점을 버린 값이다. (10 = 5, 9 = 4) {start: 0, mid: 8, end: 20}
이진탐색의 방식은 결과적으로 mid가 탐색값이 되면 탐색을 멈추고 mid를 반환하는 방식이다. 탐색값과 mid를 비교해서 탐색값이 더 크다면 start = mid를 해주어 탐색 범위를 좁히고 변경된 start를 기준으로 mid = parseInt((start + end) / 2) 를 작성해서 mid위치를 재지정해준다. 반대로 탐색값이 더 작다면 end = mid, mid = parseInt((start + end) / 2)를 작성하여 end위치와 mid위치를 재지정해주면 된다.
마치며...
이진 탐색코드 같은 경우엔 코딩테스트에서도 분명 이점이 있지만 프로젝트를 진행할 때 특정 값을 정렬된 데이터들 내에서 탐색하는 방법을 사용할때 많이 이용하게 될 것 같다.
예를 들어 640원을 거슬러 주어야한다고 하고 220원, 200원, 10원 동전이 있다고 가정하면
220원 2개, 200원 1개로 총 3개가 필요할 것이다. 이 또한 배수관계에 속하기 때문에
가장 큰 수의 동전부터 나눌 수 있는 만큼 나누고 점차 작은 수의 동전으로 나누어주는
같은 방식의 탐욕알고리즘을 사용하여 문제를 해결할 수 있다.
마치며...
탐욕알고리즘에 대해서는 간단하게 포스팅을 해보았다. 실질적으로 탐욕알고리즘은 코딩테스트를 볼 때 중요했던 개념이었다. 나는 탐욕알고리즘을 파악할때 예시로 주어지는 입력값과 출력값(정답)을 보며 연관성을 최대한 찾아보고 답을 만들기 위한 코드설계와의 연관성과 규칙성이 있는지를 확인하면서 코드를 작성할때 어떠한 연관성이 있는지를 파악하면서 실마리를 찾아냈던 것 같다. 개인적으로 익숙해지기 어려운 접근방식이었던 기억이 있다...
앞으로 보내진 원소는 위치가 변경되지 않고 시간복잡도 O(N²)으로 비효율적인 알고리즘에 속한다.
동작방식
1. 단계별로 수행하면서가장 작은 원소를 선택한다.
2. 처리되지 않은 원소중에 가장 앞의 원소와 교체한다.
선택정렬 함수 예시
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 스왑(swap)
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
2. 버블정렬(Bubble Sort)
인접한 두 원소를 체크하여 정렬이 안되어 있다면 위치를 서로 변경하는 정렬방식이다.
서로 인접한 두 원소를 비교하는 것이 마치 거품과 같다고 하여 붙여진 이름이다.
시간복잡도 O(N²)으로 비효율적인 정렬 알고리즘에 속한다.
동작방식
1. 단계별로 수행하면서 가장 큰 원소가 맨 뒤로 이동한다.
2. 다음단계에선 맨 뒤로 이동한 원소는 정렬에서 제외한다.
버블정렬 함수 예시
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
3. 삽입정렬(Insertion Sort)
각 원소를 적절한 위치에 삽입하는 정렬이다.
동작방식
1.단계별로 수행하면서현재 원소가 삽입될 위치를 탐색한다.
2.지정 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.
삽입정렬 함수 예시
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j > 0; j--) {
// 시작인덱스부터 1까지 1씩 감소하며 반복
if (arr[j] < arr[j - 1]) {
let temp = arr[j];
arr[j] = arr[j - 1]; // 한 칸씩 왼쪽으로 이동
arr[j - 1] = temp; // 스왑(swap)
} else {
break; // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
}
}
}
}
4. 병합정렬(Merge Sort)
병합정렬은 분할정복(divide and conquer) 알고리즘이다.
분할정복이란?
분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할한다.
정복(conquer): 작은 부분 문제를 각각해결하도록 한다.
조합(combine): 해결한 작은 부분의 답을 이용하여 큰 문제를 해결해나간다.
일반적으로 재귀함수를 사용하여 구현한다.
큰 문제를 작은 문제로 분할하는 방식이 같은 경우가 많기 때문이다.
그렇기 때문에 쪼개질 수 없는 크기가 될 때까지 계속해서 분할한다.
장점: 최악의 경우에도 O(N log N)을 보장할 수 있다는 점에서 효율적이다.
단점: 전반적으로 정복과정에서 임시배열이 필요한 경우가 지배적이다.
동작방식
1.단계별로 수행하면서현재 원소가 삽입될 위치를 탐색한다.
2.지정위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.
병합정렬 함수 예시
function merge(left, right) {
let sorted = [];
while (left.length && right.length) {
if (left[0] <= right[0]) sorted.push(left.shift());
else sorted.push(right.shift());
}
return [...sorted, ...left, ...right];
}
function mergeSort(arr) {
if (arr.length === 1) return arr;
let half = Math.ceil(arr.length / 2);
let left = arr.slice(0, half);
let right = arr.slice(half);
return merge(mergeSort(left), mergeSort(right));
}
let arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4, 5, 6, 7]
function merge: 이미정렬된 배열 left와 right를 하나의 함수로 합쳐주는 순수 함수
function mergeSort: 배열을 반으로 나누어 merge함수에게 left와 right로 전달한다.
마치며...
오늘 포스팅한 정렬알고리즘은 사실, 알고리즘을 따로 공부를하기전까진 단순하게 정렬하는거지! 라고 생각했지만 정말 다양하고 어떤방식으로 정렬을 하느냐에 따라 시간복잡도가 제곱이상의 차이가 나기도 한다는 것이 새롭게 다가왔던 것 같다. 앞으로도 코드의 퀄리티를 위해서 프로젝트에서 정렬할때 잘 생각해보고 적용시켜야겠다.
공식화한 형태로 표현한 것을 의미하며 유한성을 가지고 언젠가는 끝나야 하는 속성을 가지고 있다.
알고리즘의 조건
알고리즘은 아래 5가지 조건에 만족해야 한다.
입력: 외부에서 제공되는 자료가 0개 이상 존재해야 한다.
출력: 적어도 2개 이상의 서로 다른 결과를 도출해내야 한다.
명확성: 수행과정은 무엇을 하기위한 것인지 정의가 명확해야 한다.
유한성: 알고리즘의 명령어대로 수행하여 처리가 되었을때 종료되어야 한다.
효율성: 모든 과정이 명백히 실행가능해야 하며 시간적, 공간적 효율성을 가져야 한다.
1. 선형 자료구조
하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이다. 데이터가 일렬로 연속적으로(순차적) 연결되어있다. 배열, 연결리스트, 스택, 큐, 덱 등이 있다.
2. 비선형 자료구조
하나의 데이터뒤에 다른 데이터가 여러개 올 수 있는 자료구조이다. 데이터가 일직선상으로 연결되어있지 않아도 되며 트리, 그래프 같은 것이 있다.
자료구조와 알고리즘의 관계
효율적인 자료구조 설계를 위해 알고리즘 지식이 요구된다. 효율적인 알고리즘을 작성하기 위해서는 문제상황에 맞는 적절한 자료구조가 사용되어야 하며 프로그램을 작성할 때 자료구조와 알고리즘 모두 고려해야 한다.
프로그램의 성능 측정 방법
시간복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정한다.
공간복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정한다.
주로 공간을 많이 사용하는 대신 시간을 단축하는 방법을 선택한다.
Big-O 표기법
복잡도를 표현할 때는 Big-O 표기법을 사용한다.
특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있으며 가장 빠르게 증가하는
항만을 고려하는 표기법이다.
다음 알고리즘은 O(n)의 시간 복잡도를 가진다.
let n =10;
let sum = 0;
for (let i = 0; i < n; i++) {
sum += i;
}
console.log(sum); // 45
다음의 알고리즘은 O(n²)의 시간 복잡도를 가진다.
let n = 9;
for(let i = 1; i <= n; i++) {
for(let j = 1; j <= n; j++) {
console.log(`${i} X ${j} = ${i * j}`);
}
}
/*
실행결과:
1 X 1 = 1
1 X 2 = 2
...
9X 8 = 72
9 X 9 = 81
*/
연산횟수에 대한 소요시간
일반적으로 연산횟수가 10억을 넘어가면 1초이상의 시간이 소요된다. [예시] n = 1000
O(log n) : 약 10번 연산
O(n) : 약 1,000번 연산
O(n log n) : 약 10,000번 연산
O(n²) : 약 1,000,000번 연산
O(n³) : 약 1,000,000,000번 연산
Big-O표기법으로 시간 복잡도를 표기할 때는 가장 큰 항만을 표시한다. 가장 큰 항에 붙어 있는 계수는 제거한다. O(3n² + n) = O(n²)
Big-O 표기법을 사용한 시간복잡도의 예시
O(1) : 스택에서 Push, Pop
O(log n) : 이진트리
O(n) : for 문
O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬
O(n²): 이중 for 문, 삽입정렬, 거품정렬, 선택정렬
O(2ⁿ) : 피보나치 수열
마치며...
마무리 글에 갑자기 알고리즘에 대해서 공부를 하게 된 이유에 대해 적을까 한다. 메모서비스 개발을 진행하고 있다가 마무리되어 갈 즈음에 문득 스스로 문제해결능력에 대한 불만와 방식에 대해서 의구심을 품게 되었다. "과연 지금까지의 방식이 효율적이고 가장 빠른 길일까?" 그러다 알고리즘에 대해서 문득 떠올리게 되었고 하나씩 알아보게 되었는데 지금까지 나에게 느꼈던 부족함을 해결해 줄 수 있을 것이라 생각이 들었다. 그렇게 개발에 1개월의 공백을 두게 되었지만 다양한 알고리즘을 학습하고 코드를 직접 만들어보기도 하면서 지금까지 나에게 부족했던 부분들이 많이 채워지는 것을 느꼈다. 문제를 해결하기 위해 사고하는 방식이 달라졌고 시간복잡도에 대한 개념이 생기니 효율적으로 문제해결에 다가설 수 있게 된 것 같았다. 완벽하다고 할 수 없겠지만 나에게 있어 개발자로서 필요한 역량을 향상시키기 위한 없어선 안될 1개월이었던 것 같다.
