Patrick's Devlog

1. DP vs Backtracking DP는 problem과 sub-problem을 나누어 진행하고, 이 sub-problem은 더 작은 sub-problem으로 나누어 질 수 있다. 겹치는 sub-problem은 memorization을 통해 저장하면서 중복된 계산을 줄여갔다. 그러나, Backtracking은 우리가 가져갈 수 있는 모든 경우의 수를 하나씩 살펴보고, Decision space를 만들어 나간다. 여기서 어떠한 경우의 수가 의미가 없게되면 가지치기를 하게 되고 backtracking을 하면 된다. 2. Backtracking ex> Phone keypad 문제(leetcode 17) 우리가 아는 휴대폰의 키패드는 아래의 사진과 같다. "25"가 입력이 되었을 때, AJ / AK / A..

1. DFS 깊이우선탐색(depth-first search, DFS)은 맹목적 탐색 방법 중 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용해 트리에 다음 Level의 한개의 자식 노드를 첨가하여, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 쉽게 설명하면 하나의 루트를 선택하여 최대한 깊이 들어가 확인한 후 다시 돌아가서 다른 루트를 탐색하는 방법이다. 구현 방법은 재귀 호출을 사용하면 된다. 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 depth bound을 사용한다. depth bound에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모 노드로 돌아와 부모 노드에..

개요 공부를 진행하다 오랜만에 이진 탐색을 꺼내려니 기억이 잘 나지 않아서 정리를 해두었다. 단순한 알고리즘이라, 정리해두고 기억이 나지 않을때 가끔씩 살펴보려 한다. 이진 탐색 알고리즘(Binary Search Algorithm) 정렬과 함께 가장 기초인 알고리즘으로 꼽힌다. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 정확히 설명하면 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단해 맨 앞부터 검색하거나 중간부터 검색한다. 이진 탐색의 원리는 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 ..

개요 알고리즘 문제를 풀다가 배낭 관련 문제를 풀기 위해 기본적인 이론을 공부하고 코딩을 진행해보려고 한다. 저번처럼 유튜브 채널 코드없는 프로그래밍님의 Knapsack Problem 영상을 통해 공부를 진행할 예정이다. 자세한 내용을 알고싶다면 https://www.youtube.com/watch?v=rhda6lR5kyQ에서 확인하면 된다. Knapsack Problem 배낭 문제는 Dynamic Programming의 아주 대표적인 문제이다. 이는 조합 최적화의 문제이다. 간단하게 설명하자면 한 여행가가 지니고 있는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있으며, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이해가 잘 안된다면 아..

개요 조금씩 알고리즘 공부를 진행하고 있던 중에, DP에 대해 이미 공부를 했지만 아직 많이 빈약한 것 같아 유튜브를 통해 인강을 들은 후 다시 한 번 정리하려고 한다. 강의는 코드없는 프로그래밍님의 Dynamic Programming이다. 강의를 듣고싶다면 아래의 링크로 들어가면 들을 수 있다. https://www.youtube.com/watch?v=eJC2oetXaNk Dynamic Programming 다이나믹 프로그래밍은 세가지 조건이 충족되면 바로 적용이 가능하다 1. Problem이 더 작은 subproblem으로 쪼개질 때 2. 이런 subproblem들의 솔루션으로 더 큰 규모의 problem의 솔루션을 구할 수 있을 때 3. 이러한 subproblem들이 겹칠 때 -> memorizat..