알고리즘 기초

1. 알고리즘이란?

알고리즘은 문제를 해결하기 위한 명확한 단계별 절차입니다. 코드를 작성하기 전에 먼저 "어떻게 풀 것인가"를 정리하는 것이 알고리즘입니다.

// 프로그램 = 자료구조 + 알고리즘
const numbers = [3, 1, 4, 1, 5];  // 자료구조 (배열)

// 알고리즘 (최댓값 찾기)
let max = numbers[0];
for (let i = 1; i < numbers.length; i++) {
    if (numbers[i] > max) {
        max = numbers[i];
    }
}

2. 알고리즘의 5가지 필수 조건

입력(Input) - 외부에서 데이터를 받을 수 있어야 함

function findMax(arr) {  // arr이 입력
    // ...
}

출력(Output) - 결과를 반환해야 함

function findMax(arr) {
    let max = arr[0];
    // ...
    return max;  // 출력
}

명확성(Definiteness) - 모호하지 않고 명확해야 함

// 나쁜 예: 무엇을 비교하는지 불명확
if (x > y) { /* ... */ }

// 좋은 예: 명확한 의도
if (currentValue > maxValue) {
    maxValue = currentValue;
}

유한성(Finiteness) - 반드시 종료되어야 함

// 나쁜 예: 무한 루프
while (true) {
    // 종료 조건 없음
}

// 좋은 예: 명확한 종료 조건
let i = 0;
while (i < arr.length) {
    // ...
    i++;
}

효과성(Effectiveness) - 실행 가능해야 함

// 모든 명령이 실제로 실행 가능해야 함
arr.forEach(item => console.log(item));  // ✓

3. 알고리즘 표현 방법

의사코드(Pseudo-code)

// 1부터 n까지 합 구하기
sum ← 0
for i ← 1 to n do
    sum ← sum + i
return sum

JavaScript 실제 코드

function sumToN(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

4. 시간 복잡도와 Big-O 표기법

시간 복잡도는 입력 크기에 따른 실행 시간의 증가율을 나타냅니다.

O(1) - 상수 시간

function getFirst(arr) {
    return arr[0];  // 배열 크기와 무관하게 항상 같은 시간
}

O(n) - 선형 시간

function findMax(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {  // n번 반복
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

O(n²) - 이차 시간

function printPairs(arr) {
    for (let i = 0; i < arr.length; i++) {      // n번
        for (let j = 0; j < arr.length; j++) {  // n번
            console.log(arr[i], arr[j]);
        }
    }
}

O(log n) - 로그 시간

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

5. 실전 예제

1부터 n까지 합 구하기 - 비교

// O(n) - 반복문 사용
function sumWithLoop(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

// O(1) - 수학 공식 사용
function sumWithFormula(n) {
    return (n * (n + 1)) / 2;
}

console.log(sumWithLoop(100));     // 5050
console.log(sumWithFormula(100));  // 5050

배열의 최댓값 찾기

function findMaxValue(arr) {
    if (arr.length === 0) return null;
    
    let max = arr[0];
    
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    return max;
}

const numbers = [3, 7, 2, 9, 1, 5];
console.log(findMaxValue(numbers));  // 9

구구단 출력 (이중 루프)

function printMultiplicationTable() {
    for (let i = 1; i <= 9; i++) {           // 외부 루프
        let row = '';
        for (let j = 1; j <= 9; j++) {       // 내부 루프
            row += `${i * j}\t`;
        }
        console.log(row);
    }
}

삼각형 패턴 출력

function printTriangle(n) {
    for (let i = 1; i <= n; i++) {
        let stars = '';
        for (let j = 1; j <= i; j++) {
            stars += '*';
        }
        console.log(stars);
    }
}

printTriangle(5);
// *
// **
// ***
// ****
// *****

6. 성능 최적화 팁

불필요한 계산 제거

// 나쁜 예
for (let i = 0; i < arr.length; i++) {  // 매번 length 계산
    // ...
}

// 좋은 예
const len = arr.length;
for (let i = 0; i < len; i++) {
    // ...
}

조기 종료

function hasElement(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return true;  // 찾으면 즉시 종료
        }
    }
    return false;
}

적절한 자료구조 선택

// 중복 검사 - Set 사용 O(1)
const uniqueSet = new Set(arr);
if (uniqueSet.has(value)) { /* ... */ }

// 빈도수 계산 - Map 사용 O(1)
const frequency = new Map();
arr.forEach(item => {
    frequency.set(item, (frequency.get(item) || 0) + 1);
});

7. 시간 복잡도 분석 실습

// 예제: 배열에서 중복 찾기
function hasDuplicate(arr) {
    // 방법 1: 이중 루프 - O(n²)
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] === arr[j]) return true;
        }
    }
    return false;
}

// 방법 2: Set 사용 - O(n)
function hasDuplicateOptimized(arr) {
    const seen = new Set();
    for (const item of arr) {
        if (seen.has(item)) return true;
        seen.add(item);
    }
    return false;
}

정리

1. 알고리즘 = 문제 해결 절차 - 코드 작성 전 논리적 순서 정리
2. 시간 복잡도 - 입력 크기에 따른 실행 시간 증가율
3. Big-O 표기법 - 최악의 경우를 가정한 성능 측정
4. 효율성 - 같은 결과를 내는 여러 알고리즘 중 더 빠른 것 선택
5. 가독성과 성능의 균형 - 과도한 최적화보다 명확한 코드 우선