icon

안동민 개발노트

1장: 알고리즘 사고와 복잡도

문제 해결에서 알고리즘과 자료구조의 역할

온라인 코딩 테스트를 풀다 보면, 처음에는 작은 입력에서 정답만 맞추면 충분해 보입니다. 하지만 입력이 커지는 순간 같은 정답 코드도 실행 시간이 크게 달라집니다. 이 차이를 가장 먼저 만드는 요소가 자료구조 선택입니다.

자료구조는 데이터를 담는 그릇이고, 알고리즘은 그 그릇을 다루는 절차입니다. 연락처를 종이 명단에서 찾는지, 이름순 색인에서 찾는지로 속도가 달라지는 상황을 떠올리면 됩니다. 이 글의 목표는 왜 이 구조를 골랐는지를 판단 이유와 함께 설명할 수 있게 만드는 것입니다.

핵심 개념 요약

자료구조와 알고리즘을 같이 보면 왜 이 코드가 느린지를 훨씬 빨리 찾을 수 있습니다. 아래 내용을 읽으면서 최근에 풀었던 문제 하나를 떠올리고, 어떤 연산이 가장 많았는지 옆에 적어 보세요.

자료구조는 데이터를 꺼내기 쉽게 정리해 두는 보관 방식입니다. 정확히 말하면, 자료구조는 저장 형태와 조회/삽입/삭제 비용을 함께 결정하는 모델입니다. 예를 들어 이름 목록을 배열로 두면 i번째 조회는 빠르지만 중간 삽입은 원소 이동 때문에 느려집니다.

알고리즘은 데이터를 어떤 순서로 처리할지 정한 작업 절차입니다. 입력을 받아 유한한 단계로 원하는 출력을 만드는 계산 규칙이라고 보면 됩니다. 같은 사용자 조회 문제라도 리스트 순회와 해시 조회는 거치는 단계 수가 달라 실행 시간이 달라집니다.

연산 비율은 조회/삽입/삭제 중 무엇이 자주 발생하는지 보여 주는 분포입니다. 구조 선택에서 연산 비율은 지배 연산을 기준으로 비용 모델을 고르는 핵심 입력값입니다. 조회가 95%, 삽입이 5%라면 삽입 최적화보다 조회가 빠른 구조를 우선 후보로 두는 편이 안전합니다.

자료구조 선택이 실무에서 중요한 이유

자료구조 결정을 뒤로 미루면 아래 문제가 자주 생깁니다.

  1. 정답은 맞지만 시간 제한을 넘김
  2. 요구사항이 바뀌었을 때 수정 비용이 급증함

예를 들어 중복 없는 사용자 조회가 중요 작업이면 리스트보다 해시 집합이 맞습니다.
반대로 정렬 순서 유지가 필수면 해시만으로는 부족하고 정렬 단계가 필요합니다.
지금 최근에 푼 문제 하나를 떠올려, 가장 자주 실행된 연산을 조회/삽입/삭제로 분류해 보세요. 우선 연산 모델을 맞추면 이후 알고리즘 선택이 쉬워집니다.

실패 입력부터 재현하는 검증 순서

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

아래 조건으로 자료구조 선택 과정을 단계별로 따라가 봅니다.

  • 요청 비율: 조회 90%, 삽입/삭제 10%
  • 정렬 출력 요구: 없음
  • 데이터 규모: 사용자 100만 명
  1. 조회가 대부분이므로 요청마다 선형 탐색이 필요한 리스트는 1차 제외합니다.
  2. 정렬 출력이 없으므로 해시 집합/해시 맵을 우선 후보로 둡니다.
  3. 최악 충돌 시 지연과 메모리 사용량을 점검한 뒤 최종 구조를 확정합니다.

단순 리스트 탐색

문제 의도: 조회 연산을 리스트 선형 탐색으로 구현했을 때의 기본 비용을 확인합니다.
입력 예시: users=["alice","bob","carol", ...], target="carol" / target="zoe"
출력 예시: true, false

아래 코드는 로그인 요청마다 리스트를 순회해 사용자를 찾습니다. push_back/add/append/push는 리스트 끝에 값 추가를 뜻합니다.

main.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool existsUserLinear(const vector<string>& users, const string& target) {
    for (const auto& name : users) {
        if (name == target) return true;
    }
    return false;
}

int main() {
    vector<string> users = {"alice", "bob", "carol", "dave"};
    cout << boolalpha << existsUserLinear(users, "carol") << "\n";
    cout << boolalpha << existsUserLinear(users, "zoe") << "\n";
    return 0;
}
Main.java
import java.util.List;

