전체 글

이 문제는 문제 설명은 길지만 짧게 설명하자면 A선수의 번호와 B선수의 번호가 주어졌을 때, 몇 번 만의 두 선수가 겨루게 될지 묻는 문제이다. 즉 총 8명의 선수가 있을 때, 현재 A의 번호는 4이고 B의 번호는 7이므로 A의 대진번호는대진 번호는 2, B의 대진 번호는 4가 된다. 이 문제의 조건인, A와 B는 항상 이기기 때문에 그다음 A의 대진 번호는 1, A의 대진 번호는 2가 된다. 다음 경기도 이길 것이고 그다음 A의대 진번호는 1, B의 대진 번호도 1로 같게 되므로 정답 3이 나오게 된다. 문제만 이해한다면 구현자체도 어렵지 않기 때문에 금방 풀 수 있는 문제였던 것 같다. 결국 자신의 번호(대진번호)가 1,2이면 그다음 대진 번호는 1, 3,4이면 대진 번호 2, 5,6이면 3 이 될 ..

SWEA D4문제를 추천순으로 풀고 있는데 어제오늘은 좀 쉬운 문제를 풀게 됐다. (사실 요즘 바빠서 알고리즘 풀 수 있을까? 했는데 다행이다.) 이 문제는 제목이 길찾기이지만, 사실 미로 찾기, 그래프 탐색하라는 문제이다. 제한시간도 30초이고 최대 방문지 점도 100개이기 때문에 BFS로 풀지, DFS 풀지 고민 없이 풀고 싶은 방식으로 풀어도 해결할 수 있을 것이다. 나는 처음보자마자 BFS가 떠올랐기 때문에, BFS로 풀어보았다. 우선 100개의 방문 체크를 할 리스트를 만들고 인접 행렬을 만들었다. 이 문제는 "출발 도착 출발 도착 출발 도착..." 이런식으로 Input값을 주기 때문에 한 번에 다 받은 다음에 두 개씩 끊어서 인접 행렬에 넣어 줄 필요가 있었다. 변수를 받고 도착지(99)에 도..

이 문제는 다른 D4문제보다는 쉬웠던 것 같다. 처음에는 D4를 보고 DP로 풀어야 하나 생각했지만 N(검증 값의 길이)가 최대 20인 것을 보고 Itertools 라이브러리를 사용하면 풀 수 있지 않을까? 생각했다. 문제를 간략히 설명하자면 점원들이 선반의 물체만 한 탑을 쌓는데(점원들의 키의 합) 선반의 물체보다 높지만 가장 낮은 탑을 쌓는 경우 선반 높이와 점원들의 키의 차이를 구하는 문제이다. 문제를 살짝 봤을 때 DP로 풀어야하는 문제인가 싶었지만 위에서 말했듯이 점원들의 수가 최대 20명이었기 때문에 부분집합으로 풀 수 있었고, 더하여 집합을 만드는데 조건도 없었기 때문에 라이브러리를 사용할 수 있었다. 이를 코드로 나타내면 이렇게 나타낼 수 있다. 이번문제는 어떻게 푸는 문제인지 확실히 감잡..

이 문제는 인도네시아의 섬들을 모두 연결하는데 환경부담금이 가장 적게 나오도록 연결하는 방법을 묻는 문제이다. 즉 가중치(환경부담금)를 이용한 최소 신장 트리를 구하는 문제이다. 조금 더 쉽게 말하자면 부담금이 가장 적게 나오는 방법으로 모든 섬을 한점 잇기 하는 방법을 찾는 방법이다. 이 문제에서는 X좌표와 Y좌표, 환경부담세율을 Input값으로 각 거리에 비례하는 환경부담금이 최소가 되는 최소 신장 트리를 구하는 문제이다. 문제에 대한 설명은 이 정도로 하고 내가 이문제를 풀기 위해 사용한 Prim알고리즘에 대해 잠깐 알아보고 코드를 정리해 보겠다. MST(Minimum Spanning Tree)를 구하는 알고리즘 중 대표적으로 Prim과 Kruskal 알고리즘이 있는데, 두개다 자신이 없었던 나는 ..