[멀티캠퍼스] 풀스택 개발자 아카데미 (12) - Algorithm(1)

0. 알고리즘

우리가 매일 사용하는 스마트폰 앱부터 복잡한 인공지능 시스템까지, 현대 기술의 중심에는 바로 알고리즘(Algorithm) 이 있다.

컴퓨터는 스스로 생각하지 못하기 때문에, 우리는 알고리즘을 통해 컴퓨터에게 무엇을, 어떻게 해야 할지 명확하게 지시해야한다.

1. 논리 세우기

알고리즘은 단순히 공식을 암기하는 것이 아닌, 주어진 문제의 조건을 명확히 이해하고, 논리적으로 추론하여 해결 절차를 만들어내는 과정이다.

다음 문제에 대해 생각해보자

• 규칙: 모든 카드의 한쪽 면에는 알파벳이, 다른 쪽 면에는 숫자가 있다.
• 주장: "카드의 한 면이 D이면, 반드시 반대 면은 3이다."

이 주장이 '참'인지 '거짓'인지 검증하기위해 꼭 뒤집어봐야 하는 카드는 무엇인가?

정답은 'D'와 '7'이다.

• 'D'를 뒤집는 이유: 뒷면이 '3'이 아니라면 주장은 즉시 거짓이 된다.
• '7'을 뒤집는 이유: 만약 뒷면이 'D'이면, "D이면 3이다"라는 주장에 대한 명백한 반례가 된다.

이와 비슷한 논리로, "20세 이하는 맥주를 마실 수 없다"는 규칙을 확인하려면 '19세' 가 무엇을 마시는지와 '맥주' 를 마시는 사람의 나이를 확인해야 한다. 이처럼 알고리즘적 사고는 문제의 모든 조건을 빠짐없이 고려하고, 반례를 찾아내려는 논리에서 시작된다.

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

똑같은 기능을 하는 코드라고, 입력 데이터의 양이 늘어남에 따라 실행 속도는 달라질 수 있다. 시간 복잡도는 이러한 입력 데이터의 크기(n)와 알고리즘의 실행 시간 사이의 관계를 나타내며, 주로 Big-O 표기법을 사용해 표현한다.

• O(1) - 상수 시간: 입력 크기와 상관없이 항상 일정한 시간이 소요 (예: 배열의 i번째 요소 접근)
• O(log n) - 로그 시간: 데이터가 두 배로 늘어도 연산은 한 단계만 추가 (예: 이진 검색)
• O(n) - 선형 시간: 데이터 크기와 실행 시간이 정비례 (예: 배열 전체 순회)
• O(n log n): 선형 시간(O(n))보다는 조금 더 걸리지만, 제곱 시간(O(n²))보다는 훨씬 효율적인 복잡도. 대표적으로 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)과 같은 효율적인 정렬 알고리즘이 속한다.
• O(n²): 이중 반복문 구조에서 흔히 나타나며, 데이터가 커지면 성능이 급격히 저하 (예: 버블 정렬)

3. 자료구조

알고리즘을 작성하기에 앞서, 이 재료가 되는 핵심인 자료구조를 간단히 알고 있어야 한다. 문제의 특성에 맞는 자료구조를 선택해야 효율적인 알고리즘을 작성할 수 있기 때문이다.

3.1. Stack: LIFO

Stack은 데이터가 한쪽 입구로만 들어오고 나갈 수 있는 LIFO(Last-In, First-Out; 후입선출) 구조를 가진다. 서랍 속에 옷을 차곡차곡 쌓고, 아래에 있는 옷을 꺼내려면 위에 쌓인 옷들을 먼저 꺼내야 하는 것과 같다.

• 동작 과정: '괄호 짝 맞추기' 문제는 스택의 대표적인 활용 사례입니다.

  1. 문자열을 순회하며 여는 괄호((, {, [)를 만나면 스택에 push
  2. 닫는 괄호(), }, ])를 만나면 스택의 맨 위(peek)를 확인
  3. 짝이 맞으면 스택에서 pop 하여 제거. 짝이 맞지 않거나 스택이 비어있으면 유효하지 않은 괄호로 처리
  4. 문자열 순회가 끝났을 때 스택이 비어있으면 모든 괄호의 짝이 올바르다고 판단

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

• 활용: 함수 호출 스택, 웹 브라우저의 '뒤로 가기' 기능, 실행 취소 등의 기능에서 활용해볼 수 있다.

3.2. Queue: FIFO

Queue는 데이터가 한쪽(Back)으로 들어와 반대쪽(Front)으로 나가는 FIFO(First-In, First-Out; 선입선출) 구조를 가진다. 쉽게 생각해서, 노래를 듣기 위해 플레이 리스트(큐)에 노래를 추가하는 것과 같다.

동작 과정: '카드 문제'는 큐의 동작을 잘 보여줍니다. N장의 카드를 1부터 순서대로 큐에 넣고(Enqueue), 맨 앞의 카드를 버리고(Dequeue), 그다음 카드는 빼서(Dequeue) 다시 맨 뒤에 넣는(Enqueue) 과정을 반복합니다.

import java.util.Queue;
import java.util.LinkedList;

