알고리즘 면접 질문

알고리즘의 시간 복잡도는 입력 크기에 따라 알고리즘 실행 시간이 얼마나 늘어나는지를 나타내고, 공간 복잡도는 알고리즘이 사용하는 메모리 공간이 얼마나 늘어나는지를 나타냅니다. 이 두 가지를 고려하는 이유는 효율적인 알고리즘을 설계하고 자원을 최적화하기 위해서입니다.

특히, Big O 표기법은 알고리즘의 성능을 분석할 때 입력 크기가 매우 커질 때, 즉 최악의 경우에 실행 시간이나 메모리 사용량이 어떻게 증가하는지를 나타내는 방법입니다. 예를 들어 O(n)은 입력 크기에 비례하여 실행 시간이 증가한다는 의미이고, O(1)은 입력 크기와 상관없이 항상 일정한 시간이 걸린다는 의미입니다. Big O 표기법을 통해 알고리즘의 확장성을 예측하고 성능 병목 지점을 파악하여 개선할 수 있습니다.

배열과 연결 리스트는 데이터를 저장하는 기본적인 자료구조이지만, 메모리 구조와 동작 방식에 큰 차이가 있습니다.

배열은 메모리에 연속적으로 할당되어 있어 인덱스를 통해 상수 시간(O(1))으로 데이터에 접근할 수 있다는 장점이 있습니다. 하지만 크기를 변경하기 어렵고, 중간에 데이터를 삽입하거나 삭제할 때 다른 요소들을 이동시켜야 하므로 비효율적입니다. 예를 들어, 정렬된 데이터를 유지해야 하는 경우, 새로운 데이터를 삽입할 때 배열은 삽입 위치 이후의 모든 데이터를 이동시켜야 합니다.

반면, 연결 리스트는 각 요소가 포인터를 통해 다음 요소를 가리키는 방식으로, 메모리에 비연속적으로 할당됩니다. 따라서 삽입/삭제 연산이 상수 시간(O(1))으로 가능하지만, 특정 위치의 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 하므로 탐색 시간이 오래 걸립니다(O(n)). 예를 들어, 빈번하게 데이터의 삽입/삭제가 일어나는 편집기나 플레이리스트 관리 시스템에 연결 리스트가 더 적합합니다.

스택과 큐는 데이터를 저장하고 관리하는 기본적인 자료구조입니다.

스택은 LIFO, 즉 Last-In, First-Out 원리를 따릅니다. 가장 마지막에 들어간 데이터가 가장 먼저 나오는 구조입니다. 마치 접시를 쌓아 올리는 것과 같습니다. 프로그래밍에서는 함수 호출 시 함수의 실행 정보를 저장하는 함수 호출 스택, 웹 브라우저의 뒤로 가기/앞으로 가기 기능 등에 활용됩니다.

큐는 FIFO, 즉 First-In, First-Out 원리를 따릅니다. 가장 먼저 들어간 데이터가 가장 먼저 나오는 구조입니다. 마치 줄을 서서 기다리는 것과 같습니다. 프린터의 인쇄 대기열, 운영체제의 작업 스케줄링, 메시지 큐 등에 사용됩니다.

이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다. 먼저 배열의 중간 값을 확인하고, 찾으려는 값과 비교합니다. 만약 중간 값이 찾으려는 값보다 크면, 탐색 범위를 왼쪽 절반으로 좁히고, 작으면 오른쪽 절반으로 좁힙니다. 이 과정을 반복하여 값을 찾거나, 탐색 범위가 없어지면 값이 없다고 판단합니다.

이 알고리즘을 사용하려면 데이터가 반드시 정렬되어 있어야 합니다.

시간 복잡도는 O(log N)입니다. 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 데이터의 크기가 커져도 탐색 시간이 매우 빠르게 증가하지 않습니다.

버블 정렬은 이름 그대로 물방울이 올라오듯, 인접한 두 원소를 계속 비교하면서 가장 큰(또는 작은) 원소를 맨 뒤로 보내는 방식입니다. 마치 거품이 올라오듯 말이죠. 한 번의 패스가 끝나면 가장 큰 원소가 제자리를 찾고, 다음 패스에서는 남은 원소들 중 가장 큰 원소가 제자리를 찾습니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

