곰탱이의 공부정리

https://www.acmicpc.net/problem/9663  이 문제는 전통적인 알고리즘 문제이다. 이 문제를 푸는 법은 결국엔 하나하나 다 놔봐서 되는 경우의 수를 찾는 백트랙킹으로 풀어야한다.  먼저 우리는 1행을 기준으로 아래행으로 나아가면서 퀸을 하나하나 놔 볼것이다. 근데 퀸이 서로를 겨누게 두면 안 되기에, 다른 퀸과 같은행,같은열,같은 대각선에 두면 안된다. 같은행은 우리가 행을 내려갈 것이므로 크게 신경 쓰지 않아도 되고, 같은 열은 그냥 검사하면 되고, 같은 대각선은 체스 보드판을 일종의 좌표계로 보고 x+y=t, x-y=t에 걸리는지 아닌지를 검사하면 된다.  본래 필자는 이를 2차원 배열로 직관적으로 풀려했으나, 0,1을 하나하나 건드려야 한다는점, 메모리가 부족하단 점 등 때..

https://www.acmicpc.net/problem/15686  치킨거리란 집과 가장 가까운 치킨집 사이의 거리이다. 그리고 도시의 치킨거리란 모든 집의 치킨거리를 합한 것이다. 우리가 주어진 치킨집 중 M개의 치킨집만을 남겨야 할 때, 도시의 치킨거리가 최소가 되게하는 경우의 도시의 치킨거리를 출력하는 문제이다. 이 때 0은 빈곳, 1은 집, 2는 치킨 집으로 인풋이 주어진다.  이 문제는 딱 봐도 복잡한 형식이다. 그렇기에 사실 마땅한 알고리즘보단 하나하나 차분히 나누어 충실히 구현하여 문제를 풀어야한다. 먼저 우리는 집과 치킨집 사이의 치킨거리를 구해서 2d 배열로 저장해놓을 필요가 있다. 그래야 치킨집을 하나씩 없애보며 도시의 치킨거리를 구할 수 있다. 그리고 M개가 될 때까지 치킨집들을 없..

https://www.acmicpc.net/problem/15666  이 문제는 N개의 자연수 중 M개를 중복하여 고른 내림차순 수열을 중복없이 사전순으로 출력하는 문제이다. 이 문제도 DFS를 응용하여 풀면 쉽게 풀 수 있는 문제이다.def chosing(seq): if len(seq) == M+1: ans_set.add(tuple(seq[1:])) return for i in Ns: if i >= seq[-1]: chosing(seq+[i]) N,M = map(int,input().split())Ns = list(map(int,input().split()))ans_set = set()chosing([-1])ans_list..

https://www.acmicpc.net/problem/15663  이 문제는 N과 M이 주어지고 N개의 자연수 중 M개를 고른 수열을 중복없이 사전순으로 출력하는 문제이다. 이 문제에서 주어지는 N개의 자연수는 중복될 수 있으므로, 필자는 그냥 고를 수 있는 모든 경우의 수열을 구하고 집합 자료형과 sorted() 함수를 이용하여 간단하게 구했다. 처음엔 시간초과가 나오지 않을까 했지만 N이 8 이하로 많이 해봤자 수열이 8! 밖에 나오지 않는지라, 그렇게 구하였다. def DFS(seq,visited): if len(seq) == M: ans_set.add(tuple(seq)) return for i in range(len(Ns)): if no..