public class Main {
    static boolean existsUserLinear(List<String> users, String target) {
        for (String name : users) {
            if (name.equals(target)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        List<String> users = List.of("alice", "bob", "carol", "dave");
        System.out.println(existsUserLinear(users, "carol"));
        System.out.println(existsUserLinear(users, "zoe"));
    }
}
main.py
users = ["alice", "bob", "carol", "dave"]

def exists_user_linear(users, target):
    for name in users:
        if name == target:
            return True
    return False

print(exists_user_linear(users, "carol"))  # True
print(exists_user_linear(users, "zoe"))    # False
main.rs
fn exists_user_linear(users: &[&str], target: &str) -> bool {
    for &name in users {
        if name == target {
            return true;
        }
    }
    false
}

fn main() {
    let users = vec!["alice", "bob", "carol", "dave"];
    println!("{}", exists_user_linear(&users, "carol"));
    println!("{}", exists_user_linear(&users, "zoe"));
}

알고리즘 기초 결과 기초 조건 확인

이 방식은 데이터가 작을 때는 단순하고 읽기 쉽습니다.
하지만 요청마다 최대 N개를 비교하므로 사용자가 늘수록 느려집니다.
조회가 핵심인 시스템에서는 선형 탐색이 반복 병목이 됩니다.

  • 평균 시간복잡도: O(N)
  • 최악 시간복잡도: O(N)
  • 공간복잡도: O(N)

해시 집합 기반 조회

문제 의도: 같은 조회 문제를 해시 집합으로 바꿨을 때 탐색 비용 변화를 비교합니다.
입력 예시: user_set={"alice","bob","carol", ...}, target="carol" / target="zoe"
출력 예시: true, false

같은 기능을 집합으로 바꾸면 조회 비용을 크게 줄일 수 있습니다. contains/in은 그 값이 집합 안에 있는지 검사하는 메서드입니다.

main.cpp
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

bool existsUserHash(const unordered_set<string>& userSet, const string& target) {
    return userSet.find(target) != userSet.end();
}

int main() {
    unordered_set<string> userSet = {"alice", "bob", "carol", "dave"};
    cout << boolalpha << existsUserHash(userSet, "carol") << "\n";
    cout << boolalpha << existsUserHash(userSet, "zoe") << "\n";
    return 0;
}
Main.java
import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean existsUserHash(Set<String> userSet, String target) {
        return userSet.contains(target);
    }

    public static void main(String[] args) {
        Set<String> userSet = new HashSet<>();
        userSet.add("alice");
        userSet.add("bob");
        userSet.add("carol");
        userSet.add("dave");

        System.out.println(existsUserHash(userSet, "carol"));
        System.out.println(existsUserHash(userSet, "zoe"));
    }
}
main.py
user_set = {"alice", "bob", "carol", "dave"}

def exists_user_hash(target):
    return target in user_set

print(exists_user_hash("carol"))  # True
print(exists_user_hash("zoe"))    # False
main.rs
use std::collections::HashSet;

fn exists_user_hash(user_set: &HashSet<&str>, target: &str) -> bool {
    user_set.contains(target)
}

fn main() {
    let mut user_set: HashSet<&str> = HashSet::new();
    user_set.insert("alice");
    user_set.insert("bob");
    user_set.insert("carol");
    user_set.insert("dave");

    println!("{}", exists_user_hash(&user_set, "carol"));
    println!("{}", exists_user_hash(&user_set, "zoe"));
}

알고리즘 기초 결과 전개 흐름 추적

해시 기반 구조는 평균적으로 매우 빠른 조회를 제공합니다.
조회가 압도적으로 많은 시나리오라면 리스트보다 유리합니다.
다만 정렬 순서가 필요한 요구사항에서는 별도 정렬 단계가 필요합니다.

  • 평균 시간복잡도: O(1)
  • 최악 시간복잡도: O(N) (충돌 집중 시)
  • 공간복잡도: O(N)

조회/삽입 비율별 판정 축

문제를 받으면 아래 순서로 판단하면 실패 확률이 낮아집니다.

  • 1단계: 핵심 연산이 조회/삽입/삭제/정렬 중 무엇인지 확인
  • 2단계: 연산 비율을 추정해 가장 자주 일어나는 비용을 최소화
  • 3단계: 최악 입력에서도 허용 가능한지 복잡도 상한 확인
  • 4단계: 요구사항 변경 시 구조를 확장할 수 있는지 점검

이 순서를 우선 잡고 코드를 쓰면, 중간에 갈아엎는 비용이 줄어듭니다.

해시 셋 도입 시 구현 비용 상충

자료구조 변경은 항상 장점만 있는 것이 아닙니다.

