코딩스토리

www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 구현과 시뮬레이션, 삼성 코테의 전형적인 유형이다. 설명은 복잡하고 어려워 보이지만 사실 풀어써보면 굉장히 간단한 문제다. 1. 0세대는 지정된 방향으로 한 칸 전진 2. 1세대 이상부터는 지금까지의 선분들을 끝점을 기준으로 모두 90도 회전 여기서 선분이라고 생각하지 않고 선분의 각 끝점이라고 생각해보면 어렵지 않다. 그럼 90도 회전은 어떻게 시켜야 하나 고민해봐야 한다. 나는 이..

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 알고리즘을 사용한 문제이다. 최단거리를 찾아야 하나 가중치가 존재한다. 즉 전형적인 다익스트라 알고리즘 문제이다. 문제는 지금까지 인접 리스트를 활용해서 풀어보다 보니 이렇게 그래프로 모델링해서 풀어본 적이 없었다. 구현 자체는 문제가 없었는데 고민했던 부분은 우선순위 큐에서 우선순위를 어떻게 주어야 하는지였다. 내가 사용하고 싶은 것은 dis, x좌표, y좌표 이 3가지였기 때문에..

www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 다음 주 알고리즘 학회의 주제가 그래프여서 한번 풀어보았다. 솔직한 마음으로는 가볍게 풀어보고 괜찮은 문제다 싶으면 미팅 때 내야겠다고 생각했는데.. 푸는데 2시간 걸렸다... 삼성 A형 문제라는데 아직 A형 따긴 멀었네.. 문제 자체가 어렵다기 보단 어떻게 구현해야 할지 생각하다 더 좋은 구현 방법이 자꾸 떠올라 계속해서 바꾸다 보니 오래 걸렸다. 문제의 퀄리티는 굉장히 좋은 것 같다. (다양한 알고리즘들이 사용됨!) ..

www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 알고리즘을 사용하여 해결할 수 있는 문제이다. 문제 분석 1. "목적지의 후보"들이 주어진다. 2. 목적지까지 반드시 "최단거리"로만 갈 것이다. 3. 반드시 "g와 h사이의 교차로"를 지나간다. 따라서 이 문제를 한 줄로 요약하면 다음과 같다. "목적지의 후보들 중 g와 h 사이의 간선을 반드시 지나가는 경로가 최단 경로인 정점들을 모두 찾아라!" 해결 방법 사실 문제를 보자마자 해결법이 떠올..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 알고리즘을 활용한 문제이다. 문제에서 확인해야 하는 조건들 1. 방향성이 없는 그래프 -> 무방향 그래프, 즉 양방향 그래프가 된다. (입력받을 때 처리) 2. 임의로 주어진 두 정점은 반드시 통과해야 한다. -> 두 정점을 거쳐서 가야함 3. 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능 -> 각각의 중간 정점에 가서 새롭게 다익스트라..