class CardGame {
    public int findLastCard(int N) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            queue.add(i); // Enqueue
        }

        while (queue.size() > 1) {
            queue.poll(); // Dequeue: 제일 위 카드 버리기
            queue.add(queue.poll()); // Dequeue then Enqueue: 다음 카드 뒤로 옮기기
        }
        return queue.poll(); // 마지막 남은 카드 반환
    }
}

• 활용: 너비 우선 탐색(BFS), 프린터의 인쇄 작업 대기열, 메시지 큐 시스템 등 순서가 중요한 작업을 처리하는 경우 활용할 수 있다.

3.3. Hash Table

Hash Table은 Key-Value 쌍으로 데이터를 저장하는 자료구조로, 평균적으로 O(1) 의 매우 빠른 속도로 데이터를 검색, 삽입, 삭제할 수 있다.

• 동작 과정: 내부적으로 해시 함수(Hash Function) 를 사용하여 Key를 배열의 인덱스(Hash 값)로 변환하고, 해당 인덱스에 Value를 저장한다.

  • 예를 들어, '문자열에서 가장 많이 반복되는 문자 찾기' 문제에서 각 문자를 Key로, 등장 횟수를 Value로 저장하면 매우 효율적으로 풀 수 있다.
• 해시 충돌 (Hash Collision): 가장 큰 난제는 서로 다른 Key가 같은 해시 값(인덱스)을 갖는 '해시 충돌'이 있다. 이를 해결하기 위해 Chaining(해당 인덱스에 연결 리스트를 만들어 데이터를 이어 붙이는 방식)이나 Open Addressing(다른 비어있는 인덱스를 찾아 저장하는 방식) 등의 기법이 사용된다.

import java.util.Map;
import java.util.HashMap;

class FrequencyFinder {
    public char findMostFrequentChar(String text) {
        Map<Character, Integer> freqMap = new HashMap<>();
        // 각 문자의 빈도를 계산하여 HashMap에 저장
        for (char c : text.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        char maxChar = ' ';
        int maxFreq = -1;
        // HashMap을 순회하며 가장 높은 빈도의 문자를 찾음
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            if (entry.getValue() > maxFreq) {
                maxFreq = entry.getValue();
                maxChar = entry.getKey();
            }
        }
        return maxChar;
    }
}

• 활용: 데이터베이스 인덱싱, 캐시 구현, 객체의 유일성 확인(HashSet) 등 빠른 조회가 필수적인 거의 모든 곳에 사용할 수 있다.

3.4. Linked List

Linked List는 배열과 같이 데이터를 순차적으로 저장하지만, 메모리상에 연속적으로 위치하지 않는다는 큰 차이점을 가진다. 각 데이터 조각(노드, Node)은 실제 데이터 값과 다음 노드를 가리키는 참조(포인터) 를 함께 가지고 있다. 이 참조가 마치 사슬처럼 다음 데이터를 연결해주는 역할을 한다.

• 삽입과 삭제 (O(1)): 연결 리스트의 가장 큰 장점은 데이터의 삽입과 삭제가 매우 빠르다는 것이다. 특정 위치에 데이터를 추가하거나 삭제할 때, 해당 위치의 앞뒤 노드가 가리키는 참조 값만 변경해주면 되기 때문이다. 배열처럼 데이터를 일일이 옮길 필요가 없으므로, 연산은 O(1)의 시간 복잡도를 가진다

• 검색 (O(n)): 반면, 특정 데이터를 찾기 위해서는 첫 번째 노드(Head)부터 시작해 참조를 따라가며 순차적으로 모든 노드를 확인해야 한다. 이는 O(n)의 시간 복잡도를 가져, 검색 성능은 배열에 비해 불리하다.

import java.util.LinkedList;
import java.util.List;

class LinkedListExample {
    public void run() {
        List<String> list = new LinkedList<>();
        // 데이터 추가
        list.add("Apple");
        list.add("Banana");
        // 특정 인덱스에 삽입. 해당 위치(1번 인덱스)까지 탐색이 필요하므로 O(n)
        list.add(1, "Cherry");

        System.out.println(list); // [Apple, Cherry, Banana]

        // 데이터 삭제. "Apple"을 찾기 위해 리스트를 순회해야 하므로 O(n)
        list.remove("Apple");
        System.out.println(list); // [Cherry, Banana]
    }
}

• 활용: 데이터의 추가와 삭제가 빈번하게 일어나는 경우, 저장할 데이터의 개수를 미리 예측하기 어려운 경우, 스택이나 큐와 같은 다른 자료구조를 구현하는 기본 구조로 사용될 수 있다.

4. 결론

이번 내용은 이후 다양한 알고리즘 패러다임을 이해하기 위한 기초 지식이다.

Stack, Queue, Hash Table, Linked List는 각기 다른 강점과 약점을 가진 '문제 해결 도구'들로, 문제를 마주했을 때 어떤 자료구조를 선택하는가에 따라 코드의 성능과 복잡성이 결정된다.

빠른 검색이 필요하다면 Hash Table, 데이터의 순서가 중요하다면 Queue를, 잦은 데이터 변경이 예상된다면 Linked List를 떠올릴 수 있어야 한다. 이와 같이 적재적소에 맞는 자료구조를 선택하는 능력이야말로 효율적인 알고리즘 설계의 첫걸음으로 볼 수 있다.