Algorithm

• 코딩 테스트를 위한 Tip
• 문제 해결을 위한 전략적 접근(문제 접근법)
• Sorting Algorithm(정렬 알고리즘)
• Prime Number Algorithm(소수 판별법 알고리즘)

코딩 테스트를 위한 Tip

이 글은 How to Rock an Algorithm Interview을 번역한 내용에 기반을 두고 있습니다.

1. 칠판에 글쓰기를 시작하세요.

당연하게 들릴지 모르겠지만, 빈 벽을 쳐다보다 아무것도 못하는 수십 명의 후보자들이 많습니다. 텅 빈 벽을 보면서 아무것도 보지 않는 것보다 문제의 예를 응시하는 것이 더 생산적일 것입니다. 연관된 그림을 생각할 수 있다면 그 그림을 그리세요. 중간 크기의 예제가 있다면 작업할 수 있습니다(중간 크기의 예제는 작은 것보단 낫습니다. 작은 예제로 문제가 풀리는 경우는 흔하지 않기 때문이죠). 혹은 알고있는 몇 가지의 명제를 적어두세요. 아무것도 안하는 것보단 좋습니다.

2. 생각한 것들로 이야기하세요.

그리고 자신의 소리가 멍청하게 들릴까 걱정하지 마세요. 많은 사람들이 조용히 문제를 생각하는 것을 선호하지만, 때로는 막혔을 때 대화로 해결하는 것이 한 가지 방법이 될 수 있습니다. 가끔은 면접관에게 당신의 진행상황에 대해 명확하게 말하는 것이 무슨 일이 일어나는지 이해하는 계기가 될 수 있습니다. 당신이 강력하게 주장하지 않더라도, 면접관은 당신의 생각을 지속하도록 질문을 중단시킬 수 있습니다. 무엇을 하든 힌트를 위해 면접관을 속이려 하지마세요. 힌트가 필요하다면, 정직하게 그것에 대해 질문하세요.

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

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

• Sorting (plus searching / binary search) : 정렬 (이진 탐색)
• Divide and Conquer : 분할 정복
• Dynamic Programming / Memoization : 동적 프로그래밍
• Greediness : 탐욕 알고리즘
• Recursion : 재귀 알고리즘
• Algorithm associated with a specific data structure : 특정 데이터 구조와 관련된 알고리즘(4번째 목차로…)

4. 데이터 구조를 생각하세요.

상위 10개 데이터 구조가 현실에서 사용되는 데이터 구조의 99퍼를 차지한다는 것을 알고 계셨나요? 물론 농담입니다. 때로는 블룸 필터 또는 접미어 트리를 최적의 솔루션으로 하는 문제를 질문합니다. 하지만 이러한 문제조차도 훨씬 더 일반적인 데이터 구조를 최적의 솔루션으로 사용하는 경향이 있습니다. 다음 데이터 구조들은 가장 자주 표시되는 것들입니다.

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

이러한 데이터 구조의 안과 밖을 알아야 합니다. 삽입/삭제/조회 특성은 무엇인가요?(예를 들어, 균형 잡힌 이진 트리의 경우 O(log n)입니다.) 일반적인 주의사항은 무엇인가요?(Hashing은 까다롭고, 일반적으로 해시되는 물체의 크기가 k일 경우 O(k) 시간이 걸립니다.) 각 데이터 구조와 함께 사용되는 알고리즘은 무엇인가요?(그래프의 경우 Dijkstra(다익스트라)입니다.) 하지만 당신이 이러한 데이터 구조를 이해하게 되면, 올바른 데이터 구조를 사용하는 순간 종종 문제에 대한 해결책이 당신의 마음속에 떠오를 것입니다.

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

여러분이 받은 문제는 이전에 보았거나 혹은 그와 유사한 문제일 가능성이 있습니다. 예전 문제들의 해결책들을 어떻게 문제의 세부 사항에 적용할 수 있을지 생각해보세요. 문제가 제시된 형태에 사로잡히지 마세요! 핵심에 맞춰서 과거의 해결책과 일치하는지 확인하세요.

