알고리즘 면접 질문

💡 동적 계획법(DP, Dynamic Programming)에 대해 설명해주세요.

주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법을 말합니다.

동적 계획법에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고

그 결과를 재활용하는 메모이제이션(Memoization)기법으로 속도를 향상시킬 수 있습니다.

 

※ 메모이제이션 : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 재사용함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

---

💡 동적 계획법(DP, Dynamic Programming)이 갖는 2가지 조건은 무엇인가요?

1. 중복되는 부분(작은) 문제  

중복되는 부분 문제는 나눠진 부분 문제가 중복되는 경우로, 메모이제이션 기법을 사용해 중복 계산을 없앱니다.

2. 최적 부분 구조

최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.

---

💡 버블 정렬(Bubble Sort)에 대해 설명해주세요.

버블 정렬는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.

0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬합니다. 시간 복잡도는 O(n^2)입니다.

 

 

---

💡 선택 정렬(Selection Sort)에 대해 설명해주세요.

선택 정렬은 첫 번째 값을 두번째 부터 마지막 값까지 차례대로 비교하여 최솟값을 찾아 첫 번째에 놓고,

두 번째 값을 세 번째 부터 마지막 값까지 비교하여 최솟값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬하는 알고리즘입니다. 시간복잡도는 O(n^2)입니다.

 

 

---

💡 삽입 정렬(Injection Sort)에 대해 설명해주세요.

삽입 정렬은 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘입니다.

평균 시간복잡도는 O(n^2)이며, Best Case 의 경우 O(n)까지 높아질 수 있습니다.

 

 

---

💡 힙 정렬(Heap Sort)에 대해 설명해주세요.

힙 정렬은 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘입니다.

힙 정렬이 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값 몇개만을 필요로 하는 경우입니다.

시간 복잡도는 O(nlogn)입니다.

 

 

---

💡 병합 정렬(Merge Sort)에 대해 설명해주세요.

병합 정렬은 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘입니다.

시간 복잡도는 O(nlogn)입니다.

 

 

---

💡 퀵 정렬(Quick Sort)에 대해 설명해주세요.

퀵 정렬은 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나로 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬 합니다.

병합정렬과 달리 리스트를 비균등하게 분할합니다.

시간 복잡도는 O(nlogn)이며 worst case 경우 O(n^2)까지 나빠질 수 있습니다.

 

 

---

💡 정렬 알고리즘 시간 복잡도 비교 표

 

 

---

💡 Big-O 표기법의 시간 복잡도 크기 순서를 말해주세요.

O(1)  <  O(log N)  <  O(N)  <  O(N log N)  <  O(N^2)  <   O(2^N)  <  O(N!)

 

 

---

💡 허프만 코딩에 대해 설명해주세요.

허프만 코딩은 문자의 빈도 수를 가지고 압축하는 과정을 말하며, 접두부 코드와 최적 코드를 사용합니다.

• 접두부 코드 : 각 문자에 부여된 이진 코드가 다른 이진 코드의 접두부가 되지 않는 코드 (즉, 겹치지 않도록 이진 코드를 만드는 것)
• 최적 코드 : 인코딩된 메시지의 길이가 가장 짧은 코드

---

💡 재귀 알고리즘에 대해 설명해주세요.

재귀 알고리즘이란 함수 내부에서 함수가 자기 자신을 또 다시 호출하여 문제를 해결하는 알고리즘입니다.

자기자신을 계속해서 호출하여 끝없이 반복되게 되므로 반복을 중단할 조건이 반드시 필요합니다.

---

💡 피보나치 수열의 N번째 값을 구하는 메소드에 대해 각각 재귀와 반복문으로 손코딩(또는 수도코딩) 해주세요.

	private static int recursiveFibonacci(int index) {
	if (index <= 2){
	return 1;
	}
	return recursiveFibonacci(index - 1) + recursiveFibonacci(index - 2);
	}
	private static int loopFibonacci(int index) {
	int answer = 1;
	int before = 1;
	int temp;
	for (int i = 2; i < index; i++) {
	temp = answer;
	answer += before;
	before = temp;
	}
	return answer;
	}

---

💡 팩토리얼의 N번째 값을 구하는 메소드에 대해 각각 재귀와 반복문으로 손코딩(또는 수도코딩) 해주세요.

	private static int recursiveFactorial(int num) {
	if(num > 1) {
	return recursiveFactorial(num -1) * num;
	}
	return 1;
	}
	private static int loopFactorial(int num) {
	int answer = 1;
	for(int i = 2; i <= num; i++) {
	answer *= i;
	}
	return answer;
	}

---

💡 코딩 테스트를 위한 Tip

Translate this article: How to Rock an Algorithms Interview

1. 칠판에 글쓰기를 시작하십시오.

이것은 당연하게 들릴지 모르지만, 빈 벽을 쳐다 보면서 수십 명의 후보자가 붙어 있습니다. 나는 아무것도 보지 않는 것보다 문제의 예를 응시하는 것이 더 생산적이라고 생각합니다. 관련성이있는 그림을 생각할 수 있다면 그 그림을 그립니다. 중간 크기의 예제가 있으면 작업 할 수 있습니다. (중간 크기는 작은 것보다 낫습니다.) 때로는 작은 예제에 대한 솔루션이 일반화되지 않기 때문입니다. 또는 알고있는 몇 가지 명제를 적어 두십시오. 뭐라도 하는 것이 아무것도 안 하는 것보다 낫습니다.

2. 그것을 통해 이야기하십시오.

