부록 E16: 알고리즘과 복잡도

5 분 소요

이 장에서 배울 것

이번 장에서는 알고리즘(algorithm)과 복잡도(complexity)를 배웁니다. 알고리즘은 문제를 푸는 절차입니다. 복잡도는 그 절차가 얼마나 오래 걸리고, 얼마나 많은 메모리를 쓰는지 보는 감각입니다.

핵심 용어를 먼저 정리하겠습니다.

알고리즘(algorithm): 입력을 받아 원하는 출력을 만드는 단계적 절차입니다.
입력(input): 알고리즘에 들어가는 데이터입니다.
출력(output): 알고리즘이 만들어 내는 결과입니다.
시간복잡도(time complexity): 입력이 커질 때 실행 시간이 얼마나 늘어나는지 나타내는 감각입니다.
공간복잡도(space complexity): 입력이 커질 때 메모리 사용량이 얼마나 늘어나는지 나타내는 감각입니다.
선형시간(O(n)): 입력 개수에 비례해 시간이 늘어나는 경우입니다.
제곱시간(O(n²)): 입력 개수의 제곱에 비례해 시간이 늘어나는 경우입니다.
해시(hash): 값을 빠르게 찾기 위해 key를 이용하는 방식입니다.
동적 계획법(dynamic programming): 작은 문제의 답을 저장해 큰 문제를 푸는 방법입니다.
그래프 탐색(graph traversal): 노드와 간선을 따라 연결된 구조를 살펴보는 방법입니다.

알고리즘과 복잡도

가장 쉬운 비유: 요리법과 장보기 비용

알고리즘은 요리법과 비슷합니다. 라면 끓이기 알고리즘은 물을 끓이고, 면과 스프를 넣고, 몇 분 기다리는 절차입니다. 입력은 물, 면, 스프이고 출력은 라면입니다.

복잡도는 그 요리법의 비용 감각입니다. 한 명분 라면은 쉽지만 100명분 라면은 시간이 더 걸립니다. 입력이 커질수록 시간이 얼마나 늘어나는지 보는 것이 시간복잡도입니다.

선형시간: 하나씩 한 번만 보기

유전자 이름 목록에서 TP53이 있는지 찾는 코드를 봅시다.

genes = ["BRCA1", "EGFR", "TP53", "MYC"]

for gene in genes:
    if gene == "TP53":
        print("찾았습니다")

목록 길이가 4개면 최대 4번 봅니다. 길이가 100개면 최대 100번 봅니다. 이런 식으로 입력 크기에 비례하는 경우를 선형시간이라고 합니다.

제곱시간: 모든 쌍을 비교하기

모든 샘플 쌍의 거리를 계산한다고 생각해 봅시다.

samples = ["s1", "s2", "s3", "s4"]

for a in samples:
    for b in samples:
        print(a, b)

샘플이 4개면 4×4=16번 비교합니다. 샘플이 100개면 100×100=10,000번 비교합니다. 이런 구조는 입력이 커질 때 빠르게 무거워집니다.

해시와 딕셔너리

파이썬 딕셔너리는 key로 값을 빠르게 찾을 수 있습니다.

expression = {
    "BRCA1": 12.5,
    "TP53": 8.0,
    "EGFR": 20.1
}

print(expression["TP53"])

리스트에서 하나씩 찾는 것보다 딕셔너리로 바로 찾는 것이 보통 훨씬 빠릅니다. 생물정보학에서는 유전자 ID → 유전자 이름, 변이 ID → 주석, 샘플 ID → 환자 정보처럼 key-value 구조가 자주 나옵니다.

정렬과 탐색

정렬(sorting)은 데이터를 순서대로 놓는 작업입니다. 예를 들어 read count가 큰 유전자부터 보고 싶다면 정렬이 필요합니다.

values = [5, 20, 3, 10]
print(sorted(values))

결과는 다음과 같습니다.

[3, 5, 10, 20]

정렬된 데이터에서는 탐색을 더 빠르게 할 수 있습니다. 책의 단어가 알파벳순으로 정리되어 있으면 찾기 쉬운 것과 같습니다.