6. 문제를 작은 문제로 나누어서 수정하세요.

문제의 특별한 경우 또는 단순한 버전을 해결하려고 시도하세요. 코너 케이스를 보는 것은 문제의 복잡성과 범위를 제한하는 좋은 방법입니다. 문제를 큰 문제의 하위 집합으로 줄이면 기초부터 시작하여 전체 범위까지 작업을 할 수 있습니다. 문제를 작은 문제의 구성으로 보는 것도 도움이 됩니다. 예를 들어, “알 수 없는 상수 k에 의해 주기적으로 이동되는 정렬된 배열에서 숫자 찾기”는 (1) 먼저 “k”를 알아낸 다음 (2) 이동된 배열에서 이진 검색을 수행하는 방법을 알아내 해결 할 수 있습니다.

7. 되돌아 오는 것을 두려워하지 마세요.

특정 접근법이 효과가 없다고 느껴져서 다른 접근 방식을 시도할 때가 있습니다. 물론 쉽게 포기해서는 안됩니다. 하지만 당신은 결실도 없고 유망함이 느껴지지 않는 접근법에 시간을 허비했다면, 뒤로 물러나 다른 작업을 시도해보세요. 저는 덜 접근한 지원자보다 멀리 나아간 지원자를 더 많이 보았고, 이것은 당신이(당신과 같은 다른 이들 모두) 비논리적인 접근법을 포기해야 한다는 것입니다.

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

코딩 테스트의 목적

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

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

접근하기

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

생각할 때

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

문제 접근법

Data structure

• 배열 : 임의의 사이즈를 선언한다.(Heap, Queue, Binary Tree, Hashing 사용)
• 스택 : 행 특정조건에 따라 push, pop 사용한다.
• 큐 : BFS(너비 우선 탐색)를 통해 순서대로 접근할 때 적용한다.
• 연결리스트 : 배열 구현, 포인터 구현 2가지 방법 - 삽입, 삭제가 많이 일어날 때 활용한다.
• 그래프 : 경우의 수, 연결 관계가 있을 때 사용한다.
• 해싱 : 데이터 수만큼 메모리에 생성할 수 없는 상황에 적용
• 트리 : Heap과 BST(이진 탐색)

Algorithm

• ★재귀(Recursion) : 가장 많이 활용된다. 호출 횟수를 줄이는 것이 중요!(반복 조건, 종료 조건 체크)
• ★BFS(너비), DFS(깊이) : 2차원 배열에서 확장 시, 경우의 수를 탐색할 때 구조체(class)와 visited 체크를 사용한다.
• ★정렬 : Quick Sort, Merge(병합) Sort가 대표적이지만, 보통 Quick Sort를 사용한다.
• ★메모이제이션(Memoization) : 이전 결과가 또 사용될 때, 반복 작업을 안하도록 저장한다.
• ★이분탐색(Binary Search) : log N으로 시간복잡도를 줄일 수 있는 간단하면서 핵심적인 알고리즘이다.
• 최소 신장 트리(MST) : 사이클이 포함되지 않고 모든 정점이 연결된 트리에 사용한다.(크루스칼, 프림)
• 최소 공통 조상(LCA) : 경우의 수에서 조건이 겹치는 경우, 최단 경로 탐색시 공통인 경우가 많을 때 사용한다.
• 서로소 집합(Disjoint-Set) : 인접한 집합의 모임으로 Tree의 일종이며 시간복잡도가 낮다.
• 분할 정복 : Merge Sort에 사용되며 범위를 나누어 확인할 때 사용한다.
• 트라이(Trie) : 모든 String을 저장하면서 비교하는 방법이다.
• 비트마스킹 : |는 OR, &는 AND, ^는 XOR를 통해 메모리를 절약할 수 있다.

해결 방법 분류

DP(동적 계획법)

복잡한 문제를 간단한 여러 개의 하위 문제(sub-problem)로 나누어 푸는 방법이다.

