Code States 50일차 - [자료구조/알고리즘] 코딩 테스트 준비

Chapter - Time Complexity

Time Complexity

알고리즘 문제를 풀다 보면 문제에 대한 해답을 찾는 것이 가장 중요하다. 그러나 그에 못지않게, 효율적인 방법으로 문제를 해결했는지도 중요하다. 혹시 문제를 풀다가, 이것보다 더 효율적인 방법은 없나?, 또는 이게 제일 좋은 방법인가? 라고 고민한 적이 있나? 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같은 말이다. 이번 챕터에서는 시간 복잡도와 Big-O(빅-오) 표기법에 대해 배운다.

시간 복잡도

문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 무슨 의미일까?

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

앞서 이야기했던 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다. 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

Big-O 표기법

시간 복잡도를 표기하는 방법은 다음과 같다.

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 이 중에서 Big-O 표기법이 가장 자주 사용된다. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다. "최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다.

 

만약에 결과를 반환하는 데 최선의 경우 1초, 평균 1분, 최악의 경우 1시간 걸리는 알고리즘을 구현했다면, 100번 실행하는데 최선의 경우 100초가 걸린다. 실행결과가 1시간을 훌쩍 넘겼다면, 어디에서 문제가 발생한거지?라는 의문이 생길 것이다. 최선의 경우만 고려했으니, 어디서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하니까 문제를 파악하는데 많은 시간이 필요하다.

 

평균값을 기대하는 시간 복잡도를 고려한다면, 100번 실행할 때 100분이 소요된다고 생각했는데, 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 할 것이다.

 

이처럼 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직하다. 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.

O(1)

시간 복잡도가 O(1)인 경우

Big-O 표기법은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가'를 표기하는 방법이다. O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.

O(n)

시간 복잡도가 O(n)인 경우

O(n)은 liner complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다. 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다.

O(log n)

시간 복잡도가 O(log n)인 경우

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

자료구조에서 배웠던 BST(Binary Search Tree)에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

O(n^2)

시간 복잡도가 O(n^2)인 경우

O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

2n, 5n을 모두 O(n)이라고 표현하는 것처럼, n^3, n^5도 모두 O(n^2)로 표기한다. n이 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문이다.

O(2^n)

O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

재귀로 구현한 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘이다.

Advanced

일반적으로 코딩 테스트에서는 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야 한다.

컴파일러 혹은 컴퓨터의 사양에 따라 차이는 있지만, 시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측해 보는 것은 중요하다.

 

예를 들어 입력으로 주어지는 데이터에는 n만큼의 크기를 가지는 데이터가 있고, n이 1,000,000보다 작은 수일 때 O(n) 혹은 O(n log n)의 시간 복잡도를 가지도록 예측하여 프로그램을 작성할 수 있다.

 

따라서, 입력데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀어야한다. 그리고 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중해라.

Chapter - Greedy Algorithm / implementation

Greedy Algorithm

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimalsolution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다. 그러나 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다.

 

따라서 두 두가지의 조건을 만족하는 "특정한 상황"이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 한다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

Implementation

알고리즘 문제를 푼다는 것은, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것과 같다. 수많은 문제 해결 과정은 대부분 여러 개의 카테고리로 묶여진다.

카테고리를 분류한다고 해도 내가 생각한 로직을 '코드로 구현'한다는 건 전부 공통적인 속성이다. 이러한 문제 해결을 코드로 풀어낼 때, 정확하고 빠를 수록 구현 능력이 좋다고 말한다. 구현 능력이 좋은 개발자를 선발할 의도로 구현 능력을 직접 평가하기도 한다.

보통 이러한 문제들은 구현하는 것 자체를 굉장히 까다롭게 만든다. 지문을 매우 길게 작성하거나, 까다로운 조건이나 상황을 붙인다거나, 로직은 쉽지만 구현하려는 코드가 굉장히 길어지게 되는 문제들이 대다수이다. 그렇기 때문에 깊은 집중력과 끈기가 필요하다.

구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있다. 완전 탐색이란 가능한 모든 겨웅의 수를 전부 확인하여 문제를 푸는 방식을 뜻하고, 시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그린다.

완전 탐색

모든 문제는 완전 탐색으로 풀 수 있다. 이 방법은 굉장히 단순하고 무식하지만 "답이 무조건 있다."는 강력함이 있다.

완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다. 완전히 탐색하는 방법에는 brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있다.

시뮬레이션

시뮬레이션은 모든 과정의 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다. 보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.

(Advanced) Dynamic Programming

탐욕 알고리즘과 함께 언급하는 알고리즘으로, Dynamic Programming(DP; 동적 계획법)이 있다. 줄임말로는 DP라고 하는 이 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서부터 출발한다는 점이다. 그러나 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식이다.

Dynamic Programming의 원리는 간단하다. 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종문제를 해결하는 문제 방식이다. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 다시 말해, 하나의 문제는 단 한번만 풀도록 하는 알고리즘이 바로 이 다내믹 프로그래밍이다.

다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.(Overlapping Sub-problems)
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.(Optimal Substructure)

첫 번째 조건은 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다는 말과 같다.

두 번째 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미한다. 따라서 두 번째 조건을 달리 표현하면, 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 한다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할수 있다.

Recursion + Memoization

다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다. 이때 결과를 저장하는 방법을 Memoization이라고 한다. Memoization의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 게산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

Iteration + Tabulation

하위 문제의 결괏값을 배열에 저장하고, 필요할 때 조회하여 사용하는 것은 재귀 함수를 이용하는 방법과 같다. 그러나 재귀 함수를 이용한 방법이 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결했다면, 반복문을 이용한 방법은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법이다. 따라서 이 방식을 Bottom-up 방식이라고 부르기도 한다.