동적 계획법과 서열 비교

동적 계획법은 작은 문제의 답을 표에 저장하면서 큰 문제를 푸는 방법입니다. 서열 정렬(sequence alignment)에서 중요합니다.

예를 들어 두 문자열을 비교할 때, 앞부분끼리의 최적 비교 결과를 저장해 두면 뒤쪽 계산을 반복하지 않아도 됩니다. 입문 단계에서는 “서열 정렬은 모든 가능성을 막무가내로 다 해보지 않고, 작은 비교 결과를 재사용한다” 정도로 이해하면 충분합니다.

그래프 탐색

그래프는 점과 선으로 이루어진 구조입니다. 단백질 상호작용망, 유전자 조절망, 대사경로는 그래프로 볼 수 있습니다.

그래프 탐색은 한 노드에서 시작해 연결된 노드들을 따라가는 작업입니다. 예를 들어 어떤 단백질과 직접 또는 간접적으로 연결된 단백질들을 찾을 수 있습니다.

복잡도 감각이 왜 필요한가

작은 예제에서는 어떤 코드든 잘 돌아갑니다. 하지만 생물정보학 데이터는 큽니다. read가 수천만 개, 세포가 수십만 개, 변이가 수백만 개일 수 있습니다. 이때 비효율적인 알고리즘은 현실적으로 끝나지 않을 수 있습니다.

예를 들어 1,000개 데이터를 모든 쌍 비교하면 1,000,000번입니다. 100,000개라면 10,000,000,000번입니다. 입력이 커질 때 비용이 어떻게 변하는지 생각해야 합니다.

실전 보강: n이 커질 때 숫자가 어떻게 폭발하는가

복잡도는 기호만 외우면 쓸모가 없습니다. 입력 크기가 커질 때 실제 숫자가 어떻게 바뀌는지 봐야 합니다.

샘플 수 n = 10
모든 쌍 비교 n² = 100번
중복 없는 쌍 비교 n(n-1)/2 = 45번

샘플 수 n = 1,000
모든 쌍 비교 n² = 1,000,000번
중복 없는 쌍 비교 n(n-1)/2 = 499,500번

작은 데이터에서는 아무 코드나 빨라 보입니다. 하지만 샘플 수가 100배가 되면 O(n²) 코드는 대략 10,000배 무거워질 수 있습니다.

실전 보강: 서열 정렬과 DP 표 크기

동적 계획법으로 두 서열을 비교할 때는 보통 표를 만듭니다. 길이가 각각 n, m인 두 서열을 비교하면 대략 (n+1) × (m+1)칸을 채웁니다.

서열 A 길이 = 100
서열 B 길이 = 200
DP 표 크기 = 101 × 201 = 20,301칸

서열이 조금만 길어져도 표가 커집니다. 그래서 생물정보학에서는 정확한 알고리즘과 빠른 휴리스틱 방법을 상황에 맞게 고릅니다.

초보자가 자주 하는 오해

오해 1: 내 노트북에서 빨랐으니 서버에서도 항상 충분하다. 작은 테스트 데이터와 실제 전체 데이터는 규모가 다릅니다.
오해 2: for문은 무조건 나쁘다. 문제는 for문 자체가 아니라 입력 크기에 따라 반복이 어떻게 늘어나는지입니다.
오해 3: 메모리는 실행 시간과 별개다. 너무 큰 표나 배열은 메모리를 터뜨려 실행 자체를 실패하게 할 수 있습니다.
오해 4: Big-O는 정확한 초 단위 시간이다. Big-O는 증가 추세를 보는 도구입니다.

이전 개념과 다음 개념의 연결

복잡도 감각은 E15 single-cell, E21 워크플로우, E22 HPC, E24 대규모 데이터 처리에서 계속 등장합니다. 어떤 코드를 병렬화하기 전에 먼저 알고리즘 자체가 너무 무거운지 판단해야 합니다.

어려운 개념 보강: Big-O를 숫자로 체감하기

