이 글은 게일 라크만 맥도웰 저자의 ‘코딩인터뷰 완전분석’을 읽으며, 깨달은 사실과 내용을 정리하는 글입니다.
자세한 내용이 궁금하다면 http://www.yes24.com/Product/Goods/44305533 에서 책을 구매하시면 좋겠습니다.

많은 테크 회사들이 면접에서 기술적 문제를 출제하고, 지원자가 어떻게 해결하는지 확인합니다.

실제로 네카라쿠배 등의 기업에서 면접 문제를 출제합니다.

이번 포스팅에서는 이 문제들을 어떻게 접근해야하고 해결해야하는지 그리고 면접관에게 어떻게 설명해야하는지에 대해 정리해보겠습니다.

준비하기

많은 지원자들이 공부를 한답시고 문제와 답을 읽기만 하곤 합니다.

하지만 이러한 방식의 학습은 도움이 되지 않는다고 저자가 이야기합니다.

중요한 것은 문제를 직접 푸는 훈련을 해야한다는 것입니다.

어떻게 이런 훈련을 해야하는지 정리해보면 아래와 같습니다.

1. 직접 풀도록 노력하라
   • 어려운 문제를 접하더라도, 일단 포기하지 말고 풀어보는게 좋습니다.
   • 그리고 문제를 풀때는, 공간 및 시간 효율에 대해서도 반드시 생각해야 합니다.
2. 코드를 종이에 적으라
   • IDE의 편리한 기능은 오히려 학습을 방해할 수 있습니다.
   • 실제 면접은 IDE로 진행되지 않으므로, 종이에 코드를 작성하는 연습을 하면 효과적입니다.
3. 코드를 테스트하라
   • 기본 조건, 오류 발생 조건, 엣지 케이스 등 모두 경우에 대해 테스트해야 합니다.
4. 종이에 적은 코드를 그대로 컴퓨터로 옮긴 뒤, 실제로 실행해 보라
   • 코드를 종이에 적으며 여러 실수를 했을 것입니다. 이 실수들을 정리해두고, 실제 면접을 대비합시다.

추가로 가상 면접을 가능한 많이 해보는 것이 도움됩니다.

기본적으로 알고 있어야 하는 것들

면접 문제를 해결하기 위해서, 고급 지식들을 동반해야 하는 경우는 매우 적습니다.

하지만 기본적인 CS나 개발 지식은 갖추어야 합니다. 즉, 기본기는 필수입니다.

알아두어야 하는 기본 지식은 아래와 같습니다.

자료구조	알고리즘	개념
연결리스트	너비 우선 탐색	비트 조작
트리, 트라이, 그래프	깊이 우선 탐색	메모리 (스택 vs 힙)
스택 & 큐	이진 탐색	재귀
힙(Heaps)	병합 정렬 (Merge Sort)	동적 프로그래밍
Vector / ArrayList	퀵 정렬	big-O 시간 & 공간
해시테이블

실제로 많은 면접에서 자료구조나 알고리즘이 중요하게 사용되므로, 직접 종이에 구현해보고, 컴퓨터로 실제로 동작시켜보는 것이 아주 좋습니다.

특히 해시테이블에 대해 잘 알아둡시다. (자주 사용됩니다.)

2의 승수표

2의 승수를 어느정도 외워둔다면, 규모 확장성과 메모리 제한 관련 문제를 풀 때 유용하게 사용될 수 있습니다.

X	2^X	근사치	메모리 요구량
7	128
8	256
10	1,024	1,000 (천)	1K
16	65,536		64K
20	1,048,576	1,000,000 (백만)	1MB
30	1,073,741,824	1,000,000,000 (십억)	1GB
32	4,294,967,296		4GB
40	1,099,511,627,776	1,000,000,000,000 (조)	1TB

실제 문제 풀어보기

면접 문제 접근방법

저자가 제시하는 문제 접근 방법은 아래와 같습니다.

1. 듣기
2. 예제 만들어보기
3. 무식하게 풀어보기
4. 최적화
5. 검토하기
6. 구현하기
7. 테스트

그리고 중요한 것은 이 모든 과정을 면접관에게 자세히 설명하는 것입니다.

면접관은 지원자가 어떻게 문제를 풀고 있는지 궁금해합니다.

각 단계에 대해 좀 더 자세히 알아보겠습니다.

1. 듣기

면접관이 제시하는 문제와 관련된 모든 정보를 잘 들어야 합니다.