시간 복잡도는 최악의 경우와 평균적인 경우 모두 O(N^2)입니다. 이는 배열의 크기가 커질수록 정렬에 걸리는 시간이 제곱으로 늘어난다는 뜻이라, 실제 시스템에서는 매우 비효율적입니다. 예를 들어, 이미 정렬된 배열의 경우를 제외하고는 항상 N번의 비교와 N-1번의 교환이 발생합니다.

실제 시스템 개발에서 잘 사용되지 않는 주된 이유는 바로 이 O(N^2)의 비효율성 때문입니다. 데이터 양이 조금만 많아져도 성능 저하가 심각해지기 때문에, 퀵 정렬, 병합 정렬, 힙 정렬과 같이 평균적으로 O(N log N)의 시간 복잡도를 갖는 더 효율적인 알고리즘들이 선호됩니다. 물론, 버블 정렬도 약간의 최적화(한 번도 교환이 일어나지 않으면 정렬이 끝났다고 판단)를 통해 최선(이미 정렬된 경우)의 경우 O(N)의 시간 복잡도를 가질 수는 있지만, 이는 일반적인 상황과는 거리가 있습니다.

재귀 함수는 함수가 자기 자신을 다시 호출하는 방식으로 문제를 해결하는 프로그래밍 기법입니다. 큰 문제를 작은 부분 문제로 나누어 해결하는 데 유용하죠.

재귀 함수를 작성할 때 가장 중요한 두 가지 요소는 '종료 조건'과 '재귀 호출'입니다.

종료 조건은 재귀 호출이 멈추는 시점을 정의하는 부분입니다. 이게 없으면 함수가 무한히 자기 자신을 호출하면서 스택 오버플로우 에러가 발생할 수 있습니다. 흔히 '기저 사례(base case)'라고도 부릅니다.

재귀 호출은 함수가 자기 자신을 호출하는 부분인데, 이때 반드시 입력값을 변경해서 호출해야 합니다. 그렇지 않으면 종료 조건에 도달하지 못하고 무한 루프에 빠질 수 있습니다. 예를 들어 팩토리얼 계산 함수에서 factorial(n)을 호출할 때 factorial(n-1)과 같이 입력값을 줄여나가는 방식입니다.

해시 테이블은 키(Key)와 값(Value)을 저장하는 자료구조로, 키를 해시 함수를 통해 배열의 인덱스로 변환하여 데이터를 빠르게 저장하고 검색할 수 있게 해줍니다. 해싱은 이 해시 함수를 이용해 키를 고정된 크기의 해시 값으로 변환하는 과정입니다.

하지만 서로 다른 키가 같은 해시 값을 가질 수 있는데, 이를 충돌(Collision)이라고 합니다. 충돌을 해결하는 대표적인 방법 두 가지는 다음과 같습니다.

첫째, 체이닝(Chaining)입니다. 각 배열의 인덱스마다 연결 리스트와 같은 별도의 자료구조를 두어, 같은 해시 값을 가진 데이터들을 연결 리스트에 저장하는 방식입니다.

둘째, 개방 주소법(Open Addressing)입니다. 충돌이 발생했을 때, 비어있는 다른 인덱스를 찾아 데이터를 저장하는 방식입니다. 이때 탐사(Probing)라는 과정을 통해 다음 저장될 위치를 결정합니다.

퀵 정렬과 병합 정렬은 모두 분할 정복 기법을 사용하는 효율적인 정렬 알고리즘입니다.

퀵 정렬은 먼저 '피벗'이라는 기준 요소를 선택하고, 배열을 피벗보다 작은 요소와 큰 요소로 분할합니다. 이 과정을 재귀적으로 반복하여 정렬합니다. 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 피벗 선택이 좋지 않으면 최악의 경우 O(n^2)까지 성능이 저하될 수 있습니다. 공간 복잡도는 재귀 호출 스택 때문에 O(log n)에서 O(n) 정도입니다.