  • 해시 맵: 조회는 빠르지만 정렬 출력이 바로 되지 않음
  • 배열: 메모리 연속성이 좋아 캐시 친화적이지만 중간 삽입이 느림
  • 트리: 범위 질의가 강하지만 구현과 디버깅 난이도가 높음

평균 속도만 보는 대신, 필요한 기능과 디버깅 난이도까지 함께 비교해야 합니다.

로그 단서로 좁혀가는 실수 포인트

다음 상황에서는 구조 선택이 잘못되기 쉽습니다.

  • 데이터는 작지만 정렬 출력이 자주 필요한데 무조건 해시만 사용
  • 중복 허용 요구사항이 있는데 집합으로 바꿔 데이터 손실 발생
  • 입력 규모 추정을 과소평가해 선형 탐색을 유지
  • 메모리 제한을 무시하고 고비용 구조를 택함

문제의 정답 코드보다, 문제 모델에 맞는 구조인지 우선 검증해야 합니다.

연산 비율 기반 구조 선택

문제 의도: 연산 비율과 정렬 요구를 기준으로 구조 선택 규칙을 코드로 고정합니다.
입력 예시: (read=0.9, write=0.1, ordered=false), (read=0.7, write=0.3, ordered=true)
출력 예시: hash-map-or-hash-set, balanced-tree-or-sort-step

아래 예시는 입력된 연산 비율을 바탕으로 추천 구조를 단순 규칙으로 반환합니다.
정답 알고리즘이라기보다, 설계 판단 기준을 코드로 명시하는 예제입니다. 케이스를 한 줄씩 넣어 출력을 확인하면 분기 규칙을 쉽게 검증할 수 있습니다.

main.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string chooseStructure(double readRatio, double writeRatio, bool orderedOutput) {
    if (orderedOutput && readRatio >= 0.6) return "balanced-tree-or-sort-step";
    if (readRatio >= 0.8 && !orderedOutput) return "hash-map-or-hash-set";
    if (writeRatio >= 0.5) return "list-or-linked-structure";
    return "array-list-default";
}

int main() {
    vector<double> readCases = {0.9, 0.7, 0.4};
    vector<double> writeCases = {0.1, 0.3, 0.6};
    vector<bool> orderedCases = {false, true, false};

    for (int i = 0; i < static_cast<int>(readCases.size()); ++i) {
        double r = readCases[i];
        double w = writeCases[i];
        bool o = orderedCases[i];
        cout << "(" << r << ", " << w << ", " << boolalpha << o << ") -> "
             << chooseStructure(r, w, o) << "\n";
    }
    return 0;
}
Main.java
public class Main {
    static String chooseStructure(double readRatio, double writeRatio, boolean orderedOutput) {
        if (orderedOutput && readRatio >= 0.6) return "balanced-tree-or-sort-step";
        if (readRatio >= 0.8 && !orderedOutput) return "hash-map-or-hash-set";
        if (writeRatio >= 0.5) return "list-or-linked-structure";
        return "array-list-default";
    }

    public static void main(String[] args) {
        double[] readCases = {0.9, 0.7, 0.4};
        double[] writeCases = {0.1, 0.3, 0.6};
        boolean[] orderedCases = {false, true, false};

        for (int i = 0; i < readCases.length; i++) {
            double r = readCases[i];
            double w = writeCases[i];
            boolean o = orderedCases[i];
            System.out.println("(" + r + ", " + w + ", " + o + ") -> " + chooseStructure(r, w, o));
        }
    }
}
main.py
def choose_structure(read_ratio, write_ratio, ordered_output):
    if ordered_output and read_ratio >= 0.6:
        return "balanced-tree-or-sort-step"
    if read_ratio >= 0.8 and not ordered_output:
        return "hash-map-or-hash-set"
    if write_ratio >= 0.5:
        return "list-or-linked-structure"
    return "array-list-default"

cases = [
    (0.9, 0.1, False),
    (0.7, 0.3, True),
    (0.4, 0.6, False),
]

for c in cases:
    read_ratio = c[0]
    write_ratio = c[1]
    ordered_output = c[2]
    print(c, "->", choose_structure(read_ratio, write_ratio, ordered_output))
main.rs
fn choose_structure(read_ratio: f64, write_ratio: f64, ordered_output: bool) -> &'static str {
    if ordered_output && read_ratio >= 0.6 {
        return "balanced-tree-or-sort-step";
    }
    if read_ratio >= 0.8 && !ordered_output {
        return "hash-map-or-hash-set";
    }
    if write_ratio >= 0.5 {
        return "list-or-linked-structure";
    }
    "array-list-default"
}

fn main() {
    let read_cases = [0.9, 0.7, 0.4];
    let write_cases = [0.1, 0.3, 0.6];
    let ordered_cases = [false, true, false];

    for i in 0..read_cases.len() {
        let r = read_cases[i];
        let w = write_cases[i];
        let o = ordered_cases[i];
        println!("({}, {}, {}) -> {}", r, w, o, choose_structure(r, w, o));
    }
}