모든 정보를 활용해서 문제를 해결해야 할 수도 있습니다.

그리고 확실히 듣지 못했거나, 이해가 되지 않는 부분은 면접관에게 질문하여 명확히 짚고 넘어가야 합니다.

하나 더 알아두어야 하는 것은, 문제를 푸는 데 아무 영향도 끼치지 않는 정보를 제공하는 경우는 거의 없다는 것입니다.

• “정렬된 배열 두개가 주어졌을 때, …”
  • 여기에서 캐치해야 하는 부분은 배열이 정렬되어 있다는 것 입니다.
  • 최적 알고리즘을 구할 때, 데이터가 정렬된 상태인 경우와 아닌 경우는 아예 다른 접근방식이 필요합니다.
• “서버에서 반복적으로 수행되는 알고리즘을 설계하려고 하는데, …”
  • 이 경우에는 반복적으로 수행 이라는 정보가 중요합니다.
  • 반복적으로 실행되는 경우와 한 번만 실행되는 경우가 매우 다르다는 의미이기도 합니다.

모든 정보를 기억하기 힘들다면, 화이트보드 등에 적어두는 것도 매우 좋습니다.

2. 예제 만들어보기

직접 예제를 만들어보고, 화이트보드에 작성해둔 상태에서 문제를 풀는 것이 좋습니다.

예제를 만들 때는 아래 3가지를 유의해야 합니다.

• 명확한 예제를 쓰라
  • 문제에 맞는 실제 숫자와 문자열을 사용하는 것이 좋습니다.
• 충분히 큰 예제를 쓰라
  • 대부분 예제의 크기가 매우 작을 것입니다.
  • 충분히 큰 예제를 사용해야 유의미한 패턴을 찾아내기 유리합니다.
• 특별한 예제를 지양하라
  • 무심코 특별한 경우의 예제를 만들기 쉽습니다. 이를 주의합시다.
  • 이 경우에도 유의미한 패턴을 찾아내기 어렵습니다.

3. 무식하게 풀어보기

예제가 완성됐다면, 무식한 방법 (Brute Force) 로 먼저 시도해봅시다.

처음으로 만든 알고리즘이 형편없더라도 괜찮습니다. 중요한 것은 알고리즘의 시간 및 공간복잡도를 설명한 뒤, 개선하는 것입니다.

알고리즘 최적화의 시작점이 바로, 완전 탐색같은 무식한 방법임을 기억합시다.

4. 최적화

이제 최적화 작업을 해봅시다.

아래 방법을 활용할 수 있습니다.

• 간과한 부분이 있는지 생각해봅니다. 보통의 경우, 문제에서 언급된 정보를 모두 사용해야 합니다.
• 새로운 예제를 만들어 봅니다.
• 잘못된 방법으로 풀어 본 뒤, 왜 해당 알고리즘이 틀렸는지 생각해 봅시다. 그리고 발견된 문제를 해결해봅시다.
• 시간과 공간의 TradeOff 관계를 고려해 균형을 맞춰봅시다. 이때 해시테이블을 사용하면 유용합니다.
• 정보를 미리 계산해두는 것을 고려합니다.
• 가능한 최선의 수행 시간(BCR)이 무엇인지 생각해봅니다.

추가로 저자가 제시하는 BUD 최적화가 있습니다. BUD와 BCR은 나중에 다루도록 하겠습니다.

5. 검토하기

최적 알고리즘을 완성했다고 바로 코딩에 뛰어드는 것은 좋지 않습니다.

잠시 생각하며 알고리즘에 대한 이해를 확실히 해두고, 코딩을 해야 합니다.

거의 완벽에 가까운 상태로 만든 뒤, 실제 코딩에 들어갑시다.

의사코드를 사용하는 것이 좋을 수도 있지만, 반드시 그렇지만은 않을 수 있습니다. 의사코드 대신 간단한 문장하나로 표현할 수도 있습니다.

6. 코드 작성하기

이 단계에서 중요한 것은 보기 좋은 코드로 만드는 것입니다.

이를 위한 방법은 아래와 같습니다.

• 모듈화된 코드 사용하기
  • 이를 통해, 코딩 과정을 좀 더 단순화시킬 수 있습니다.
  • 예를 들어, 배열을 정렬하는 코드를 모두 작성하는 것이 아니라, sort(int[]) 이라는 함수가 존재한다고 가정할 수 있습니다.
  • 필요하다면 모든 코딩을 마친 후, 추상화시킨 부분을 구현하면 됩니다.
