문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다) 단, 좌표평면의 경계를 넘어가..

다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 다익스트라 알고리즘을 구현하는 과정은 다음과 같다. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음에는 시작 정점을 방문한다.) 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 프로그래머스의 배달 문제의 그래프를 예시로 다익스트라 알고리즘을 설명해보겠다. 1번 정점을 시작 정점으로 잡고 1번 정점에서 방문할 수 있는 각 정점까지의 거리를 표시한다. 1번 정점에서 방문할 수 없는 정점은 INF(무한대)로 표시해둔다. 방문하지 않은 정점 중 가장 거리가 짧은 2번 정점을 방문한다. 1번 정점에서 2번 정..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 풀이 분할 정복 알고리즘을 사용하는 문제로, 2^n * 2^n 크기의 2차원 배열을 4등분하여 r행 c..

힙(heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙은 다음과 같은 힙 속성을 만족한다. A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있는데, 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 한다. 키 값의 대소관계는 오직 부모노드와 자신노드 사이에만 성립하며 형제 노드간에는 대소관계가 정해지지 않는다. 각 노드의 자식노드 최대 개수는 힙의 종류에 따라 다르나 일반적으로 자식노드의 개수가 최대 2개인 이진 힙을 사용한다. 힙에서는 가장 높은(또는 가장 낮은) 우선순위를 가지는..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..

BFS (너비 우선 탐색) BFS는 탐색을 할 때 너비를 우선으로 수행하는 그래프 탐색 알고리즘이다. 너비 우선 탐색은 최단 경로를 찾아야 할 때 많이 사용한다. 재귀 함수로 구현하지 않고 큐(Queue)로 주로 구현한다. BFS를 그래프를 저장 할 때는 인접 행렬과 인접 리스트로 구현하는 방법이 있는데 인접 행렬은 시간 복잡도가 O(V^2) (V는 정점의 수), 인접 리스트는 O(V + E) (V는 정점, E는 간선) 이라 인접 리스트가 더 빠르기 때문에 주로 인접 리스트로 저장한다. C++ BFS 구현 bool visited[101] = {}; void bfs(vector graph[], int start) { queue q; q.push(start); visited[start] = true; whi..

이진 탐색 Lower Bound, Upper Bound 이진 탐색은 찾는 값이 존재하는지 탐색하여 하나의 값을 찾는 것이라면 lower bound와 upper bound는 이진 탐색에서 살짝 변형시킨 방식으로 중복된 값이나 상한, 하한선을 찾는 경우 등의 다양한 방식으로 활용할 수 있다. 이진탐색 포스팅 Lower Bound Lower Bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾는다. [1, 2, 3, 3, 3, 4, 5] 라는 리스트에서 3을 타겟으로 Lower Bound를 찾으면 결과로 나오는 인덱스는 3이 처음 등장하는 2가 된다. Upper Bound Upper Bound는 타겟보다 큰 값이 나오는 처음 위치를 찾는다. 위와 같은 [1, 2, 3, 3, 3, 4, 5] 의 리스트에..

분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때 까지 나눠 각각을 풀면서 다시 합병하여 문제를 해결하는 알고리즘이다. 상위의 해답을 구하기 위해 아래로 내려가며 하위의 해를 구하는 하향식 접근법을 사용하여 일반적으로 재귀함수로 구현된다. 분할정복의 대표적인 알고리즘은 퀵 정렬과 병합 정렬이 있다. DP와 분할 정복이 비슷한 느낌이어서 공통점과 차이점을 찾아보았다. 공통점 문제를 가장 작은 단위가 될 때까지 나눠서 분할함 차이점 동적 계획법 중복된 문제의 답은 저장되어 상위 문제 해결 시 재활용 됨 (메모이제이션 기법) 분할 정복 부분 문제는 서로 중복되지 않음(메모이제이션 기법 사용 안함) 분할 정복을 설계하는 방법 1) Divide : 문제가 분할이 가능할 경우, 2개 이상의 문..