복잡도 표기에서 O(n), O(n²) 같은 표기는 정확한 실행 시간을 초 단위로 말하는 공식이 아닙니다. 입력이 커질 때 계산량이 어떤 속도로 늘어나는지 보는 약속입니다. 여기서 n은 입력 개수입니다. 샘플 수, read 수, 유전자 수, 변이 수가 모두 상황에 따라 n이 될 수 있습니다.

선형시간 O(n)은 입력을 한 번 훑는 느낌입니다.

n개를 각각 한 번씩 본다 → 대략 n번 작업

제곱시간 O(n²)은 모든 쌍을 비교하는 느낌입니다.

n개 각각을 다른 n개와 비교한다 → 대략 n × n번 작업

숫자로 보면 차이가 커집니다.

n = 100     → O(n)은 100번,     O(n²)은 10,000번
n = 10,000  → O(n)은 10,000번,  O(n²)은 100,000,000번

이 차이는 생물정보학에서 바로 문제가 됩니다. 샘플 100개끼리 모든 쌍의 거리를 계산하는 것은 괜찮을 수 있지만, 세포 100만 개끼리 모든 쌍을 비교하면 거의 불가능해질 수 있습니다.

공간복잡도도 중요합니다. 100만 × 100만 거리 행렬을 전부 저장하려면 원소가 1조 개입니다. 원소 하나가 8바이트 실수라면 필요한 메모리는 다음과 같습니다.

1,000,000 × 1,000,000 × 8 bytes
= 8,000,000,000,000 bytes
≈ 8 TB

이런 계산은 “코드가 논리적으로 맞는가”와 별개로 “현실적으로 실행 가능한가”를 판단하게 해 줍니다.

흔한 오해는 O(n²)이면 항상 나쁘고 O(n)이면 항상 좋다고 생각하는 것입니다. 작은 데이터에서는 O(n²)도 충분히 괜찮을 수 있고, 큰 데이터에서는 O(n)이라도 파일 입출력이나 메모리 병목 때문에 느릴 수 있습니다. 복잡도는 최종 답이 아니라, 위험한 병목을 미리 발견하는 지도입니다.

미니 실습 블록: FASTA 길이 계산에서 시간복잡도 생각하기

이 실습은 FASTA 길이 계산에서 시간복잡도 생각하기를 직접 손으로 확인하는 연습입니다. 왜 필요한가 하면, 생물정보학 파일은 매우 크므로 같은 일을 한 번 훑는 코드와 모든 쌍을 비교하는 코드는 실행 시간이 크게 달라지기 때문입니다.

seqs = ["ATGC", "ATGCGC", "A"]

total = 0
for seq in seqs:
    total = total + len(seq)

print(total)

각 코드 요소의 의미를 풀어보면 다음과 같습니다. 이 코드는 서열 리스트를 한 번만 훑으므로 서열 개수를 n이라고 할 때 대략 O(n)입니다. 반면 모든 서열 쌍을 비교하면 O(n²)에 가까워질 수 있습니다.

생물정보학/계산생물학에서 쓰이는 장면은 분명합니다. read 수, 유전자 수, 세포 수가 커질수록 알고리즘 선택이 분석 시간과 메모리에 직접 영향을 줍니다.

흔한 오해 또는 주의점도 있습니다. 작은 예제에서 빠른 코드도 실제 FASTQ 수억 줄에서는 병목이 될 수 있습니다.

핵심 정리

알고리즘은 문제를 푸는 절차이고, 복잡도는 그 절차의 시간과 메모리 비용 감각입니다. 생물정보학에서는 데이터가 크기 때문에 선형시간, 제곱시간, 해시, 정렬, 동적 계획법, 그래프 탐색 같은 기본 개념을 알아야 합니다.

Gemini AI 채점

주관식 답안은 Gemini API로 채점합니다. API 키는 이 브라우저에만 저장됩니다.

API KEY 미등록

1. [객관식] 객관식

알고리즘의 설명으로 적절한 것은?

