코딩스토리

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 문제를 풀다가 '가중치'가 일정하지 않은 문제를 만나서 급하게 다익스트라를 공부한거긴 함ㅎㅎ 어쨌든 문제를 분석해보면 도로들은 단방향으로 이루어져있고 -> 단방향 그래프 각각의 ..

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까지 이다. 그리고 이 덱에는 최솟값들의 후보를 모두 가지고 있는다. 또한 이 덱은 오름차순 정렬이 되어 있다. 무슨 소리인가 할 수 있는데 천천히 살펴보면 생각보다 어렵지 않게 구현이 가능하다. 먼저 덱에 최솟값에 대한 ..

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 오랜만의 알고리즘 포스팅이다. 이번 주 우리 소학회의 공부 주제가 이분 탐색이라 이 문제를 풀어봤다. (KOALA 뽜이팅!!) 어제 그제 이분 탐색 기초 문제들을 몇 개 풀어본 뒤라 해볼 만할 거라고 생각해서 골드 문제에 도전했는데 문제를 보고 뭐지..? 란 생각이 들었다. 딱 봐도 일반적인 정렬은 무조건 아니고, 배열에 넣어서 계산하는 건 더더욱 아니고.. 음... 음....??..