DP란?DP란, Dynamic Programming의 약자로, 동적 계획법이라고합니다. DP가 어떤 단어의 약자이고 그것이 어떻게 불리는지에 대해서는 알겠는데, 너무 추상적이고 뭐가 동적으로 계획된다는 건지 이해가 되지 않을 수 있습니다. DP는 큰 문제를 조그만한 문제로 나누어, 답을 구하고 계산된 결과를 기록하고 재활용하며, 문제의 답을 찾아가는 방식으로 진행됩니다. 이런 구조적인 특성상 계산에서 나온 결과를 저장하기 위해서는 중간 계산 결과를 저장하기 위한 추가적인 메모리를 필요로 하게 됩니다.최근 한국에서 코딩테스트 시험을 볼 때, 시간 복잡도에 대해서는 다소 타이트하게 주어질 수 있지만, 공간 복잡도에 대해서는 상당히 널널하게 주는 편이므로, 어떤 문제를 풀어나갈 때, 다른 방법이 존재하더라도..
개념 - DFS란?DFS란, Depth-First Search의 약자로 깊이 우선 탐색을 의미합니다. DFS는 그래프 구조에서 사용하는 알고리즘 중 하나로 루트노드부터 탐색하는 것이 아닌 가장 깊은 곳에 있는 리프(Leaf)노드노드부터 탐색을 진행하는 탐색 알고리즘이다. 루트노드에서 다음 브랜치로 넘어가기 전에 완전하게 탐색하는 방법이다 1. 시작 노드 혹은 루트 노드 A에서 시작합니다.2. 시작 노드 A와 인접한 노드 B를 찾는다. 이때, 방문 여부를 설정한다.3. A에 인접한 다른 노드가 아닌, 다시 B에서 인접한 노드를 찾는다.4. 마지막 노드까지 순회했다면, 해당 노드의 상위 노드로 간다5. 위의 과정을 반복하면서 모든 노드를 순회한다.특징재귀적이다스스로를 호출하는 순환 알고리즘이다.방문했던 곳..
행성 X3 문제 문제 설명 상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다. 예를 들어, 10과 19의 친밀도는 25이다. 1 0 0 1 1 = 19 0 1 0 1 0 = 10 -------------- 1 1 0 0 1 = 25 행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행..
개요 - Heap이란?Heap이란 Heap Tree 구조를 가지며, 여러 개의 값중에서, 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 이진트리 구조이다. heap이라는 영단어 자체가 '어떤 것을 차곡차곡 쌓아올린 더미'라는 뜻이다. 이러한 이유로, 힙은 항상 완전 이진 트리 ..