병합 정렬은 배열을 절반으로 계속 나누다가, 각 부분 배열을 정렬한 후 다시 합치는(병합) 방식으로 동작합니다. 이 병합 과정에서 정렬이 이루어집니다. 퀵 정렬과 달리 항상 O(n log n)의 시간 복잡도를 보장하며, 최악의 경우에도 성능이 일정합니다. 하지만 정렬된 두 부분 배열을 합치기 위해 추가적인 공간이 필요하므로 공간 복잡도는 O(n)입니다.

따라서 데이터가 이미 어느 정도 정렬되어 있거나 메모리 제약이 크지 않다면 퀵 정렬이 평균적으로 더 빠를 수 있습니다. 반면, 데이터의 분포를 알 수 없거나 최악의 경우에도 일정한 성능이 중요하다면 병합 정렬이 더 안정적인 선택입니다.

면접관님, 특정 네트워크에서 최단 경로를 찾아야 한다면 너비 우선 탐색(BFS)을 선택하겠습니다.

BFS는 시작 노드에서 가까운 노드부터 차례대로 탐색하기 때문에, 간선의 가중치가 없는 그래프에서는 최단 경로를 보장합니다. 반면, 깊이 우선 탐색(DFS)은 깊이 우선으로 탐색하기 때문에 최단 경로를 보장하지 못합니다.

예를 들어, 미로 찾기를 생각해보면 BFS는 출구까지 가장 빠른 길을 찾는 반면, DFS는 일단 한 방향으로 끝까지 가보고 막히면 돌아오는 방식으로 탐색합니다.

따라서, 가중치가 없는 그래프에서 최단 경로를 찾는 문제에서는 BFS가 더 적합하다고 생각합니다.

동적 계획법과 그리디 알고리즘은 둘 다 최적화 문제를 해결하는 방법이지만, 접근 방식에 차이가 있습니다. 동적 계획법은 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피합니다. 즉, "최적 부분 구조"와 "중복 부분 문제"라는 특징을 가집니다. 예를 들어, 피보나치 수열이나 최단 경로 문제를 풀 때 유용합니다.

반면, 그리디 알고리즘은 각 단계에서 "탐욕적 선택 속성"을 만족하는, 즉 당장 눈앞에 보이는 최적의 선택을 합니다. 하지만 이 지역적인 최적해가 항상 전역적인 최적해를 보장하지는 않습니다. 대표적인 예시로, 거스름돈 문제를 해결할 때 가장 큰 단위의 동전부터 사용하는 방법이 있습니다.

따라서, 문제의 특성에 따라 적절한 알고리즘을 선택해야 합니다. 동적 계획법은 최적해를 보장하지만, 계산 비용이 높을 수 있고, 그리디 알고리즘은 빠르지만 최적해를 보장하지 못할 수 있습니다.

해시 테이블에서 해시 충돌을 해결하는 대표적인 방법은 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)이 있습니다.

체이닝은 각 해시 값에 연결 리스트를 연결하여 충돌이 발생하면 해당 리스트에 새로운 노드를 추가하는 방식입니다. 장점은 구현이 비교적 간단하고 삭제가 용이하며, 테이블이 꽉 차더라도 어느 정도 성능을 유지할 수 있다는 점입니다. 단점은 연결 리스트를 위한 추가적인 메모리 공간이 필요하고, 최악의 경우 탐색 시간이 O(n)까지 늘어날 수 있다는 것입니다.

오픈 어드레싱은 충돌이 발생하면 미리 정해진 규칙에 따라 해시 테이블 내의 다른 빈 슬롯을 찾아 데이터를 저장하는 방식입니다. 선형 탐사, 이차 탐사, 이중 해싱 등이 있습니다. 장점은 추가적인 메모리 오버헤드가 없다는 점입니다. 단점은 테이블이 꽉 찰수록 성능이 급격히 저하될 수 있고, 특히 선형 탐사의 경우 클러스터링 문제가 발생하여 탐색 효율이 떨어질 수 있습니다.

면접관님, 이진 탐색 트리에서 중위 순회는 항상 노드를 정렬된 순서대로 방문한다는 특징이 있습니다. 왼쪽 서브트리, 루트 노드, 오른쪽 서브트리 순으로 방문하기 때문이죠.

