문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 해설 단순 구현 시뮬레이션 문제이지만 패턴을 발견하기 까지 고민을 좀 요구했던 문제이다. 문제는 크게 두 부분으로 나눌 수 있..

개념 서로 다른 n개의 수 중에 r개를 선택하여 나열 nPr = n x n-1 x n-2 ...... x n-r+1 리스트를 순서대로 수를 뽑아 나열하는 것. 즉, 순서에 의미가 있는 것이 순열입니다. 반대로 순서에 의미가 없다면 조합이 되겠습니다. Itreative function Recursive function Itreative function은 c++의 STL인 next_permutation 방식입니다. 설명과 직접 구현을 해보도록 하겠습니다. Recursive function은 재귀 호출 방식입니다. 마찬가지로 직접 구현 해보도록 하겠습니다. Iterative function (next_permutation) ① 뒤쪽부터 탐색하며 꼭대기를 찾자 꼭대기를 왜 찾아야 할까요? 두 가지 리스트를 가지..

개념 완전탐색은 알고리즘에 입문하는 사람들이 가장 처음으로 접하는 내용일것입니다. 그만큼 어려운 내용은 아니며, 말 그대로 완전히 탐색하는 것입니다. 영어로는 brute-force라고 하는데, 이것을 번역해보면 "무식하게 풀기"라는 뜻입니다. 구현 완전탐색을 할 때 사용되어지는 방식은 크게 두가지로 볼 수 있습니다. 1. Iterative 2. recursion 1번은 for문을 이용한 풀이 이고 2번은 재귀 호출을 이용하여 푸는 방법입니다. 예를 들어, 1부터 n까지의 합을 구하는 코드를 구성해보겠습니다. // iterator // 조건 : n >=1 // 1~n의 합을 반환한다. int sum(int n) { int ret = 0; for (int i = 1; i < n; ++i) ret += i; ..

목차 1. Dijkstra 알고리즘의 개념 2. Dijkstra 알고리즘의 구현 정의 Dijkstra 알고리즘은 방향 혹은 무방향 그래프에서 임의의 시작점으로부터 다른 모든 정점까지 최단거리를 구해주는 알고리즘 입니다. Dijkstra 알고리즘을 사용하기 위해서는 한 가지 전제조건이 필요한데, 그래프의 어떠한 가중치도 음의 값을 포함하고 있으면 안됩니다. 개념 Dijkstra 알고리즘의 동작 방식에 대해 알아보겠습니다. Dijkstra 알고리즘을 수행하기에 앞서 임의의 시작점으로 하여금 자기 자신을 제외한 모든 정점까지의 거리를 무한대 값으로 초기화합니다. 1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점 하나를 선택하여 방문합니다. 2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리..

원리 1. 배열 리스트 중 하나를 선택한다. 이 원소를 피벗이라고 함. 2. 피벗을 기준으로 피벗 앞에는 피벗보다 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 큰 원소가 옴 3. 분할 : 리스틀 피벗을 기준으로 두 리스트로 나눈다. 4. 분할된 리스트들에서 1-3번 과정을 반복한다. 위와 같은 과정을 반복한다면 매번 분할시 피벗으로 한 원소의 위치를 정할 수 있으므로 모든 수를 정렬할 수 있는 것은 자명합니다. 앞서 포스팅한 병합정렬에서와 마찬가지로 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 분할 정복을 모른다면 공부하고 읽는 것을 권장드립니다. 하지만 포스트를 통해서 이해는 할 수 있습니다. [ 16, 11, 6, 19, 12, 2, 2, 10 ] pivot값은 맨앞의 값..

목차 1. Prim 알고리즘의 개념 2. Prim 알고리즘의 구현 3. Kruskal 알고리즘과 Prim 알고리즘의 비교 이전 포스팅에서는 최소 신장 트리를 만들기 위한 알고리즘으로 Kruskal 알고리즘에 대하여 알아보았습니다. 이번 포스팅에서는 최소 신장 트리를 구현하는 또 다른 알고리즘인 Prim 알고리즘에 대해 알아보도록 하겠습니다. Prim 알고리즘은 Union-Find 와 같은 알고리즘을 몰라도 구현할 수 있습니다. 하지만 구현이 Kruskal 알고리즘에 비해 복잡합니다. 개념 Prim 알고리즘은 다음과 같은 방법으로 동작을 수행합니다. 임의의 정점을 선택하여 최소 신장 트리에 추가합니다. 최소 신장 트리에 포함된 정점과 연결된 정점들 중에서 아직 최소 신장 트리에 포함되지 않고 간선의 가중치..