선택지 입력을 받아 원하는 출력을 만드는 단계적 절차입니다. 파일 확장자만 뜻합니다. 작은 예제에서 빨랐으니 입력이 커져도 항상 빠르다고 보는 해석 단백질의 한 종류입니다.
2. [객관식] 객관식

시간복잡도가 보는 것은?

선택지 단백질 전하가 어떻게 변하는지입니다. 실행 시간만 보고 메모리 사용량은 고려하지 않는 접근 입력이 커질 때 실행 시간이 어떻게 늘어나는지입니다. 폴더 색이 무엇인지입니다.
3. [객관식] 객관식

선형시간 O(n)에 가까운 코드는?

선택지 모든 원소 쌍을 이중 반복문으로 비교하는 코드입니다. 목록의 원소를 하나씩 한 번 확인하는 코드입니다. 서버를 끄는 코드입니다. 모든 값을 무한 반복하는 코드입니다.
4. [객관식] 객관식

제곱시간 O(n²)에 가까운 코드는?

선택지 딕셔너리에서 key 하나를 바로 찾는 코드입니다. 한 번만 print하는 코드입니다. 파일 이름을 그대로 출력하는 코드입니다. 모든 샘플 쌍을 이중 반복문으로 비교하는 코드입니다.
5. [객관식] 객관식

샘플 100개를 모든 쌍 비교하면 대략 몇 번 비교하는가? 단순히 100×100으로 생각한다.

선택지 100번입니다. 200번입니다. 1,000번입니다. 10,000번입니다.
6. [객관식] 객관식

딕셔너리가 유용한 상황으로 적절한 것은?

선택지 모든 파일을 강제로 삭제할 때입니다. 유전자 ID로 유전자 이름이나 발현량을 빠르게 찾을 때입니다. O(n²)와 O(n)을 입력 크기와 무관한 고정 시간으로 보는 해석 동적 계획법 표 크기가 서열 길이와 무관하다고 보는 해석
7. [객관식] 객관식

sorted([5, 20, 3, 10])의 결과는?

선택지 [20, 10, 5, 3] [5, 20, 3, 10] [3, 5, 10, 20] [3, 10, 5, 20]
12. [객관식] 객관식

동적 계획법의 입문용 설명으로 적절한 것은?

선택지 작은 문제의 답을 저장해 큰 문제 계산에 재사용하는 방법입니다. 모든 데이터를 삭제하는 방법입니다. 해시 기반 조회와 선형 탐색의 비용 차이를 무시하는 접근 read 품질 점수를 실험하는 방법입니다.
13. [객관식] 객관식

서열 정렬에서 동적 계획법이 유용한 이유는?

선택지 서열을 물리적으로 접기 때문입니다. SQL 서버를 자동으로 끄기 때문입니다. 부분 서열 비교 결과를 재사용해 반복 계산을 줄일 수 있기 때문입니다. Big-O를 실제 초 단위 실행시간과 완전히 같은 값으로 보는 해석
14. [객관식] 객관식

그래프 탐색의 설명으로 적절한 것은?

선택지 노드와 간선을 따라 연결된 구조를 살펴보는 것입니다. CSV 파일의 쉼표를 모두 없애는 것입니다. 작은 예제에서 빨랐으니 입력이 커져도 항상 빠르다고 보는 해석 모든 read를 삭제하는 것입니다.
15. [객관식] 객관식

단백질 상호작용망을 그래프로 볼 때 노드에 해당하기 쉬운 것은?

선택지 파일 확장자입니다. 실행 시간만 보고 메모리 사용량은 고려하지 않는 접근 O(n²)와 O(n)을 입력 크기와 무관한 고정 시간으로 보는 해석 단백질입니다.
16. [객관식] 객관식

데이터가 커질 때 비효율적인 알고리즘이 문제가 되는 이유는?

선택지 컴퓨터가 모든 숫자를 싫어하기 때문입니다. 실행 시간이 현실적으로 끝나지 않을 정도로 커질 수 있기 때문입니다. 유전자가 항상 사라지기 때문입니다. 파일 이름이 반드시 한글이어야 하기 때문입니다.
17. [객관식] 객관식

