완전탐색

이 문제는 문제에서 어피 치과 과녁을 쏜 이후에 라이언이 과녁을 쏘는데 문제에 규칙에 따라서 라이언이 최대 점수차로 이기게 과녁을 쏠려면 어떻게 점수를 얻어야 할지 구하는 문제이다. 이 문제를 보면서 어떻게 구현할지 고민을 했는데 나에게 힌트가 됐던 점은 점수가 1에서 10까지 있다는 것과 오직 점수 얻는 방식이 상대편(어피치) 보다 많이 그 점수를 맞췄을 때 딱 그 점수만 얻는다는 점이다. 예를 들면 어피치가 10점 3발, 라이언이 10점 4발을 맞춘다면 점수는 라이언만 10점을 얻게된다는 점이다. 즉, 10개의 점수판 중에서 1점을 획득한다/ 못한다, 2점을 획득한다 / 못한다 이런 식으로 경우의 수가 2의 10 제곱으로 완전 탐색을 할 수 있다는 점이 나에게 힌트였다. 나는 위의 아이디어를 바탕으로..

사실 이 문제는 어렵지는 않지만, 제한사항과 문제 카테고리가 없었으면 좀 헤매었을 것 같다. 왜냐하면 완전 탐색 문제만 보면 DP문제가 아닌가? 하는 겁이 나기 때문이다. 하지만, 위에 말한것 처럼 제한사항에서 주어지는 숫자 개수가 20개 이하인걸 확인한다면, 쉽게 풀 수 있을 것이다. 이문제는 숫자들의 배열과 타겟넘버가 주어질 때, 숫자들의 배열의 합과 차로 타깃 넘버를 만들 수 있는 방법의 개수를 묻는 문제이다. 더하거나 뺄 수 있다는 부분에서 부분집합(itertools)를 활용하기에는 조금 어려움이 있을 것 같아 나는 완전 검색(DFS) 방식으로 문제를 풀었다. 원하는 타겟넘버가 되는 조건을 종료 조건으로 그전까지는 배열을 진행하면서 합과 차를 각각 구해보는 전형적인 완전 탐색 풀이법을 사용해 보았..

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