DP에는 두 가지 구현 방식이 존재한다.

• top-down : 문제를 풀다가 하위 문제(sub-problem)가 풀리지 않았을 때 하위 문제를 풀기 시작한다. 재귀 함수로 구현하는 경우 대부분 top-down 방식이다
  • 같은 하위 문제를 가지고 있는 경우가 존재한다. 해당 최적해를 저장해서 사용하는 경우 하위 문제 수가 기하급수적으로 증가할 때 유용하다. 이러한 방법을 Memoization이라고 한다.
• bottom-up : top-down과 반대로 하위 문제들을 먼저 해결하여 상위 문제를 푼다.

예시 - Fibonacci 수열

top-down
f (int n) {
  if n == 0 : return 0
  elif n == 1 : return 1
  if dp[n] has value : return dp[n]
  else : dp[n] = f(n - 2) + f(n - 1)
         return dp[n]
}

bottom-up
f (int n) {
  f[0] = 0
  f[1] = 1
  for(i = 2; i <= n; i++) {
    f[i] = f[i - 2] + f[i - 1]
  }
  return f[n]
}

Greedy(탐욕법)

모든 선택지를 선택해보고 그 중 가장 좋은 것을 찾는 방법이 Divide and Conquer(분할 정복)와 DP(동적 계획법)였다면 Greedy(탐욕법)는 각 단계마다 그 순간 선택할 수 있는 최선을 선택하는 해결 방법이다. 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르다. 하지만 많은 경우에 최적해를 찾지 못하고 이를 적용할 수 있는 경우가 두 가지로 제한된다.

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
2. 시간이나 공간적 제약으로 최적해 대신 근사해를 찾아서 해결하는 경우

Sorting Algorithm

Sorting 알고리즘은 크게 Comparisons 방식과 Non-Comparisons 방식으로 나눌 수 있다.

Comparisons Sorting Algorithm(비교 방식 알고리즘)

Bubble sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort

Bubble Sorting

더 알아보기

n개의 원소를 가진 배열을 정렬할 때, In-place Sort로 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다.

Selection Sort

n개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아니라 비교하고 있는 값의 index를 저장해두었다가 최종적으로 한 번만 바꿔준다. 하지만 여러 번 비교를 하는 것은 마찬가지이다.

Insertion Sort

n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬할 순서라고 가정하면, 0부터 i - 1까지의 원소들은 정렬되어 있다는 가정 하에, i번째 원소와 i - 1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복한다.

Merge Sort

n개의 원소를 가진 배열을 정렬할 때, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. Divide and Conquer, 분할하여 정복한다의 원리이다. 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법이다. 단, 분할(Divde)해서 정복하였으니 정복(Conquer)한 후에는 결합(Combine)의 과정을 거쳐야 한다.

Merge Sort는 더 이상 나누어지지 않을 때까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우(원소가 하나인 배열일 때) 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나일 경우 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 Combine될 때, 비교가 이뤄지며 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이루어진다.

하나씩 남을 때까지 분할하는 것이면, 바로 하나씩 분할하면 되지 않을까? 라는 생각에서 재귀적으로 정렬하는 원리이다.

Heap Sort