자신이 한 말이 어리석은 소리일까 걱정하지 마십시오. 많은 사람들이 문제를 조용히 생각하는 것을 선호하지만, 문제를 풀다가 막혔다면 말하는 것이 한 가지 방법이 될 수 있습니다. 가끔은 면접관에게 진행 상황에 대해서 명확하게 말하는 것이 지금 문제에서 무슨 일이 일어나고 있는지 이해할 수 있는 계기가 될 수 있습니다. 당신의 면접관은 당신이 그 생각을 추구하도록 당신을 방해 할 수도 있습니다. 무엇을 하든지 힌트를 위해 면접관을 속이려 하지 마십시오. 힌트가 필요하면 정직하게 질문하십시오.

3. 알고리즘을 생각하세요.

때로는 문제의 세부 사항을 검토하고 해결책이 당신에게 나올 것을 기대하는 것이 유용합니다 (이것이 상향식 접근법 일 것입니다). 그러나 다른 알고리즘에 대해서도 생각해 볼 수 있으며 각각의 알고리즘이 당신 앞의 문제에 적용되는지를 질문 할 수 있습니다 (하향식 접근법). 이러한 방식으로 참조 프레임을 변경하면 종종 즉각적인 통찰력을 얻을 수 있습니다. 다음은 면접에서 요구하는 문제의 절반 이상을 해결하는 데 도움이되는 알고리즘 기법입니다.

• Sorting (plus searching / binary search)
• Divide and Conquer
• Dynamic Programming / Memoization
• Greediness
• Recursion
• Algorithms associated with a specific data structure (which brings us to our fourth suggestion...)

4. 데이터 구조를 생각하십시오.

상위 10 개 데이터 구조가 실제 세계에서 사용되는 모든 데이터 구조의 99 %를 차지한다는 것을 알고 계셨습니까? 때로는 최적의 솔루션이 블룸 필터 또는 접미어 트리를 필요로하는 문제를 묻습니다. 하지만 이러한 문제조차도 훨씬 더 일상적인 데이터 구조를 사용하는 최적의 솔루션을 사용하는 경향이 있습니다. 가장 자주 표시 될 데이터 구조는 다음과 같습니다.

• Array
• Stack / Queue
• HashSet / HashMap / HashTable / Dictionary
• Tree / Binary tree
• Heap
• Graph

5. 이전에 보았던 관련 문제와 해결 방법에 대해 생각해보십시오.

여러분에게 제시한 문제는 이전에 보았던 문제이거나 적어도 조금은 유사합니다. 이러한 솔루션에 대해 생각해보고 문제의 세부 사항에 어떻게 적응할 수 있는지 생각하십시오. 문제가 제기되는 형태로 넘어지지는 마십시오. 핵심 과제로 넘어 가서 과거에 해결 한 것과 일치하는지 확인하십시오.

6. 문제를 작은 문제로 분해하여 수정하십시오.

특별한 경우 또는 문제의 단순화 된 버전을 해결하십시오. 코너 케이스를 보는 것은 문제의 복잡성과 범위를 제한하는 좋은 방법입니다. 문제를 큰 문제의 하위 집합으로 축소하면 작은 부분부터 시작하여 전체 범위까지 작업을 진행할 수 있습니다. 작은 문제의 구성으로 문제를 보는 것도 도움이 될 수 있습니다.

7. 되돌아 오는 것을 두려워하지 마십시오.

특정 접근법이 효과적이지 않다고 느끼면 다른 접근 방식을 시도 할 때가 있습니다. 물론 너무 쉽게 포기해서는 안됩니다. 그러나 열매를 맺지 않고도 유망한 생각이 들지 않는 접근법에 몇 분을 소비했다면, 백업하고 다른 것을 시도해보십시오. 저는 덜 접근한 지원자보다 한참 더 많이 나아간 지원자를 많이 보았습니다. 즉, (모두 평등 한) 다른 사람들이 좀 더 기민한 접근 방식을 포기해야 한다는 것을 의미합니다.

---

💡 문제 해결을 위한 전략적 접근

코딩 테스트의 목적

1. 문제 해결 여부
2. 예외 상황과 경계값 처리
3. 코드 가독성과 중복 제거 여부 등 코드 품질
4. 언어 이해도
5. 효율성

궁극적으로는 문제 해결 능력을 측정하기 위함이며 이는 '어떻게 이 문제를 창의적으로 해결할 것인가'를 측정하기 위함이라고 볼 수 있다.

접근하기

1. 문제를 공격적으로 받아들이고 필요한 정보를 추가적으로 요구하여, 해당 문제에 대해 완벽하게 이해하는게 우선이다.
2. 해당 문제를 익숙한 용어로 재정의하거나 문제를 해결하기 위한 정보를 추출한다. 이 과정을 추상화라고 한다.
3. 추상화된 데이터를 기반으로 이 문제를 어떻게 해결할 지 계획을 세운다. 이 때 사용할 알고리즘과 자료구조를 고민한다.
4. 세운 계획에 대해 검증을 해본다. 수도 코드 작성도 해당될 수 있고 문제 출제자에게 의견을 물어볼 수도 있다.
5. 세운 계획으로 문제를 해결해본다. 해결이 안 된다면 앞선 과정을 되짚어본다.

생각할 때

• 비슷한 문제를 생각해본다.
• 단순한 방법으로 시작하여 점진적으로 개선해나간다.
• 작은 값을 생각해본다.
• 그림으로 그려본다.
• 수식으로 표현해본다.
• 순서를 강제해본다.
• 뒤에서부터 생각해본다.

출처: https://dev-coco.tistory.com/160?category=1056309 [슬기로운 개발생활:티스토리]