• 에러를 검증하기
  • 면접관에 따라 에러나 예외를 잘 처리하는 것이 중요할 수 있습니다.
  • TODO를 코드에 집어넣고, 해당 부분에서 어떤 검증을 하겠다고 이야기하는 수준으로 넘어갈 수 있습니다.
• 필요한 경우에 다른 클래스나 구조체를 사용하기
  • 모듈화된 코드를 사용하는 것과 마찬가지로, 특정 클래스나 구조체가 존재한다고 가정하고 코딩할 수 있습니다.
• 좋은 변수명을 사용하기
  • 의미있는 변수명을 사용해서, 코드 가독성을 높힐 수 있습니다.

만약 코드에서 리팩터링해야 할 부분이 발견되면, 먼저 면접관에게 리팩토링을 진행해도 되는지 물어보고 진행하면 됩니다.

7. 테스트

실제 개발과 마찬가지로, 면접에서도 테스트없이 코드를 제출하면 안됩니다.

아래 순서대로 테스트를 진행하면 좋습니다.

1. 개념적 테스트
   • 코드 리뷰하듯, 자세히 코드를 훑으며 테스트
2. 특이하거나 표준적이지 않은 코드 위주로 디버깅
   • 코드에서 평소와 다르게 돌아가는 부분을 유심히 봅시다. 예를 들어, for(int i = 0) 이 아니라 for(int i = 2) 와 같은 부분이 존재한다면, 해당 부분에서 오류를 발생시킬 가능성이 높습니다.
3. 실수가 날만한 부분 조사
   • 예를 들어, 재귀함수의 탈출조건이나 null 등이 있습니다.
4. 작은 크기의 테스트케이스로 테스트
   • 최대한 빠르게 코드를 동작시켜볼 수 있는 작은 크기의 테스트케이스를 먼저 확인해봅니다.
5. 특이하거나 극단적인 테스트케이스로 테스트

최적화 기법 - BUD

BUD 란?

저자가 제시하는 최적화 문제를 푸는 방법입니다.

BUD의 각 약자는 아래를 의미합니다.

• B : 병목현상 (Bottleneck)
• U : 불필요한 작업 (Unnecessary Work)
• D : 중복되는 작업 (Duplicated Work)

알고리즘이 비효율적으로 동작하는 가장 흔한 이유가 바로 이 세가지입니다.

무식한 방법으로 도출된 해결책을 위 3가지 관점에서 살펴보며 개선해보면 좋습니다.

각 요소에 대해 좀 더 자세히 알아볼까요?

병목 (Bottleneck) - 개념

병목현상이란, 알고리즘에서 전체 수행 시간을 잡아먹는 부분을 의미합니다.

병목이 발생하는 이유는 크게 아래 두가지입니다.

• 어떤 부분 때문에 알고리즘이 느려지는 경우
  • 예를 들어 A단계와 B단계로 이루어진 알고리즘이 있고, A 단계에선 O(nlogn) 이 소요되고, B 단계에선 O(n) 이 소요된다고 해봅시다. 총 시간복잡도는 O(nlogn) 입니다.
    이 경우, B 단계의 시간복잡도를 아무리 줄이더라도 총 시간복잡도가 그대로 O(nlogn) 입니다. 다시말해, B 단계의 시간복잡도를 O(1) 로 만들더라도 총 시간복잡도는 줄어들지 않습니다.
    따라서 A 단계가 병목지점이 되므로, A 단계의 시간복잡도를 줄여야 총 시간복잡도가 줄어듭니다.
• 반복적으로 수행하는 부분이 여러 개 있는 경우
  • 예를 들어 검색을 여러번 수행한다면, 이 부분의 시간복잡도를 줄이는게 효과적입니다.
    만약 시간복잡도가 O(n) 인 검색 연산을 n번 반복한다면, 총 시간복잡도는 O(n^2) 입니다.
    이 경우 검색 연산의 시간복잡도를 O(1) 로 줄이면, 총 시간복잡도가 O(n) 으로 감소됩니다.

그럼 병목지점을 찾아서 개선하는 예제 문제를 한번 풀어볼까요?

병목 (Bottleneck) - 예제 문제 풀이

[문제]
서로 다른 정수로 이루어진 배열이 있을 때, 두 정수의 차이가 k인 쌍의 개수를 세라.
예를 들어, 배열 {1, 7, 5, 9, 2, 12, 3} 이 존재하고 k = 2 라면, 두 정수의 차이가 2인 쌍은 아래와 같이 4개가 존재한다.
(1,3), (3,5), (5,7), (7,9)