binary heap 자료구조를 활용할 Sorting 방법은 두 가지 방법이 존재한다. 하나는 정렬의 대상인 데이터들을 heap에 넣었다가 꺼내는 원리로 Sorting을 하게 되는 방법이고, 나머지 하나는 기존의 배열을 heapify(heap으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법이다. heap에 데이터를 저장하는 시간 복잡도는 O(log n)이고, 삭제 시간 복잡도 또한 O(log n)이 된다. 따라서 heap 자료구조를 사용하여 Sorting을 하는데 시간복잡도는 O(log n)이 된다. 이 정렬을 하려는 대상이 n개라면 시간복잡도는 O(n log n)이 된다.

Quick Sort

Sorting 기법 중 가장 빠르다고 해서 Quick이라는 이름이 붙어졌다. 단, Worst Case에서는 시간복잡도가 O(n²)가 나올 수도 있다. 하지만 constant factor가 작아서 속도가 빠르다.

Quick Sort 역시 Divide and Conquer 전략을 사용하여 Sorting이 이루어진다. Divide 과정에서 pivot이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 나누어지는 partition 과정이 이루어진다. 이렇게 좌,우측 각각의 배열을 다시 재귀적으로 Quick Sort 시키면 또 partition 과정이 적용된다. 이 때 한 가지 주의할 점은 partition 과정에서 pivot으로 설정된 값은 다음 재귀과정에 포함시키지 않아야 한다. partition 과정에서 이미 정렬된 자신의 위치를 찾았기 때문이다.

Quick Sort’s Worst case

그렇다면 어떤 경우가 Worst Case일까? Quick Sort로 오름차순 정렬을 한다고 할 때, Worst Case는 partition 과정에서 pivot value가 항상 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정되었을 때이다. 매 partition마다 unbalanced partition이 이루어지고 이렇게 partition이 되면 비교 횟수는 원소 n개에 대해서 n번, (n-1)번, (n-2)번, … 이 되므로 시간 복잡도는 O(n²)이 된다.

Balanced-partitioning

Worst Case를 알았으니 자연스럽게 Best Case는 두 개의 sub-problem의 크기가 동일한 경우가 된다. 즉 partition 과정에서 반반씩 나누게 되는 경우이다. 그러면 partition 과정에서 pivot을 어떻게 정할 것인가가 중요해진다. 어떻게 정하면 정확히 반반이 아니더라도 균형 잡힌 불할, balanced-partitioning을 할 수 있을까? 특정 위치의 원소를 pivot으로 설정하지 않고 배열 내의 원소 중에서 임의의 원소를 pivot으로 설정하면 입력에 관계없이 일정한 수준의 성능을 얻을 수 있다. 또한 악의적인 입력에 따른 성능 저하를 막을 수 있다.

Partitioning

그렇다면 가장 중요한 partition은 어떻게 이루어지는가? 먼저 가장 마지막 원소를 pivot으로 설정했다고 가정한다. 이 pivot의 값을 기준으로 좌측에는 작은 값, 우측에는 큰 값이 오도록 해야하는데, pivot은 움직이지 않는다. 첫번째 원소부터 비교해서 만약 그 값이 pivot보다 작다면 그대로 두고, 크다면 맨 마지막 자리의 앞의 원소와 자리를 바꿔준다. pivot value의 index가 k라면 k-1번째와 바꾸어 주는 것이다. 이것을 모든 원소에 대해 실행하고 마지막 과정에서 작은 값들이 채워지는 인덱스를 가리키고 있는 값에 1을 더한 index값과 pivot값을 바꿔준다. 최종적으로 결정될 pivot의 인덱스를 i라고 하면, 0부터 i-1까지는 작은 값이 될 것이고 i+1부터 k까지는 큰 값이 될 것이다.

non-Comparisons Sorting Algorithm

Counting Sort, Radix Sort

Counting Sort

Count Sort는 몇 개인지 개수를 세어 정렬하는 방식이다. 정렬하고자 하는 값 중 최대값에 해당하는 값을 size로 하는 임시 배열을 만든다. 만들어진 배열의 index 중 일부는 정렬하고자 하는 값들이 되므로 그 값에는 그 값들의 개수를 나타낸다. 정렬하고자 하는 값들이 몇 개씩인지 파악하는 임시 배열이 만들어졌다면 이 임시 배열을 기준으로 정렬을 한다. 그 전에 한 가지 작업을 추가적으로 수행해줘야 하는데 큰 index부터 시작하여 누적된 값으로 변경해주는 것이다. 이 누적된 값은 정렬하고자 하는 값들이 정렬될 index 값을 나타내게 된다. 작업을 마친 임시 배열의 index는 정렬하고자 하는 값을 나타내고 value는 정렬하고자 하는 값들이 정렬되었을 때의 index를 나타내게 된다.

Radix Sort

정렬 알고리즘의 한계는 O(n long n)이지만, 기수 정렬은 이 한계를 넘을 수 있는 알고리즘이다. 한 가지 단점이 존재하는데 적용할 수 있는 범위가 제한적이다. 이 범위는 데이터 길이에 의존하게 된다. 정렬하고자 하는 데이터의 길이가 동일하지 않은 데이터에 대해서는 정렬이 불가능하다. 기존 정렬 알고리즘에 비해 좋은 성능을 내는 것이 불가능하다는 것이다. 문자열의 경우도 마찬가지이다.

기수(radix)란 주어진 데이터를 구성하는 기본요소를 의미한다. 이 기수를 이용해서 정렬을 진행하는데, 하나의 기수마다 하나의 버킷을 생성하여 분류를 한 뒤 버킷 안에서 정렬을 하는 방식이다.

기수 정렬은 LSD(Least Significant Digit)방식과 MSD(Most Significant Digit)방식 두 가지로 나뉜다. LSD는 덜 중요한 숫자부터 정렬하는 방식으로 예를 들어 숫자를 정렬한다고 하면 일의 자리부터 정렬하는 방식이다. MSD는 중요한 숫자부터 정렬하는 방식으로 세 자리 수이면 백의 자리부터 정렬하는 방식이다.

두 가지 방식의 Big-O는 동일하다. 하지만 기수정렬을 이야기 할 때는 주로 LSD를 이야기한다. LSD는 중간에 정렬 결과를 볼 수 없다. 일의 자리부터 시작해 마지막 자리까지 모두 정렬이 끝나야 결과를 확인할 수 있다. MSD는 정렬 중간에 정렬이 완성 될 수 있다. 정렬하는데 걸리는 시간을 줄일 수 있지만 정렬이 완료되었는지 확인하는 과정이 필요하고 이 때문에 메모리 사용량이 커진다. 또 상황마다 일관적인 정렬 알고리즘을 사용하여 정렬하는데 적용할 수 없기 때문에 불편하다. 이러한 이유들로 기수 정렬을 논할 때는 대부분 LSD에 대해서 논한다.

Sorting Algorithm’s Complexity 정리

Prime Number Algorithm

소수란 양의 약수를 딱 두 개만 갖는 자연수를 소수라 부른다. 2, 3, 5, 7, 11, …이 그러한 수들인데, 소수를 판별하는 방법으로 어떤 수 N이 소수인지 판별하기 위해서는 N을 2부터 N-1까지 나누어서 나머지가 0인 경우를 검사하는 방법과 에라토스테네스의 체를 사용할 수 있다.

에라토스테네스의 체 [Eratosthenes’ sieve]

에라토스테네스의 체(Eratosthenes' sieve)는, 임의의 자연수에 대하여, 그 자연수 이하의 소수(prime number)를 모두 찾아주는 방법이다. 입자의 크기가 서로 다른 가루들을 섞어 체에 거르면 특정 크기 이하의 가루들은 아래로 떨어지고, 그 이상의 것들만 체에 남는 것처럼, 에라토스테네스의 체를 사용하면 특정 자연수 이하의 합성수는 다 지워지고 소수들만 남는 것이다.

100이하의 소수를 찾는다고 가정할 때, 1부터 100까지의 자연수를 모두 나열한 후 먼저 소수도 합성수도 아닌 1을 지우고, 2를 제외한 2의 배수들을 다 지우고, 3을 제외한 3의 배수들을 지우고, 5를 제외한 5의 배수들을 지우는 등의 과정을 100의 제곱근인 10이하의 소수들에 대해서 반복하면, 남은 수들이 구하고자 하는 소수들이다.

Time Complexity

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(N³)

O(2^N) : 크기가 N인 집합의 부분 집합

O(N!) : 크기가 N인 순열

Reference

• How to Rock an Algorithm Interview
• Interview Question for Biginner
• 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략