리스트에서 원하는 값을 처음부터 하나씩 찾는 방식은 보통 어떤 감각인가?

선택지 항상 0초 탐색입니다. 입력 개수에 비례하는 선형 탐색입니다. 무조건 제곱시간입니다. 항상 딥러닝입니다.
18. [객관식] 객관식

공간복잡도가 보는 것은?

선택지 동적 계획법 표 크기가 서열 길이와 무관하다고 보는 해석 단백질 이름만 봅니다. 해시 기반 조회와 선형 탐색의 비용 차이를 무시하는 접근 알고리즘이 메모리를 얼마나 쓰는지입니다.
19. [객관식] 객관식

100,000개 데이터의 모든 쌍 비교가 부담스러운 이유는?

선택지 대략 100,000×100,000번 비교가 필요하기 때문입니다. 항상 100번만 비교하기 때문입니다. 컴퓨터가 리스트를 저장하지 못하기 때문입니다. 모든 데이터가 문자열이 아니기 때문입니다.
20. [객관식] 객관식

해시(hash) 감각에 가까운 것은?

선택지 모든 값을 순서대로 손으로 세는 방식입니다. 파일을 이미지로 변환하는 방식입니다. key를 이용해 값을 빠르게 찾는 방식입니다. Big-O를 실제 초 단위 실행시간과 완전히 같은 값으로 보는 해석
21. [객관식] 객관식

생물정보학에서 복잡도 감각이 특히 중요한 이유는?

선택지 생물학에는 숫자가 전혀 없기 때문입니다. 모든 데이터가 항상 1개뿐이기 때문입니다. 코드는 절대 느려지지 않기 때문입니다. read, 변이, 세포 수가 매우 클 수 있기 때문입니다.
22. [객관식] 객관식

이중 반복문이 항상 나쁜 것은 아니지만 조심해야 하는 이유는?

선택지 한 줄 코드가 모두 금지되기 때문입니다. 입력이 커지면 비교 횟수가 제곱으로 늘 수 있기 때문입니다. Python이 반복문을 지원하지 않기 때문입니다. 리스트가 항상 비어 있기 때문입니다.
23. [객관식] 객관식

정렬된 데이터가 탐색에 도움이 되는 비유로 적절한 것은?

선택지 무작위로 흩어진 종이를 더 찾기 어렵게 만드는 것과 같습니다. 음식을 냉장고에 넣는 것과 같습니다. 단어가 알파벳순으로 정리된 사전에서 찾기 쉬운 것과 같습니다. 전하가 서로 밀어내는 것과 같습니다.
24. [객관식] 객관식

알고리즘을 평가할 때 함께 봐야 할 두 비용은?

선택지 시간과 메모리입니다. 작은 예제에서 빨랐으니 입력이 커져도 항상 빠르다고 보는 해석 실행 시간만 보고 메모리 사용량은 고려하지 않는 접근 파일명과 배경화면입니다.
25. [객관식] 객관식

샘플 1000개의 모든 순서 있는 쌍을 이중 for문으로 비교하면 비교 횟수는?

선택지 1,000,000번 1,000번 2,000번 499,500번
26. [객관식] 객관식

샘플 1000개의 중복 없는 쌍 비교 횟수 n(n-1)/2는?

선택지 1,000,000번 500번 499,500번 999번
27. [객관식] 객관식

길이 100과 200인 두 서열의 DP 표를 (n+1)(m+1)로 만들면 칸 수는?

선택지 20,000칸 20,301칸 300칸 30,000칸
28. [객관식] 객관식

O(n²) 알고리즘에서 n이 100에서 1000으로 10배 증가하면 연산량은 대략 몇 배 증가하는가?

선택지 10배 20배 1000배 100배
29. [객관식] 객관식

유전자 이름을 key로 발현량을 빠르게 찾고 싶을 때 적절한 파이썬 자료구조는?