이 특징을 활용해서 다양한 문제를 풀 수 있습니다. 예를 들어, BST에 저장된 모든 값을 정렬된 배열 형태로 얻고 싶을 때 중위 순회를 사용하면 간단하게 구현할 수 있습니다.

또 다른 예로는, 특정 범위 내에 있는 값을 찾는 문제가 있습니다. 중위 순회를 하면서 현재 노드의 값이 범위 안에 있는지 확인하고, 범위를 벗어나면 탐색을 중단하여 효율적으로 원하는 값들을 찾을 수 있습니다. 균형 잡힌 BST라면 시간 복잡도는 O(k + log n) 정도가 될 겁니다. (k는 범위 내의 노드 수, n은 전체 노드 수)

우선순위 큐를 구현할 때 힙을 사용하는 가장 큰 이유는 효율성입니다. 힙은 O(log N)의 시간 복잡도로 삽입과 삭제 연산을 수행할 수 있기 때문입니다. 우선순위 큐는 가장 높은(또는 가장 낮은) 우선순위를 가진 요소를 빠르게 찾고 제거해야 하는데, 힙은 이러한 요구사항을 완벽하게 충족합니다.

힙은 완전 이진 트리 구조를 가지며, 최소 힙이나 최대 힙이라는 힙 속성을 유지합니다. 최소 힙은 부모 노드가 항상 자식 노드보다 작거나 같고, 최대 힙은 부모 노드가 항상 자식 노드보다 크거나 같습니다.

삽입 연산은 새로운 요소를 트리의 가장 마지막 레벨에 추가한 후, 힙 속성을 만족하도록 부모 노드와 비교하며 위로 올라가는 '상향식(bubble-up)' 과정을 거칩니다. 삭제 연산은 루트 노드를 제거하고, 트리의 가장 마지막 노드를 루트로 옮긴 후, 힙 속성을 만족하도록 자식 노드와 비교하며 아래로 내려가는 '하향식(bubble-down)' 과정을 거칩니다. 이 두 연산 모두 트리의 높이에 비례하는 시간 복잡도를 가지므로 O(log N)이 됩니다.

두 포인터 기법은 주로 배열이나 연결 리스트에서 특정 조건을 만족하는 요소를 효율적으로 찾을 때 유용합니다.

첫 번째 예시는 정렬된 배열에서 합이 특정 값 target이 되는 두 수를 찾는 문제입니다. 배열의 양 끝에 포인터 두 개를 두고, 두 포인터가 가리키는 값의 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로, 크면 오른쪽 포인터를 왼쪽으로 이동시키면서 탐색합니다. 이 방법은 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

두 번째 예시는 문자열이 회문인지 확인하는 문제입니다. 문자열의 처음과 끝에 포인터를 두고, 두 포인터가 가리키는 문자가 서로 다르면 회문이 아니고, 같으면 포인터를 안쪽으로 이동시키면서 비교합니다. 이 역시 O(n)의 시간 복잡도로 회문 여부를 판단할 수 있습니다. 두 포인터 기법은 추가적인 공간을 사용하지 않아 공간 복잡도도 O(1)입니다.

면접관님, 대규모 데이터셋에서 동적 계획법을 사용할 때 DP 테이블 크기나 상태 전이 비용 때문에 성능 문제가 발생할 수 있습니다. 이를 해결하기 위한 고급 최적화 기법들이 있습니다.

먼저 Convex Hull Trick은 점화식이 dp[i] = min(a[j] * b[i] + c[j]) 형태일 때 유용합니다. 각 j에 대해 직선 y = a[j] * x + c[j]을 그리고, 이 직선들의 lower envelope를 유지하면서 최적의 j를 빠르게 찾습니다.

Divide and Conquer Optimization은 점화식이 dp[i][j] = min(dp[i-1][k] + cost(k, j)) 형태이고, cost(k, j)가 Monge array 조건을 만족할 때 사용할 수 있습니다. 이 경우, 최적의 k가 단조 증가한다는 성질을 이용하여 분할 정복 방식으로 문제를 해결합니다.

