알고리즘 · 자료구조
알고리즘의 정확성·복잡도와 선택
먼저 모든 입력에 대한 정확성 계약을 확인한 뒤, 입력 규모와 서비스의 메모리·지연 시간 제약에 맞춰 알고리즘을 선택합니다.
이럴 때 필요해요
막연히 '이 알고리즘이 빠르다'거나 '문제를 많이 풀었다'는 인상 대신, 검증 가능한 복잡도 근거와 트레이드오프로 설계 결정을 설명하기 위해 필요합니다.
어떻게 동작하나요?
알고리즘을 설계하거나 고를 때 첫걸음은 속도가 아니라 정확성(Correctness)입니다. 허용되는 모든 입력 범위에서 요구된 출력이 나오는지, 반복문이나 재귀를 돌 때 깨지지 않는 규칙(불변식, Invariant)이 무엇인지, 그리고 빈 배열·단건 입력·최댓값·음수 같은 경계 조건에서도 멈추지 않고 올바르게 종료하는지를 먼저 확인해야 합니다. 평범한 테스트 케이스 몇 개가 우연히 통과하는 것과 모든 입력에서 계약이 성립하는 것은 다릅니다.
정확성이 검증되었다면 입력 크기 n이 커질 때 실행 시간과 메모리 사용량이 어떻게 증가하는지 시간 복잡도와 공간 복잡도로 비교합니다. 이때 평균적인 기대 비용과 최악의 경우(Worst-case) 비용, 그리고 가끔 일어나는 배열 확장 비용을 여러 연산에 나누어 계산하는 상환(Amortized) 비용을 구분해야 합니다. 또한 Big-O 표기는 입력 규모에 따른 증가 추세를 나타낼 뿐 그 자체가 실제 몇 밀리초가 걸린다는 뜻은 아닙니다.
실무에서 두 알고리즘을 두고 고민할 때는 서비스의 자원 제약을 함께 봅니다. 예를 들어 메모리가 빠듯한 환경에서는 전체 배열을 다 저장하는 O(n) 공간 방식 대신 스트리밍으로 누적값만 계산하는 O(1) 공간 방식을 고르거나, 캐시에 최대 크기 제한을 두어 시간과 공간을 맞바꾸는 절충(Trade-off)을 합니다. 반대로 입력 개수가 수십 개로 항상 작다면 복잡한 자료구조보다 상수 비용이 작고 읽기 쉬운 단순 루프가 훨씬 나은 선택일 수 있습니다.
암호나 보안 알고리즘을 다룰 때는 '누가 어떤 계산 능력으로 공격하는지(위협 모델)'와 '기밀성·무결성·인증 중 무엇을 지키는가'를 먼저 분리합니다. 평문 길이만큼의 무작위 키를 딱 한 번만 쓰는 일회용 패드(One-Time Pad)는 정보 이론적 비밀성을 주지만 키 전달이 어렵고 변조 검출(무결성)도 해 주지 않습니다. 현대 실용 암호는 현실적인 계산 한계에 기반한 안전성을 제공하며, 키 보관과 구현까지 포함한 시스템 전체로 평가해야 합니다.
면접에서 알고리즘 학습 경험을 답할 때도 확인 가능한 사실과 문제 해결 과정을 중심으로 이야기하는 것이 좋습니다. 단순히 푼 문제 개수를 부풀리기보다, 처음 세운 접근이 어떤 반례에서 실패했고 상태 정의나 자료구조를 어떻게 고쳐 해결했는지를 설명하면 탄탄한 기본기를 보여 줄 수 있습니다.
코드 예제
동작을 설명하는 읽기 전용 예제입니다.
요구: 숫자 스트림의 합계만 반환
방법 A: 모든 n개 값을 저장 후 합산 → 시간 O(n), 추가 공간 O(n)
방법 B: 누적 합계만 갱신 → 시간 O(n), 추가 공간 O(1)
주의: 모든 원소를 다시 출력해야 한다면 요구가 달라진다.숫자 스트림의 합계만 구하면 되는 요구사항에서 전체 값을 배열에 다 모아 두는 방법(추가 공간 O(n))과 누적 변수 하나만 갱신하는 방법(추가 공간 O(1))을 비교한 예시입니다. 만약 나중에 원본 숫자 전체를 다시 출력해야 한다면 출력 계약 자체가 달라집니다.
이 개념으로 실습하기
자주 헷갈리는 포인트
- 입력 크기나 상수 비용, 메모리 한도를 따지지 않고 Big-O 차수 하나만으로 실제 실행 속도 순위를 단정하면 안 됩니다.
- 암호 알고리즘의 기밀성 증명을 곧바로 메시지 무결성이나 서비스 전체의 절대적인 해킹 불가능성으로 확대 해석하면 안 됩니다.
내 말로 설명해 보기
추가 메모리를 O(n) 쓰던 알고리즘을 스트리밍 방식의 O(1) 공간 알고리즘으로 바꾸기 전에, 함수의 입력·출력 계약에서 무엇부터 확인해야 할까요?
실전 시나리오에 적용해 보기
함께 읽으면 좋은 개념
관련 면접 질문 8개
좋은 코드의 품질은 어떤 기준으로 평가하고 설명할 수 있나요?
좋은 코드는 명시된 기능 요구사항을 정확히 충족하면서, 나중에 코드를 수정하는 동료가 의도를 쉽게 이해하고 안전하게 검증할 수 있는 코드입니다. 이를 위해 경계 조건과 오류 처리 정책, 명확한 책임 분리, 읽히는 이름과 데이터 흐름, 그리고 요구되는 성능 수준을 함께 평가합니다. 단순히 코드 줄 수가 짧다거나 특정 패턴을 썼다는 점보다 실제 요구사항 변경 시나리오와 테스트 가능성을 근거로 유지보수성을 설명하는 것이 좋습니다.
꼬리질문과 참고자료 →문제를 해결할 좋은 알고리즘을 고를 때 정확성과 효율성은 어떤 순서로 검증하나요?
먼저 입력·출력 계약과 불변식(Invariant)을 바탕으로 모든 유효한 입력에서 올바른 답을 내고 정상 종료하는지 '정확성'부터 확인합니다. 그다음 입력 크기와 분포에 따른 시간·공간 복잡도, 최악의 경우(Worst-case), 그리고 구현 복잡도를 함께 검토합니다. 이론적 Big-O 차수로 규모 증가에 따른 추세를 비교하되, 실제 선택에서는 목표 실행 환경의 데이터로 측정한 결과를 함께 확인해야 합니다.
꼬리질문과 참고자료 →정확성이 같은 여러 알고리즘이 있을 때 어떤 비용과 제약 조건을 비교해 선택하나요?
정확성 요구를 모두 만족한다면 실제 입력 크기와 분포에서의 응답 지연(Latency), 단위 시간당 처리량(Throughput), 최대 메모리 사용량, 그리고 구현·운영 복잡도를 비교합니다. 예를 들어 실시간 사용자 요청은 최악 꼬리 지연(Tail Latency)을 줄이는 것이 중요하고, 대규모 배치 작업은 전체 처리량과 메모리 한도가 더 중요할 수 있습니다. 동일 조건의 측정치와 복잡도 분석을 근거로 선택 이유를 설명하고, 서비스 제약이 바뀌면 선택도 함께 재검토합니다.
꼬리질문과 참고자료 →