먼저 무식한 방법으로 풀어보겠습니다.

1. 가장 앞에서부터 임의의 원소 a 를 선택한다.
2. a 앞에 있는 다른 원소 b 를 선택한다.
3. |a-b| == k 를 만족한다면, 정답 변수에 저장한다.
4. b 를 배열의 끝까지 선택하며 2번 3번 단계를 반복한다.
5. a 를 배열의 끝까지 선택하며 전체를 반복한다.

이 부분에서 병목지점을 찾아볼까요?

이 알고리즘을 2개 단계로 나눌 수 있습니다.

• a 와 b 를 선택하는 단계 ⇒ 시간복잡도 O(n^2)
• |a-b| == k 인지 확인하는 단계 ⇒ 시간복잡도 O(1)

총 시간복잡도는 O(n^2) * O(1) = O(n^2) 입니다.

시간복잡도를 따져봤을 때, 두 번째 단계를 아무리 줄이더라도 전체 시간복잡도는 줄어들지 않는다는 것을 알 수 있습니다. (물론 O(1) 에서 더이상 줄이는게 불가능하기도 합니다.)

따라서 우리는 a 와 b 를 선택하는 단계의 시간복잡도를 개선해야합니다.

그럼 어떻게 줄일 수 있을까요?

이진 탐색을 통해 개선이 가능합니다.

1. 주어진 배열을 오름차순으로 정렬한다.
2. 가장 앞에서부터 임의의 원소 a 를 선택한다.
3. 이진 탐색을 통해 |a-b| == k 를 만족시키는 b 를 찾는다.
4. a 를 배열의 끝까지 선택하며 반복한다.

시간복잡도를 정리해보면 아래와 같습니다.

• 배열을 정렬하는 단계 ⇒ 시간복잡도 O(nlogn)
• a 와 b 를 선택하는 단계 (이진탐색을 n번 반복) ⇒ 시간복잡도 O(nlogn)
• |a-b| == k 인지 확인하는 단계 ⇒ 시간복잡도 O(1)

이 경우 총 시간복잡도는 O(nlogn) + {(nlogn) * O(1)} = O(nlogn) 이 됩니다.

HashSet을 사용해서 좀 더 개선해볼 수 있습니다.

HashSet을 통해, a-b == k 나 b-a == k 를 만족시키는 b 를 O(1) 만에 찾을 수 있습니다.

1. 모든 원소를 HashSet에 add한다.
2. 가장 앞에서부터 임의의 원소 a 를 선택한다.
3. a-k 나 a+k 값이 HashSet에 존재하는지 확인한다.
4. a 를 배열의 끝까지 선택하며 반복한다.

시간복잡도는 아래와 같습니다.

• HashSet에 모든 원소 저장 ⇒ 시간복잡도 O(n)
• a 를 순차적으로 선택 ⇒ 시간복잡도 O(n)
• 만족하는 b 를 HashSet에서 찾기 ⇒ 시간복잡도 O(1)

총 시간복잡도는 O(n) + {O(n) * O(1)} = O(n) 입니다.

이렇게 병목지점을 찾아서 개선하며, 최종적으로 알고리즘을 기존 O(n^2) 에서 O(n) 으로 최적화했습니다.

불필요한 작업 (Unnecessary Work) - 개념

이번에는 알고리즘에서 굳이 수행하지 않아도 되는 부분을 제거하여, 전체 효율을 개선하는 방법에 대해 알아보겠습니다.

바로 예제를 통해 알아볼까요?

불필요한 작업 (Unnecessary Work) - 예제 문제 풀이

[문제] a, b, c, d가 1 에서 1000 사이에 있는 정수 값 중 하나일 때, a^3 + b^3 = c^3 + d^3 을 만족하는 모든 자연수를 출력하라.

이번에도 역시 가장 단순한 방법으로 풀어볼까요?

모든 a, b, c, d마다 a^3 + b^3 = c^3 + d^3 를 만족하는지 확인하면 됩니다.

for (int a = 1; a <= 1000; a++)
	for (int b = 1; b <= 1000; b++)
		for (int c = 1; c <= 1000; c++)
			for (int d = 1; d <= 1000; d++)
				if (cal(a, b, c, d) == true) print(a, b, c, d) //cal 함수가 a^3 + b^3 = c^3 + d^3 을 만족하는지 확인

총 4번의 반복문으로 시간복잡도는 O(n^4) 입니다.