Monotonic Queue Optimization은 점화식이 dp[i] = min(dp[j] + cost(i, j)) 형태이고, j의 범위가 i에 따라 단조적으로 변할 때 효과적입니다. 큐를 사용하여 dp[j] + cost(i, j) 값이 최소가 될 가능성이 없는 j들을 제거하면서 최적값을 찾습니다. 예를 들어, 슬라이딩 윈도우 최솟값 문제에 적용할 수 있습니다.

Dinic 알고리즘은 Edmonds-Karp나 Ford-Fulkerson보다 실제 환경에서 훨씬 효율적인 이유는, 한 번의 레벨 그래프 구성으로 여러 개의 증강 경로를 동시에 찾고 처리하기 때문입니다.

핵심 단계는 다음과 같습니다.

먼저 BFS를 이용해 소스에서 싱크까지의 최단 경로 길이를 기준으로 레벨 그래프를 구성합니다. 이 레벨 그래프는 각 노드의 소스로부터의 최단 거리를 나타냅니다.

이후 DFS를 이용해 레벨 그래프 상에서 블로킹 플로우를 찾습니다. 블로킹 플로우란, 더 이상 레벨 그래프 상에서 소스에서 싱크로 도달할 수 없을 때까지 모든 가능한 증강 경로를 통해 최대한의 유량을 흘려보내는 것을 의미합니다.

이러한 레벨 그래프 구성과 블로킹 플로우 탐색 과정을 반복하면, 각 단계마다 잔여 네트워크에서 최단 경로를 따라 유량을 증가시키므로 전체적인 수렴 속도가 빨라져 효율성이 높아집니다.

면접관님, 대용량 텍스트 데이터에서 반복되는 부분 문자열을 찾거나 최장 공통 부분 문자열을 찾는 문제에 Suffix Array와 Suffix Tree를 활용할 수 있습니다.

Suffix Array는 문자열의 모든 접미사를 사전순으로 정렬한 배열입니다. LCP(Longest Common Prefix) 배열과 함께 사용하면 반복되는 부분 문자열이나 최장 공통 부분 문자열을 효율적으로 찾을 수 있습니다. 구현이 비교적 간단하고 공간 효율성이 좋습니다. 시간 복잡도는 정렬 알고리즘에 따라 O(n log n) 정도입니다.

Suffix Tree는 문자열의 모든 접미사를 트리 형태로 표현한 자료구조입니다. 개념적으로 강력하며 다양한 문자열 문제에 유연하게 적용할 수 있습니다. 하지만 구현이 복잡하고 Suffix Array보다 공간을 더 많이 사용합니다. 시간 복잡도는 O(n)입니다.

특정 문제에 따라 장단점이 있습니다. 공간 효율성이 중요한 경우에는 Suffix Array가 유리하고, 복잡한 문자열 패턴 분석이 필요한 경우에는 Suffix Tree가 더 적합할 수 있습니다. 예를 들어, 게놈 분석과 같이 매우 큰 데이터셋에서는 Suffix Array의 공간 효율성이 큰 장점이 됩니다.

Line Sweep 알고리즘은 평면 상의 선분 교차 문제를 효율적으로 해결하는 방법입니다. 핵심 아이디어는 가상의 수직선(sweep line)을 왼쪽에서 오른쪽으로 쓸면서 지나가면서, 이 선에 걸리는 선분들을 관리하는 것입니다.

선분이 시작되거나 끝나는 점, 또는 교차점이 발생할 가능성이 있는 점들을 이벤트 포인트로 관리하고, 이 이벤트들을 x좌표 기준으로 정렬합니다. Sweep line이 이벤트 포인트를 지날 때마다, 해당 위치에서 활성화되는 선분들을 균형 이진 탐색 트리(BST)에 삽입하거나 삭제합니다.

BST는 sweep line과 교차하는 선분들을 y좌표 순서대로 정렬된 상태로 유지합니다. 새로운 선분이 삽입될 때, BST에서 인접한 선분들과 교차하는지 확인하여 교차점을 찾습니다.

