-
Atcoder Educational DP contest 풀이
Atcoder에서 열렸던 Educational DP contest 문제들에 대한 풀이입니다. 자주 나오는 다이나믹 프로그래밍 유형들을 연습할 수 있는 좋은 셋이라고 생각합니다. 문제마다 간략한 풀이를 작성했습니다. 코드는 Atcoder에서 자유롭게 열람이 가능하므로 문제마다 링크를 달아두었습니다. 어느정도는 난이도 순서대로 정렬되어 있지만, 사람마다 느끼는 난이도가 다를 수 있습니다. A. Frog 1 문제 링크 $d_i :$ $i$ 번째 Stone까지 도달하는 최소 비용 $d_i = min(d_{i-1} + h_i - h_{i-1} ,\ d_{i-2} + h_i - h_{i-2} )$ 위와 같은 점화식으로 간단히 해결할 수...
-
트리의 종류와 이해
트리의 종류와 이해 0. 목차 목차 tree란? tree의 종류 결론 참고자료 1. tree란? tree 자료구조는 그래프의 한 종류로, 정의 내리자면 트리란 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이 때 각 노드는 재사용 되지 않는 구조이다. tree 에는 여러가지 특징들이 존재한다. tree 의 서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 유일하다. tree 에는 사이클을 가지는 노드 집합이 존재하지 않는다. tree 반드시 하나의 root가 존재한다. (부모 노드가 존재하지 않는 노드) 이런...
-
알고리즘 문제 풀이2
알고리즘 문제 풀이 4월에 푼 재미있는 문제들의 풀이를 작성해보았습니다. 문자열 장식 N개의 문자열이 주어지면 이 문자열들을 합쳐서 만들수 있는 사전순으로 가장 앞서는 문자열을 구하는 문제입니다. 단, 각 문자열 안에서의 상대적인 순서는 유지해야합니다. 우선 상대적인 순서를 유지해야 하니까 주어진 문자열들의 앞글자부터 하나씩 때어 온다고 생각합시다. 그러면, 매순간 각 문자열의 앞글자들 중에 사전순으로 가장 작은 알파벳이 있다면 그것을 때어 오는 것이 이득이라는 것을 쉽게 알 수 있습니다. 그런데 이러한 문자열이 여러개가 있으면 어떤 문자열에서 때어오는 것이 이득일까요?...
-
특별한 정렬 알고리즘들 2
개요 이번 글에서는 지난 달 글에 이어서 조금 더 다양한 정렬 알고리즘을 소개해 보려고 합니다. 저번 글에서도 언급했지만 정렬의 종류는 엄청나게 다양하며, 이 글에서 소개하는 정렬 알고리즘들은 그들 중 극히 일부에 불과합니다. 개중에는 병렬 처리가 되거나 쓰기 연산이 극도로 비싼 등 매우 특수한 실행 환경에서만 이득이 되는 것들도 있고, 데이터가 거의 정렬된 상태에서 매우 효율적인 알고리즘, 또는 현실 세계의 데이터들에 적합하도록 고안된 알고리즘 등도 있었고, 마지막에 잠깐 언급한, 그저 재미를 위해서만 만들어낸, 비효율적이기만 한 알고리즘들도...
-
그래프 색칠과 NP-Completeness
서론 현실의 여러 대상들은 그래프로 추상화 할 수 있다. 그래프를 색칠하는 것은, 서로 인접한 두 정점이 같은 색을 같지 않도록 색칠 하는 것이다. 이 그래프를 색칠하는 문제는, 다양한 스케쥴링 문제 혹은 컴파일러의 레지스터 배치, 패턴 매칭, 시험/수업 시간표 작성 등 다양한 문제를 해결할 수 있다. 이런 문제들이 다항시간안에 검증이 가능하지만, 다항 시간안에 풀리는지는 밝혀지지 않는 NP-Complete 문제라는 것을 알아보자. 그래프 그래프는, 정점을 나타내는 집합 $V$와, 간선을 나타내는 집합 $E$의 원소인, $G = (V, E)$로 나타낸다....