어떻게 개선할 수 있을까요?

a, b, c가 결정되었다면, 굳이 각 d를 확인할 필요가 없습니다.

a^3 + b^3 - c^3 = d^3 이기 때문이죠!

따라서 아래 코드로 개선할 수 있습니다.

for (int a = 1; a <= 1000; a++)
	for (int b = 1; b <= 1000; b++)
		for (int c = 1; c < a^3 + b^3; c++)
			print(a, b, c, cal(a, b, c)) //cal 함수가 d를 반환

이 경우, 시간복잡도는 O(n^3) 이 됩니다.

d 를 1~1000까지 반복하는 불필요한 과정을 제거함으로써, 알고리즘의 시간복잡도를 O(n^4) 에서 O(n^3) 으로 개선할 수 있습니다.

중복되는 작업 (Duplicated Work) - 개념

중복되는 작업을 제거하여, 알고리즘을 최적화하는 방법에 대해 알아봅시다.

역시 바로 예제를 통해 설명하겠습니다.

중복되는 작업 (Duplicated Work) - 예제 문제 풀이

위에서 사용한 예제 문제를 다시 가져와 개선해봅시다.

0~1000까지의 d 마다 반복하는 작업을 제거하여, 알고리즘을 개선했었습니다.

사실 중복되는 작업이 존재하기 때문에, 아직 개선될 여지가 있습니다.

굳이 각 (a,b) 마다 (c,d) 를 찾아내야할까요?

각 쌍의 계산 결과를 미리 계산해서 HashMap에 저장해두고 사용하면 O(n^2) 만에 해결할 수 있습니다.

1. 1~1000 에 대해서 a^3 + b^3 의 결과를 HashMap에 저장한다.
   이때, Key는 결과값이고 Value는 (a,b) 이다.
2. 1~1000 에 대해서 a^3 + b^3 마다, 그 결과값을 HashMap에서 찾아 (c,d)로 취급한다.

코드로 나타내면 아래와 같습니다.

HashMap<Integer, List<int[]>> hashMap = new HashMap<>();

//1번 절차
for (int a = 1; a <= 1000; a++) {
	for (int b = 1; b <= 1000; b++) {
		int key = a^3 + b^3;
		if (hashMap.containsKey(key)) {
			hashMap.get(key).add(new int[] {a, b});
		} else {
			List<int[]> list = new ArrayList<>();
			list.add(new int[] {a, b});
			hashMap.put(key, list);
		}
	}
}

//2번 절차
for (int a = 1; a <= 1000; a++) {
	for (int b = 1; b <= 1000; b++) {
		List<int[]> cdList = hashMap.get(a^3 + b^3);
		for (int[] cd : cdList)
			print(a, b, cd[0], cd[1]);
	}
}

기존 알고리즘에서 중복되는 작업이 바로 각 (a,b)마다 (c,d)를 찾는 것입니다.
왜냐하면 각 (a,b)를 (c,d)로 취급하는 것이 가능하기 때문에, (c,d)를 구하기 위해 계산하는 작업을 (a,b)를 계산하며 이미 수행했다고 볼 수 있기 때문입니다.

따라서 미리 각 (a,b)마다 결과값을 미리 저장해두고, 그대로 (c,d)로 사용하면 됩니다.

결론적으로 기존 O(n^4) 에서 O(n^2) 로 개선할 수 있습니다.

최적화 기법 - 직접 풀어보기 DIY (Do It Yourself)

직접 풀어보기 DIY (Do It Yourself) 기법이란?

이 방법은 인간의 직관력을 통해 최적화하는 기법입니다.

인간의 직관력을 활용한다… 이게 정확히 무슨말일까요?

저자가 말하는 예시는 아래와 같습니다.

• 문제 상황 : 이진탐색을 배우지 않은 상태에서 ‘정렬된 배열에서 원소를 찾는 문제’를 처음 접했다.
• 정답 : 이진탐색으로 찾아야 한다.
• 실제 : ‘아하! 중간에 있는 원소랑 다른 원소들을 비교한 뒤 절반씩 나눠 가면 되겠구나’ 라고 생각하긴 어렵다.

만약 이것을 실생활에 적용해보면 어떨까요?

• 문제 상황 : ‘알파벳 순으로 정렬된 수첩에서 Peter 라는 이름을 찾기’
• 실제 : ‘대충 중간부터 확인해보고, Peter라는 이름을 비교해나가며 찾아봐야겠다’

