알루코딩

많이들 접해보신 DP의 단골문제 동전문제입니다. 주어진 동전을 얼마든지 사용하면서 amount를 만들 수 있는 총 가짓수를 구하는 문제인데요, 이 외에도 가장 최소의 동전 개수만 사용해서 푸는 문제 등 동전에 관한 DP문제는 이제 거의 정형화된 알고리즘으로 자리잡았습니다. 그렇기 때문에, 해당 문제를 푸는 방향도 처음 본 문제라면, 접근이 어려울 수 있습니다. 특히, DP는 많은 유형을 풀어봄으로써 어느정도 유형화를 하는 것도 방법입니다. 이 문제에 대해서는 먼저, 메모제이션 기법을 사용해서 전형적인 DP로 풀어보도록 하겠습니다. 그럼, 이 문제에 대해 이해를 시각화해볼까요? 원리를 살펴보면 다음과 같은 테이블을 그릴 수 있습니다. 테이블의 열은 '(원)'을 뜻하며, 0원부터 amount(=5)원까지 테..

해당 문제는 팰린드롬 문제입니다. '팰린드롬'이라는 것은 문자열을 앞에서 읽나 뒤에서 읽나 동일한 문자열 형태를 띄는 문자열을 말하는데요, 'a'라는 단일문자도 팰린드롬에 속하는 것을 유의하면 됩니다. 이 문제에서는 주어진 문자열 s 에 들어있는 팰린드롬 문자열이 총 몇개인지 파악하는 문제입니다. 첫번째 예시에서 문자열 s는 'abc'인데, 각 단일문자만이 팰린드롬이고, 그 외에는 팰린드롬이 아니기에 결과를 3을 리턴합니다. 두번째 예시에서 문자열 s는 'aaa'인데, 결과가 6이 나왔습니다. 먼저 각 위치에서 'a'가 단일문자로서 팰린드롬을 형성하고, 첫번째,두번째 문자로 이루어진 'aa'와 두번째, 세번째 문자로 이루어진 'aa'가 총 2개 있습니다. 마지막으로 'aaa'도 팰린드롬 문자열이기에 결과..

이 문제를 처음봤을 때, 최장수열과 관련한 풀이가 떠올랐습니다. 최장수열은 대표적인 DP 유형의 문제로서 기억을 하고 있기에 보자마자 DP를 활용해보고자 했습니다. 이 문제의 핵심은 문자열 S를 순회하면서 반복되지 않는 문자를 가지는 문자열의 최대 길이를 반환하는 것입니다. 그렇다면, 순회를 할 때 계속해서 알아야 하는 값은 현재 위치에서 조건에 맞는 문자열을 만들 수 있는 최장길이 이전에 똑같은 문자가 나왔는지에 대한 여부 로 정리할 수 있겠습니다. 그럼, 바로 코드를 살펴보고, 코드 해석을 해보도록 하겠습니다. 코드는 아래와 같습니다. class Solution(object): def lengthOfLongestSubstring(self, s): if s == "": return 0 dp = [1] ..

이 문제를 푸는 것에 있어서 O(n^2)으로는 바로 풀 수 있겠지만, 결과적으로 시간초과가 나고, follow up을 보면, 공간복잡도를 O(1)로 풀기를 제안하고 있습니다. 처음에 제가 접근한 방식은 배열의 길이를 2배로 늘려서 [1,2,3,4] 가 인풋 배열이라면, [1,2,3,4,1,2,3,4] 로 만든 후, 1을 바라볼 때는, [2,3,4] 의 곱을 2를 바라볼 때는 [3,4,1], 3을 바라볼 때는 [4,1,2], 4를 바라볼 때는 [1,2,3] 을 곱해서 결과 배열을 만드려고 했습니다. 위와 같은 방식으로 문제를 풀 때, 많은 변수들이 필요했고, 파이썬의 for문을 돌면서, index를 다시 뒤로가도록 하는 것에 있어서 어려움을 겪었습니다. 결국, 저는 문제를 O(n)의 방식으로 30분만에 풀..

처음에 그냥 생각나는 로직대로 푼 알고리즘은 다음과 같습니다. nums를 처음부터 더하는데, target보다 같거나 커지면, check 변수를 통해 플래그를 걸어 놓고 여태 더했던 순회 횟수, 즉 길이를 저장합니다. 그리고 다음 인덱스로부터 또 같은 행동을 반복하는데, 최소 길이가 갱신 된다면 최소 길이를 갱신하고 그렇지 않다면 그냥 패스합니다. 풀었던 코드는 아래와 같습니다. 푼 코드는 아래와 같습니다. class Solution(object): def minSubArrayLen(self, target, nums): for i in range(len(nums)): tmp = 0 for j in range(i,len(nums)): tmp += nums[j] if tmp >= target : length ..

이 문제를 처음 봤을 때 계수정렬을 생각해봤습니다. nums[i]의 범위가 -10^4 부터 시작되므로, 음수도 포함될 수 도 있기에, 음수일 때와 양수일 때를 나눠서 계수정렬로 로직을 짰었습니다. 하지만, 계수정렬을 한 리스트가 내림차순되면서, k 번째까지 리스트를 슬라이싱 하는데에, 원소 순서가 변하기에 한계가 있었습니다. 어떤 수가 몇 번 나왔는지를 체크해야 하므로, 계수정렬보다는 딕셔너리 등을 사용하는 것이 더 적합했습니다. follow up을 보면, O(n log n)의 시간복잡도를 구현해보라고 하는데, 딕셔너리로 풀 때, O(n)으로 풀리는 것이 아닌가 하는 의구심으로 문제를 풀기 시작했습니다. 푼 코드는 아래와 같습니다. class Solution(object): def topKFrequent..