알고리즘 기초 결과 재확인

이 코드는 완벽한 자동 선택기를 만들려는 목적이 아닙니다.
설계 판단 이유를 문장으로만 남기지 않고, 명시적인 규칙으로 표현하는 데 목적이 있습니다.
팀 개발에서는 이런 규칙 함수를 두면 코드 리뷰에서 구조 선택 판단 이유를 빠르게 공유할 수 있습니다.

출력 결과가 바뀌면 자료구조 자체가 바뀌는 점을 의식하는 것이 중요합니다.
예를 들어 동일 입력이라도 ordered_output=True 여부에 따라 해시 대신 트리/정렬 단계를 택해야 합니다.

  • 평균 시간복잡도: O(1) (조건 분기 수 고정)
  • 최악 시간복잡도: O(1)
  • 공간복잡도: O(1)

실전 판정 흐름

운영 환경에서 자료구조를 바꿀 때는 아래 흐름으로 접근하면 안전합니다.

  • 1단계: 현재 병목 연산의 실제 비율을 측정한다.
  • 2단계: 평균/최악 입력 패턴을 분리해 재현한다.
  • 3단계: 후보 구조 2~3개를 동일 인터페이스로 교체 테스트한다.
  • 4단계: 성능, 메모리, 코드 복잡도, 디버깅 난이도를 함께 비교한다.
  • 5단계: 선택 판단 이유를 문서화해 이후 변경 비용을 낮춘다.

이 절차를 생략하고 감으로 구조를 바꾸면, 단기 개선 뒤 장기 퇴행이 자주 발생합니다.

운영 관점 상충 지점

자료구조 선택은 CPU 시간만의 문제가 아닙니다.

  • 메모리 지역성(locality): 같은 복잡도라도 캐시 친화성으로 체감 속도가 달라집니다.
  • 직렬화 비용: 네트워크/저장소로 내보낼 때 변환 비용이 커질 수 있습니다.
  • 관찰 가능성: 디버깅 로그에서 읽기 쉬운 구조가 운영 대응 시간을 줄입니다.
  • 동시성 안전성: 멀티스레드 환경에서는 락 전략이 자료구조와 함께 결정됩니다.

정리하면, 자료구조는 성능 튜닝 대상이면서 동시에 운영 설계 요소입니다.

중복/누락 실패사례 확인 포인트

  • 자료구조 교체 후 기존 정렬/중복 정책이 유지되는지 반드시 확인합니다.
  • 해시 구조는 키 정규화(대소문자, 공백 처리)가 누락되면 품질 문제가 생깁니다.
  • 작은 테스트 입력만 통과했다고 확신하지 말고 입력 규모를 늘려 검증합니다.
  • 코드 단순성만 보고 선택하면 운영 단계에서 병목을 뒤늦게 발견하게 됩니다.

조회 중심 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 판단 축을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

접근평균 시간최악 시간공간
리스트 선형 탐색O(N)O(N)O(N)
해시 집합 조회O(1)O(N)O(N)

평균과 최악이 다를 때는 서비스가 최악 입력을 받을 수 있는지가 의사결정 기준입니다.

구현 전후 점검 항목

  • 조회/삽입/삭제 연산 비율을 수치로 정리했는가
  • 정렬/중복 정책을 문제 요구와 일치시켰는가
  • 평균 성능과 최악 성능을 분리해 검토했는가
  • 교체 후 메모리 사용량과 디버깅 난이도를 함께 확인했는가

결론 정리

알고리즘 문제의 성패는 고급 기법보다 연산 모델을 맞추는 기본기에서 갈립니다.
자료구조와 알고리즘을 분리하지 말고, 한 번에 설계하는 습관을 가지면 문제 해결 속도와 품질이 함께 올라갑니다.

시간복잡도와 공간복잡도 읽는 법

다음 페이지

목차

핵심 개념 요약
자료구조 선택이 실무에서 중요한 이유
실패 입력부터 재현하는 검증 순서
단순 리스트 탐색
알고리즘 기초 결과 기초 조건 확인
해시 집합 기반 조회
알고리즘 기초 결과 전개 흐름 추적
조회/삽입 비율별 판정 축
해시 셋 도입 시 구현 비용 상충
로그 단서로 좁혀가는 실수 포인트
연산 비율 기반 구조 선택
알고리즘 기초 결과 재확인
실전 판정 흐름
운영 관점 상충 지점
중복/누락 실패사례 확인 포인트
조회 중심 비용 모델 정리
구현 전후 점검 항목
결론 정리