시간 복잡도는 이벤트 포인트를 정렬하는 데 O(N log N), 각 이벤트 포인트에서 BST 삽입/삭제/탐색에 O(log N)이 소요됩니다. 총 이벤트 수는 선분 시작/끝 점 N개와 교차점 K개, 즉 N+K개이므로, 전체 시간 복잡도는 O((N+K) log N)이 됩니다. BST를 사용하여 활성 선분들을 효율적으로 관리함으로써 불필요한 비교를 줄이는 것이 핵심입니다.

Segment Tree Beats는 일반 세그먼트 트리로는 어려운 복잡한 구간 업데이트를 효율적으로 처리하는 기법입니다. 핵심은 '구간 내 최댓값'과 '두 번째 최댓값' 같은 메타데이터를 활용하는 것입니다. 예를 들어, 구간 내 모든 값을 x로 클램핑할 때, 구간의 최댓값이 이미 x보다 작거나 같다면 자식 노드로 내려갈 필요 없이 해당 노드에서 처리가 완료됩니다. 또한, 구간 최댓값을 x로 변경하는 경우에도, 최댓값이 x보다 크고 두 번째 최댓값이 x보다 작다면, 최댓값만 x로 변경하고 나머지는 그대로 두는 방식으로 효율성을 높입니다. 이러한 최적화는 구간 내 값들의 분포나 업데이트 연산의 특성이 특정 조건을 만족할 때 가능하며, 주로 구간 최댓값 변경, 구간 합, 구간 최솟값 갱신 등 다양한 문제에 적용될 수 있습니다.

면접관님, 확률적 알고리즘에 대한 질문 감사합니다. Monte Carlo 알고리즘과 Las Vegas 알고리즘은 모두 무작위성을 활용하지만, 정확성과 실행 시간 측면에서 차이가 있습니다.

Monte Carlo 알고리즘은 항상 결과를 빠르게 반환하지만, 그 결과가 정확하다는 보장이 없습니다. 즉, 틀릴 확률이 존재합니다. 반면에 Las Vegas 알고리즘은 항상 정확한 결과를 반환하지만, 실행 시간이 얼마나 걸릴지 예측하기 어렵습니다. 최악의 경우 매우 오래 걸릴 수도 있습니다.

예를 들어, 스트리밍 데이터에서 특정 패턴을 찾는다고 가정해 보겠습니다. Monte Carlo 알고리즘은 빠른 속도로 패턴을 찾아내지만, 가끔 오탐을 할 수 있습니다. 반면 Las Vegas 알고리즘은 정확하게 패턴을 찾아내지만, 데이터 스트림의 특성에 따라 시간이 오래 걸릴 수 있습니다. 암호화 분야에서는 소수 판별에 Las Vegas 알고리즘이 사용될 수 있습니다. 항상 정확한 답을 내야 하기 때문입니다.

어떤 알고리즘을 선택할지는 문제의 요구 사항에 따라 달라집니다. 정확성이 매우 중요하다면 Las Vegas 알고리즘을, 빠른 속도가 중요하다면 Monte Carlo 알고리즘을 선택하는 것이 좋습니다.

NP-hard 문제에서 최적해를 다항 시간 내에 찾기 어려울 때, 근사 알고리즘은 현실적인 대안입니다. TSP의 경우, 삼각 부등식이 성립하는 그래프에서 최소 신장 트리(MST)를 구한 후, 이를 순회하는 방식으로 2배 근사 알고리즘을 설계할 수 있습니다. Vertex Cover 문제에서는 탐욕 알고리즘이나 선형 계획 완화 기법을 활용하여 근사해를 찾습니다.

근사 비율은 알고리즘이 찾은 해의 비용이 최적해의 비용 대비 얼마나 나쁜지를 나타내는 척도입니다. 예를 들어, 근사 비율이 'c'라면, 알고리즘이 찾은 해의 비용은 최적해 비용의 최대 'c'배까지 허용된다는 의미입니다. 이는 알고리즘의 성능을 정량적으로 평가하고 보장하는 데 매우 중요합니다. 근사 비율 증명은 보통 알고리즘의 해와 최적해 사이의 관계를 수학적으로 분석하여 이루어집니다.