SWEA

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

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

SWEA D4 문제를 아직 많이 풀어보진 못했지만, 혁진이의 프로그래밍 다음으로 어려웠던 문제였다. 결론부터 말하자면 이문제의 핵심은 최선을 다한다는 것이고, 이를 구현하기 위해서 뒤에서부터 접근하면 한결 편해지는 문제였다. 문제를 간략히 소개하자면 Alice와 Bob이 목표숫자 N을 정해놓고 숫자 게임을 한다. 숫자게임은 자신의 차례일 때 숫자 x를 x*2로 키우거나 x*2+1로 키울 수 있고, 자신의 차례일 때, 어떻게 숫자를 키우더라도 N보다 크게 된다면 그 사람의 패배이다. 우리가 흔히 아는 31게임이랑 비슷하지만 숫자를 키우는 방식에서 조금 차이가 있다. 문제는 Alice와 Bob이 최선을 다해 게임을 할 때, 누가 이기게 되는지 묻는다. 한번씩 31게임을 할 때, 계산 따위 하지 않고 운에 모..

최근에 풀었던 문제 중에 가장 재밌게 푼 문제인 것 같다. 물론 쉽게 푼 문제는 아니었지만, 어떻게 풀지 고민하는 과정과 실제로 그 과정에서 정답이 나오는 게 알고리즘 문제를 푸는 재미인 것 같다. 문제를 간단히 설명하자면, 몇 번의 클릭으로 지뢰가 아닌 곳을 오픈할 수 있는지 횟수에 대한 최솟값을 묻는 문제이다. 추가적인 제약사항은 *(지뢰가 아닌 곳)을 클릭했을 때, 인접한 곳에 지뢰가 없다면 인접한 블록까지 공개가 된다. 그림에서 숫자는 인접한 위치의 지뢰 개수인데, 문제에서 묻는 것은 최소 클릭 횟수이기 때문에 구현하지 않았다. 문제를 처음 보고 최소한의 횟수? 'DFS!'를 생각했지만, 게임판의 길이(N) 이 300까지 가능하기 때문에 DFS는 절대 아니라고 생각했다. 그럼 내 지식에서 남은 보..

이 문제는 수업과정에서 한번 풀어봤던 문제였지만, 그 이후로 그래프나 완전 탐색 문제 위주로 풀다가 오랜만에 마주하니 어떻게 풀어야 할지 감이 잡히지 않았다. 문제는 음주가무를 즐기다가 조교들의 눈을 피해 일사천리로 자신의 방으로 돌아가야하는 고등학생들의 자기 방으로 돌아가는 최단 시간을 구하는 문제이다.(경로가 겹치는 경우 한 명씩 지나갈 수 있으므로 한 단위 시간이 증가한다) 문제만 읽었을 때는 막막했지만, 교수님께서 알려주신 필살기인 손으로 문제 상황을 적으면서 생각을 해보았다. 이 문제는 친절하게 그림으로도 설명을 해주었기 때문에 쉽게 이해할 수 있었다. 손코딩을 하면서 내가 생각해낸 해법은 통로를 하나의 배열로 생각하여 그 통로를 지나는 경우 방문 체크를 하는 것이다. 즉, 위 그림에서 1번 방..