선택지 dict 무조건 이중 리스트 print문 주석 문자열
30. [객관식] 객관식

다음 코드의 시간복잡도에 가장 가까운 것은?

선택지 O(1) O(n²) O(n) O(2^n)
31. [객관식] 객관식

다음 코드의 시간복잡도에 가장 가까운 것은?

선택지 O(1) O(n²) O(n) O(log n)
32. [객관식] 객관식

입력 크기가 커질수록 메모리 사용량도 함께 폭증하는 대표 상황은?

선택지 변수 이름을 짧게 쓰는 경우 주석을 한 줄 추가하는 경우 print 문구를 한글로 쓰는 경우 두 서열 비교를 위해 큰 DP 표를 메모리에 올리는 경우
33. [객관식] 객관식

작은 테스트 데이터에서 빠른 코드가 실제 대규모 데이터에서 느려질 수 있는 가장 핵심 이유는?

선택지 대규모 데이터에는 숫자가 없기 때문이다. 작은 데이터는 항상 틀린 데이터이기 때문이다. 컴퓨터는 큰 파일을 읽을 수 없기 때문이다. 입력 크기에 따른 반복 횟수 증가율이 숨겨져 있을 수 있기 때문이다.
34. [객관식] 객관식

O(n log n)이 O(n²)보다 대규모 정렬/비교에서 자주 유리한 이유는?

선택지 항상 메모리를 0으로 쓰기 때문이다. n이 커질수록 n²보다 증가 속도가 훨씬 완만하기 때문이다. 정렬 결과를 무작위로 만들기 때문이다. 입력이 커질수록 실행 횟수가 줄어들기 때문이다.
35. [실전] 객관식

서열 n개를 한 번씩만 보며 길이를 합산하는 코드는 대략 어떤 시간복잡도인가?

선택지 원본 데이터를 덮어써서 파일 수를 줄이는 것이다. 분석 결과를 해석 없이 바로 생물학적 결론으로 확정하는 것이다. O(n) 샘플 ID와 파일명을 일부러 무작위로 바꾸는 것이다.
36. [실전] 객관식

모든 서열 쌍을 서로 비교하는 방식이 위험한 이유는?

선택지 원본 데이터를 덮어써서 파일 수를 줄이는 것이다. 분석 결과를 해석 없이 바로 생물학적 결론으로 확정하는 것이다. 샘플 ID와 파일명을 일부러 무작위로 바꾸는 것이다. 데이터가 커질수록 비교 횟수가 대략 n²으로 빠르게 늘기 때문이다.
주관식 37. [응용] 주관식 · Gemini 채점

알고리즘과 복잡도를 각각 설명하라.
주관식 38. [응용] 주관식 · Gemini 채점

선형시간과 제곱시간의 차이를 예로 설명하라.
주관식 39. [응용] 주관식 · Gemini 채점

딕셔너리가 유전자 정보 조회에 유용한 이유를 설명하라.
주관식 40. [응용] 주관식 · Gemini 채점

동적 계획법이 서열 정렬에 쓰이는 이유를 설명하라.
주관식 41. [응용] 주관식 · Gemini 채점

그래프 탐색이 생물정보학에서 쓰일 수 있는 예를 들어라.
주관식 42. [응용] 주관식 · Gemini 채점

대용량 생물정보학 데이터에서 복잡도 감각이 중요한 이유를 설명하라.
주관식 43. [응용] 주관식 · Gemini 채점

샘플 1000개에서 중복 없는 모든 쌍 비교 수를 계산하고, 왜 O(n²) 감각이 중요한지 설명하라.
주관식 44. [응용] 주관식 · Gemini 채점

길이 100과 200인 두 서열의 DP 표 크기를 계산하고, 공간복잡도 관점에서 설명하라.
주관식 45. [실습] 주관식 · Gemini 채점

서열 리스트의 총 길이를 계산하는 Python 코드를 작성하라.
주관식 46. [실습] 주관식 · Gemini 채점

생물정보학에서 O(n²) 알고리즘을 조심해야 하는 이유를 설명하라.