알루 코딩

많이들 접해보신 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..

이 문제는 지난 PreOrder 문제에 이어 Level Order Traversal 문제입니다. Level Order는 말그대로 레벨 순으로 순회를 하는 것인데, 트리에서는 보통 root 노드부터 레벨 1로 시작되고 아래로 내려오면서 level이 증가합니다. 해당 문제에서는 레벨별로 노드를 묶는 것이 관건인데요, 코드를 살펴보면서 설명드리겠습니다. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right from collections import deque ..

리트코드에서의 1번문제입니다. 문제를 설명해보자면, 입력값으로 nums 라는 숫자배열이 주어집니다. 그리고 target값도 입력값으로 주어지는데요, nums배열에서 두 숫자를 더해 target을 만들 수 있다면, 해당 두 숫자의 인덱스 값을 배열 형태로 출력하는 문제입니다. 문제 자체는 비교적 간단한 문제입니다만, 이 문제를 어떻게 효율적으로 풀어야 할지는 고민해봐야 할 부분입니다. 해당 문제를 직관적으로 풀자면 for문을 두 번 돌면 됩니다. 대략적인 코드는 아래와 같겠죠. for i in range(len(nums)): for j in range(i+1,len(nums)): if (nums[i] + nums[j]) == target: return [i,j] 하지만, 위와 같이 푼다면, 이미 시간복잡도..

이 문제는 전형적인 bfs,dfs 문제입니다. 문제 설명을 간단히 하자면, 주어진 image 그래프에서 (sr, sc) 위치에서부터 시작해 상,하,좌,우 4방향을 탐색하면서 image[sr][sc]와 값이 같다면, 해당 자리를 color 값으로 치환하는 문제입니다. 간단히 말해서, 시작하는 위치와 값이 같으면서 연결된 자리를 color 값으로 바꾸면 됩니다. 먼저, 코드를 살펴보면서 설명을 해보겠습니다. import copy class Solution(object): def floodFill(self,image, sr, sc, color): """ :type image: List[List[int]] :type sr: int :type sc: int :type color: int :rtype: List[L..

주어진 트리배열을 보고 PreOrder 로 출력하는 문제입니다. PreOrder은 아래와 같은 로직을 가지는데요, 부모를 먼저 출력하고, 자식 중에서 왼쪽->오른쪽 순으로 출력하는 로직을 가집니다. PreOrder traversal 말고도 순회 종류에는 크게 4가지가 있습니다. 순회 종류 4가지 (노드 방문 순서에 따라) 전위 순회 (Preorder Traversal) 중위 순회 (Inorder Traversal) 후위 순회 (Postorder Traversal) 레벨 오더 순회(level-order Traversal) 전위 순위는 root -> left -> right 중위 순위는 left -> root -> right 후위 순위는 left -> right -> root 순으로 순회를 하며 root를 ..