실제로 이런 문제가 있다면, 이런 식으로 찾을 가능성이 높습니다.

그리고 이것이 바로 이진탐색이죠!

따라서 저자는 면접 문제 질문을 받으면, 실제 예제를 통해 직관적으로 문제를 풀어 나가려는 노력을 해야 한다고 합니다.

예제 문제 풀이

그럼 한번 예제를 통해 적용해볼까요?

[문제]
길이가 작은 문자열 s와 길이가 긴 문자열 b가 주어졌을 때, 문자열 s의 순열 중 길이가 s의 길이와 같은 순열을 문자열 b에서 찾는 알고리즘을 설계하라.
문자열 b 상의 각 순열의 시작점을 출력하면 된다.

먼저 가장 단순한 방법으로 풀어보겠습니다.

1. 문자열 s의 순열 중, s의 길이와 같은 순열을 모두 찾는다.
2. 각 순열에 대해, 문자열 b에 존재하는지 찾아본다.

이 경우 시간복잡도는 총 O(s! * b) 입니다. (순열의 개수 = s!)

s의 길이가 14인 경우, 총 870억개 이상의 순열이 존재합니다. 즉, 매우 비효율적입니다.

그렇다면 우리가 직접 순열을 찾아볼까요?

• 문자열 s : abbc
• 문자열 b : cbabadcbbabbcbabaabccbabc

직접 하나씩 찾아보면, 문자열 b에 아래와 같은 순열을 찾을 수 있습니다.

cbab , cbba , abbc , …

어떻게 찾았나요? 보통 아래와 같은 방법 중 하나를 택했을 것입니다.

• s의 길이가 4이므로 b를 4개씩 끊어서 차례로 살펴본 뒤, s의 순열을 만족하는지 확인한다.
• b의 문자를 앞에서부터 차례로 살펴보면서, s에 속한 문자가 보일 때마다 그다음 문자를 포함한 4개의 문자열이 s의 순열을 만족하는지 확인한다.

제 경우, 아래와 같은 방법을 사용했습니다.

• b의 문자를 앞에서부터 차례로 살펴보면서, 길이가 4인 부분 문자열의 알파벳 개수를 센다.
  만약 알파벳 개수가 s의 알파벳 개수와 같다면 정답으로 처리한다.

여기서 핵심은 그 누구도 문자열 s의 모든 순열을 구해놓고, 문자열 b를 탐색한게 아니라는 것입니다.

즉 문제를 풀 때, 문제에 적합하고, 크기가 충분히 크며, 구체적인 예제를 바탕으로 직관적으로 직접 문제를 풀어 보면, 그 해답을 의외로 쉽게 얻을 수 있다는 것입니다.

최적화 기법 - 초기 사례(base case)로부터 확장하기

초기 사례로부터 확장하는 방법

우선 초기 사례(n = 1 과 같은)에 대한 문제를 푼 뒤, 거기서부터 해법을 확장해 나가는 방법입니다.

바로 예시를 통해 알아보겠습니다.

예제 문제 풀이

[문제]
문자열의 모든 순열을 계산하는 알고리즘을 설계하라.
문제를 단순화하기 위해, 모든 문자는 문자열 내에서 고유하게 등장한다고 가정한다.

이 문제를 풀기 위해, 가장 먼저 문자열의 길이가 1인 경우를 해결해봅시다.

• “a” → {“a”}

그 다음은 문자열의 길이가 2인 경우를 해결해봅니다.

• “ab” → {”ab”, “ba”}

문자열의 길이가 3인 경우에는 어떻게 될까요?

그냥 가능한 모든 부분에 “c”를 넣으면 됩니다.

즉 “ab” 의 앞·중간·뒤에 “c”를 넣으면 됩니다. 그리고 “ba”에도 똑같이 “c”를 넣으면 정답을 구할 수 있다는 것을 알 수 있습니다.

이 알고리즘은 재귀 함수를 통해 구현할 수 있습니다.

String s = "abc";
HashSet<String> resultSet = new HashSet<>();

resultSet.add("");

public void solution(int depth) {
	if (depth == s.length()) {
		return;
	}

	//item별로 문자 삽입 후 저장
	HashSet<String> tmpSet = new HashSet<>();
	char c = s.charAt(depth);
	for (String item : resultSet) {
		for (int u = 0; u <= item.length(); u++) {
			StringBuilder sb = new StringBuilder(item);
			sb.insert(u, c);
			tmpSet.add(sb.toString());
		}
	}

	resultSet = tmpSet;

	solution(depth + 1);
}

