Jins' Dev Inside

LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다.

개인적으로 매력있게 느끼는점은 인간이 직관적으로 쉽게 찾을 수 있는 법을 논리적으로 찾기가 쉽지 않으며, 그를 위한 수학적 방법들에 있었다.

LIS 알고리즘은 주어진 수열 내에서 가장 긴 부분 수열을 찾아내는 알고리즘이다. 

가령 다음과 같은 수열이 주어져있을 때를 생각해보자.

위와 같이 주어진 수열에서, LIS 는 10, 20, 50, 90 또는 10, 20, 40, 60 등으로 구해낼 수 있으며 가장 긴 증가하는 부분 수열의 길이는 4라는 걸 직관적으로 구할 수 있다.

하지만, 알고리즘으로 옮기려고 한다면 이 직관을 표현하는 건 쉽지 않다. 

또한 우리는 구현에 있어서 매 Index에 대해 다른 전체 Index를 검색해야하는 어마어마한 시간 복잡도에 마주하게 된다.

이는 최적화 알고리즘 기법의 한종류인 Dynamic Programming 을 이용해도 마찬가지인데, DP로 구현할 시 알고리즘은 다음과 같다.

위의 알고리즘의 경우에도 역시 시간 복잡도는 O(N^2) 이 되고, N이 커질수록 부담스러운 알고리즘이 된다.

만약 N이 10000이 넘어간다면? 그때는 눈으로 보일만큼 성능에 영향을 주는 모듈이 되게 된다.

최장 부분 수열의 길이를 구하는 데 있어서 최적의 방법은 일반적으로 O(N logN) 알고리즘으로 알려져있고, Trace 배열을 정의해서 같은 시간복잡도에 최장 부분 수열까지도 알아낼 수 있다.

공부할 당시 최장 부분 수열의 길이를 구하는 부분은 간단했으나, 최장 부분 수열 자체를 O(N logN) 시간 안에 구하는게 쉽지 않았던 기억이 있어 정리해보았다.

최적화의 핵심은 Binary Search 이고, lis 라는 별도의 배열에 내용을 담는다. 과정은 다음과 같다.

먼저, 배열의 각 요소를 순회한다. 이때, 배열의 각 요소를 lis 배열에 담는데, lis 배열에는 작은 순서대로만 들어가야한다.

그를 위해서는, lis 배열의 가장 마지막 요소(우리는 lis 배열을 증가하는 순서로 담았기 때문에 lis 배열의 최댓값이다.)와 배열의 요소를 비교하면 된다.

만약 lis 배열의 최댓값보다 크다면, 해당 요소를 lis 배열의 마지막에 추가시켜주면 된다.

하지만, 다음 요소는 lis 배열의 마지막 요소보다 작다. 이 때 Binary Search 가 필요하다. 우리는 Binary Search 를 통해 

"정렬된" LIS 배열에서 arr 요소가 들어가야할 위치를 찾을 수 있다.

예시에서 이제 LIS 배열은 다음과 같이 변한다.

이런식으로, LIS 배열을 증가하는 부분수열로 만들어 놓으면 쉽게 최장 부분수열의 길이를 O(N logN) 시간복잡도로 구할 수 있다.

하지만, 이런 구현만으로는 어떤 요소가 최장 부분 수열을 구성하는지 알 수 없다. 

가령, 다음과 같이 배열의 마지막 요소가 첫번째 요소보다 작을 경우, 이 구현을 통해 수열 자체를 구하는건 불가능하다.

따라서, lis 배열을 채울때, 어떤 항목이 참조되는지 Reference 배열을 정의하여 요소들을 Tracing 하는 테크닉을 사용한다.

-- LiS 구현(C++) --

Trace 배열을 사용하면 위와 같이 LIS 알고리즘 사용 중 Refenrence를 저장하는 방식으로 최장 부분 수열의 추적도 가능하다.

Trace 배열에 저장된 인덱스를 끝에서부터 가져오면 최장부분순열 자체를 역순으로 구해낼 수 있다.

알고리즘의 시간복잡도는 O(N logN) 으로 DP 구현보다 효율적인 시간복잡도로 작동하게 된다.

이 방법 외에도 Segment Tree 등을 이용해 최적화된 구현이 가능하다.

순열탐색은 알고리즘 문제풀이나 실제 코딩에서도 상당히 많이 등장하는 알고리즘의 한 종류이다.

가령 명확한 기준을 갖고 일정한 순서로 전체를 탐색해야 하는 경우, 매우 유용하게 쓰일 수 있으며, 면접에서도 종종 등장하는 알고리즘 구현 문제이다.

순열 탐색을 하는 데 있어서 방법은 많은데, 포스팅에서 다룰 유명한 알고리즘이 있고, 이 방법을 모른다면 일반적으로 DFS나 BFS 를 이용해서도 구현할 수 있다. 하지만 많은 경우에 있어서 구현이 쉽지 않을 것이다.

이번에 다룰 알고리즘은 O(N) 의 시간복잡도로, 무작위 순열의 다음 순열을 구해내는 알고리즘이다.

또한 이를 바탕으로 무작위로 배치된 전체 수열의 모든 순열의 쌍을 구해보고자 한다.

모든 수열의 쌍을 구하는 알고리즘은 무작위 순열의 다음 순열을 구해낸다면 똑같이 적용하면 되므로, 다음 순열을 구하는 Next Permutation Algorithm 부터 정리해보자. 먼저 다음과 같은 수열을 예로 들어보자.

이제, permute 함수를 이용하면 무작위로 전달된 수열의 전체 순열을 순서대로 뽑아낼 수 있다. 결과가 많기 때문에 예시의 결과만 확인해보자.

