코딩스토리

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 알고리즘 관련 문제이다. 처음 봤을 때 어떻게 해야 할지 감은 잡혔으나 그걸 코드로 옮기는 게 너무 어려웠다.. 먼저 떠올렸던 해법은 1. 다익스트라를 통해 시작점부터 도착점까지 최단 거리를 구한다. 2. 최단 경로에 포함된 간선들을 모두 제거한다. 3. 다익스트라를 통해 거의 최단 경로를 구한다. 문제는 2번이였다. 최단 경로가 여러 개가 나올 수 있고, 그렇다면 그 ..

www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라를 활용한 문제이다. 문제 분석 기본적인 다익스트라 문제이다. 버스 비용이 다르다 -> 가중치가 다르다, 즉 다익스트라! 도시를 노드로, 버스 비용을 간선으로 바꾸어 그래프 문제로 모델링하면 된다. 이 문제의 특이한 점은 출력 조건이였다. 1. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용 출력 2. 경로에 포함되어있는 도시의 개수 3. 도시 순서대로 출력 최소 비..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 작년 8월에 처음 공부한 뒤 지금까지 한 번도 복습하지 않았다.. 당연히 그때도 어려웠지만 지금은 완전히 까먹은 상태여서 언젠간 해야지 하다가 결국 어제오늘 복습을 했다. 사실 bfs 문제를 풀다가 '가중치'가 일정하지 않은 문제를 만나서 급하게 다익스트라를 공부한거긴 함ㅎㅎ 어쨌든 문제를 분석해보면 도로들은 단방향으로 이루어져있고 -> 단방향 그래프 각각의 ..

# 이 글을 "Do it! 쉽게 배우는 R 데이터 분석"의 내용을 바탕으로 작성한 글입니다. 이번엔 지도를 시각화해보자. 지역별 통계치를 색깔의 차이로 표현한 지도를 '단계 구분도'라고 하는데 오늘은 이걸 만들어 볼 예정이다. 당연히 여러 패키지가 필요하다. 필요한 패키지에 대한 정보는 책에 잘 나와있다. 이 부분을 쭈욱 공부해봤는데.. 굳이 포스팅할 필요까진 없을 것 같으나 그래도 해봤다는 것을 남기기 위해 직접 실행한 화면 캡처본만 남긴다. 아래는 한국 시도별 인구 데이터이다. 이 부분을 굳이 기억하고 있을 필요까진 없을 것 같아서 그냥 따라 치면서 이해했다. 한번에 너무 많은 것을 공부하려다 보니 슬슬 지친다.. 그래도 음.. 나름 재밌긴 하네요ㅎㅎ

www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 덱과 슬라이딩 윈도우 알고리즘을 사용하면 되는 문제였다. 해결방법은 다음과 같다. 하나의 덱에 최솟값에 대한 정보를 담고 있는다. 이때 이 덱의 크기는 최대 L까지 이다. 그리고 이 덱에는 최솟값들의 후보를 모두 가지고 있는다. 또한 이 덱은 오름차순 정렬이 되어 있다. 무슨 소리인가 할 수 있는데 천천히 살펴보면 생각보다 어렵지 않게 구현이 가능하다. 먼저 덱에 최솟값에 대한 ..