초기 사례로부터 확장된 알고리즘은 자연스럽게 재귀 알고리즘으로 구현되는 경우가 많다는 것을 알아둡시다.

가능한 최선의 수행 시간 (Best Conceivable Runtime - BCR)

가능한 최선의 수행 시간 (BCR)이란?

BCR이란, 어떤 문제를 푸는 데 여러분이 상상할 수 있는 모든 해법 중 수행 시간이 가장 빠른 것을 의미합니다.

예를 들어 길이가 A와 B인 배열 두 개가 주어졌을 때, 두 배열에 공통으로 들어 있는 원소의 개수가 몇 개인지 세는 경우를 생각해봅시다.
이 경우 각 배열의 원소를 적어도 한번씩은 확인해봐야하기 때문에, 어떤 알고리즘이든 O(A+B) 보다 빠를 수는 없습니다. 따라서 이 문제의 BCR은 O(A+B) 입니다.

BCR과 최선의 경우의 수행 시간은 아무런 연관관계가 없음에도 주의합시다.

• BCR : 모든 해법 중 가장 빠른 알고리즘의 시간복잡도
• 최선의 경우의 수행 시간 : 특정 알고리즘이 가장 빠르게 동작하는 case의 시간복잡도

또한 BCR을 반드시 만족할 필요는 없습니다. 단순히 어떤 알고리즘도 이보다 나을 순 없다고 알려주는 역할만 할 뿐입니다.

그럼 예제를 통해 더 알아볼까요?

BCR 예제

[문제]
정렬된 배열 두 개가 주어졌을 때, 공통으로 들어 있는 원소의 개수를 찾으라.
두 배열의 길이는 같고 하나의 배열 안에서 동일한 원소는 하나만 존재한다.

예제를 하나 만들어봅시다.

• A : 13 27 35 40 49 55 59
• B : 17 35 39 40 55 58 60

이 문제를 가장 단순히 풀어보면 아래와 같습니다.

1. A의 특정 원소를 선택한다.
2. B의 모든 원소를 확인하며, A의 해당 원소와 동일한지 확인한다.
3. 모든 A의 원소에 대해 반복한다.

시간복잡도는 O(n^2) 이 됩니다.

이 문제의 BCR은 O(n) 입니다. 왜냐하면, A와 B의 원소를 적어도 한번씩은 살펴봐야하기 때문에 O(2n) 이 되기 때문입니다.

이를 통해, ‘현재 알고리즘의 시간복잡도는 O(n^2) 이고 BCR은 O(n) 이므로, 좀 더 개선의 여지가 있지 않을까?’ 라는 생각을 해볼 수 있습니다.

위 알고리즘의 시간복잡도를 분석해보면 아래와 같습니다.

• 모든 A의 원소를 선택한다 → O(n)
• A의 특정 원소가 B에 존재하는지 확인한다 → O(n)

여기서 개선할 수 있는 부분은 어떤 곳일까요?

BCR을 도출할 때, 우리는 ‘적어도 A와 B의 모든 원소를 살펴봐야 한다’고 했습니다.
이 말은 즉, 첫번째 단계는 줄일 수 없다는 것과 동일합니다.

따라서 우리는 두번째 단계 (A의 특정 원소가 B에 존재하는지 확인) 의 시간복잡도를 줄여야 합니다.

HashSet을 사용하면, O(1) 만에 탐색할 수 있습니다.

1. HashSet에 B의 모든 원소를 넣는다.
2. A의 특정 원소를 선택한다.
3. HashSet에 A의 해당 원소가 있는지 확인한다.

이 경우, 시간복잡도는 아래와 같습니다.

• B의 모든 원소를 HashSet에 넣는다 → O(n)
• A의 모든 원소를 선택한다 → O(n)
• A의 특정 원소가 HashSet에 있는지 확인한다 → O(1)

따라서 총 시간복잡도는 O(n) 이 되고 BCR이 O(n) 이므로, 더 이상 개선의 여지가 없습니다.

하지만 면접관이 ‘더 개선할 수 있을까요?’ 라고 물어볼 수 있습니다.

이 경우 시간복잡도는 더이상 개선할 수 없으므로, 공간복잡도를 개선하라는 의미입니다.

우리가 문제에서 놓친 정보가 무엇일까요?

바로 ‘배열이 모두 정렬되어 있다는 것’입니다.