Permute 함수의 결과로 나온 2차원 List 를 출력한 모습이다. 초기에 제시된 순열의 다음 순열을 성공적으로 구해내는 것을 확인할 수 있다.

Permute 함수는 아니겠으나, nextPermute 함수의 Next Permutation 알고리즘이 사용하는 방식은 C++ 의 STL 이 사용하는 수도코드와 같다. 최적화된 Greedy 알고리즘으로 생각된다. 좀 더 연구가 하고 싶다면 다음 자료를 참조하자.

(https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)

순열의 순차탐색은 많이 사용하는 알고리즘이지만, 면접이나 코딩테스트와 같은 제한된 환경에서 최적화된 시간 복잡도를 요하는 바로 다음 순열을 구하기는 쉽지 않다.

어려운 알고리즘이 아니기 때문에 이해하고 외워두는 것도 좋다.

LCS 알고리즘은 흔히 알려진 DP 를 이용한 매칭 알고리즘이다.

두 수열 혹은 문자열 사이에 공통으로 존재하는 부분 문자열을 찾는 알고리즘으로 가령, 다음과 같은 예시를 봐보자.

SETAPPLE 

EATMANY

위의 예시에서 공통으로 존재하는 부분 문자열은 E-T-A 이다. 순서가 보장되면서 양쪽에 모두 존재하는 똑같은 패턴의 공통 문자열이다.

문제를 해결하기 위해서 가장 쉬운 방법은 두 문자열에 대한 Nested Loop 를 돌면서 완전탐색으로 순서를 기록하면 되지만, 이렇게 하면 매우 복잡하면서도

비효율적인 알고리즘이 된다.

그래서 흔히 알려진 알고리즘은 다음과 같은 DP 의 Memoization 테크닉을 사용한 알고리즘이다.

위의 코드를 해석해보자.

DP에 친숙하다면 위의 코드는 그다지 어렵지 않다. 2차원배열 dp 는 두 문자열에 대한 배열을 저장한다.

즉, 다음과 같이 정의된다.

dp[i][j] => 문자열1의 i 인덱스 까지에 대한 부분문자열과 문자열2의 j 인덱스 까지에 대한 부분문자열 간의 최장 공통 부분 수열 길이를 저장.

이렇게 하면, 다음과 같은 관계가 도출된다.

문자열1의 i번째 문자와 문자열2의 j번째 문자가 같다면, 해당 위치에서의 LCS 길이는 그 전길이까지의 최장 공통 부분 수열의 길이보다 1만큼 증가한 값이 된다.

dp[i][j] = dp[i-1][j-1] + 1

반면 같지 않다면, 다음과 같이 문자열1의 i-1 번째까지의 부분 문자열과 문자열2의 j-1 번째의 부분 문자열 간의 최장 부분 길이 중 더 긴쪽이 기록 된다.

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

이와 같은 식을 이용해 만든 dp 배열을 표로 기록해보자.

이제 dp 배열은 부분 문자열의 길이에 대한 모든 정보를 포함하고 있다.

오른쪽 아래에서부터 왼쪽 위까지 (두 문자열의 끝부분에서부터 시작부분까지) 반복하면서 숫자가 처음으로 작아지는 시점(역으로 생각하면 처음으로 부분 문자열 길이기 증가하는 시점이다.) 을 찾으면,

어떤 문자열이 공통 부분 문자열인지도 알 수 있다. 다음 굵게 표시된 요소들이 부분 문자열이 된다.

물론 표의 최댓값을 찾는다면 LCS 의 길이 또한 쉽게 구할 수 있다.

숫자에 대해 2의 승수(2의 제곱수)인지 확인하는 문제는 면접 시장에서 전설적으로 알려지는 유명한 문제 중 하나이다.

문제 해결에 있어서 초보자이거나, 개발 경험이 부족할 경우 의외로 코드로 옮기는데 힘들어 하는 경우도 많고,

단순한 문제임에도 불구하고 Geek 한 발상이 깃든 최적화된 코드를 유추해낼 수도 있기 때문이다.

숫자가 작을 때에는 직관적으로 숫자가 2의 제곱수인지 판단하기가 쉽지만 숫자가 커지면 쉽지 않다.

다음 수가 2의 제곱수인지 확인해보자

2097152

가장 먼저 짚어내야할 문제의 핵심은 2의 제곱수라면 2의 제곱수가 아닌 다른 수로 이루어져있지 말아야 한다.

그렇다면, 이 성질을 이용해서 숫자를 분해해보면 간단하다. 다음 알고리즘을 생각해볼 수 있다.

위의 알고리즘은 입력받은 숫자를 1이 될때까지 2로 나누어본다. 물론 중간에 2로 나누어떨어지지 않으면 숫자는 2의 제곱수가 아니기 때문에 Loop 를 벗어난다.

문제를 푸는데 익숙치 않은 일부 개발자를 제외하고는 거의 대부분의 개발자가 생각하는 알고리즘이며, 시간 복잡도는 O(logN) 이다.

그렇다면 좀 더 특별하게 풀 수 있는 방법은 있을까

컴퓨터가 숫자를 다루는 방식이 2진수라는 걸 고려하면 손쉽게 풀 수 있다. 즉, 2진수에서 2의 제곱수는 수를 구성하는 Bit가 단 한개의 1로 구성되어 있어야 한다. 따라서 다음과 같은 코드가 Optimal 이다.

이제 처음에 제시한 수의 결과를 확인해보자.

결과는 두 방식 모두 2의 제곱수임을 출력한다.

위의 문제는 Find whether the number is power of two 라는 실리콘밸리에서 흔히 알려진 면접문제이다. 고로 면접장에서 실제 볼 확률은 드물지만, 문제를 접근하는 참신한 방법은 배울 점이 많다.