Patrick's Devlog

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

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

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