따라서 아래와 같은 방식을 통해, HashSet을 사용하지 않고 (즉 추가공간을 사용하지 않고) O(n) 시간만에 정답을 구할 수 있습니다.

1. A의 가장 앞 원소를 선택한다.
2. B의 가장 앞 원소부터 해당 A 원소와 동일한지 비교한다.
3. 만약 동일하다면, 정답을 출력하고 다음 B 원소를 탐색한다.
4. 만약 A 원소보다 B 원소가 작다면, 다음 B 원소를 탐색한다.
5. 만약 A 원소보다 B 원소가 크다면, B 탐색을 중단한다.
6. A의 다음 원소를 선택하고, 중단된 B 원소부터 다시 탐색한다. (3번부터 반복)

이 경우 시간복잡도는 O(n) 이며, 추가 공간을 사용하지 않습니다.

오답에 대한 대처법

면접에 대한 가장 흔한 오해 중 하나는, 모든 문제를 맞춰야 한다는 생각입니다.

• 면접에서 답을 평가할 때 ‘맞냐’, ‘틀렸냐’로 보지 않는다.
• 면접관은 지원자들을 상대적으로 평가한다.
• 대부분의 문제가 아주 어렵기 때문에 굉장한 실력자라도 단번에 해법을 말하긴 어려울 수 있습니다.

그러므로 중요한 것은 최대한 풀려고 시도하는 것이고, 자신의 풀이과정을 잘 전달하는 것이 중요합니다.

면접관의 평가요소

• 최종 답안이 최적 해법에 근접한가
• 최종 답안을 내는데 시간이 얼마나 걸렸나
• 얼마나 힌트를 필요로 했는가
• 얼마나 코드가 깔끔한가

그외 꿀팁들

코드를 축약해도 된다

언어적 특성에 따라, 보일러 플레이트같은 코드가 들어갈 수 있습니다.

이 경우, 면접관에게 양해를 구하고 축약해도 됩니다.

예를 들어 아래와 같이 축약할 수 있습니다.

//축약 전
HashMap<String, String> map = new HashMap<>();
map.put("a", "A");
map.put("b", "B");
map.put("c", "C");

//축약 후
HashMap<String, String> map = new HashMap<>();
map.put("a", "A");
... "b", "B"
... "c", "C"

좋아보이는 코드

• 정확도
• 효율성
• 간략화
• 가독성
• 관리 가능성

모듈화 및 추상화

모듈화된 코드를 작성한다는 것은 관계 없는 코드들을 별도 함수로 나눈다는 것을 의미합니다.

그럼 가독성도 향상되고, 유지보수도 용이하며, 테스트하기도 쉬워집니다.

그리고 단순한 기능을 하는 함수의 경우 추상화를 할 수도 있습니다.

예를 든다면 아래와 같습니다.

public void solution() {
	//기타 복잡한 로직...
	
	sort();

	//기타 복잡한 로직...
}

//---[추상화 전]---
private void sort() {
	//실제로 정렬하는 로직 작성...
}

//---[추상화 후 솔루션]---
private void sort() {
	//TODO - 정렬 로직 (실제 작성 X)
}

물론 면접관에게 사전에 양해를 구하고, 필요하다면 나중에 작성하겠다고 설명해야 합니다.

오류 검사

오류 검사 로직을 중요하게 생각하는 면접관이 있을 수 있습니다.

따라서 오류 검사 로직을 따로 TODO로 빼두고 일단 알고리즘 구현에 집중하는 것이 좋습니다.

//실제로 에러 처리 로직을 구현하는 경우
public int divide(int a, int b) {
	if (b == 0) throw new RuntimeException(); //에러 처리
	return a / b;
}

//TODO로 빼두기
public int divide(int a, int b) {
	//TODO - b가 0인 경우
	return a / b;
}

포기하지 말기

면접장에서 출제되는 문제가 압도적으로 어렵다고 생각할 수 있습니다.

하지만 그런 상황에서 어떻게 대처하는가도 면접관이 테스트하려는 것 중 하나입니다.

어려운 문제를 즐기며 푸는 모습을 보여주세요!

정리하며…

이번 포스팅을 통해, 면접장에서 기술적 문제를 만났을 때 어떻게 접근하고 대처해야하는지 알아봤습니다.

집중해야하는 것은 ‘다양한 문제 접근 방식’ , ‘문제를 풀 때의 태도’ 인 것 같습니다.

모두 연습하셔서 좋은 결과가 있었으면 좋겠습니다! (저도 열심히 연습해볼게요 ㅎㅎ)