Heecheol's blog

문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 너무 어려웠다. 구현하는게 어렵다기보단 아이디어를 생각해내는게 안돼서 참고했따ㅠ 퀸은 8방향 전부 움직일 수 있다. 하나의 퀸이 들어오면 세로줄, 가로줄, 왼쪽 대각선, 오른쪽 대각선을 각각 확인하면된다. 이 범위 안에 있지만 않으면 방금 들어온 퀸과 서로 공격할 수 없는 것이다. 정리하면 각 행 또는 열에는 반드시 하나의 퀸만 존재해야하고, 양쪽 대각선에 퀸이 없어야한다. 코드에 대해서 설명해보자면,..

문제 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 역시나 9번만 해결했다면 쉽게 해결할 수 있는 문제였다. 예시를 보면 자기자신부터 이후의 숫자들과의 쌍을 출력해야한다. 마찬가지로 중복은 없어야한다. 따라서 자기자신의 인덱스를 알아야 그 이후를 알 수 있기때문에 idx라는 파라미터를 같이 받아준 뒤, 반복문을 idx부터 시작하도록 하면된다. 이전에는 자신이 포함되면 안되므로 dfs(current + "\(numbers[i]) ", ..

문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제에서는 9번에서 했던 것처럼 중복만 체크하면서 모든 쌍을 출력해주면된다. 그래서 10번처럼 idx같은 파라미터를 받을 필요도 없이 매번 반복문을 0부터 시작하면 된다. 자기자신과의 쌍을 이룰 수 있으므로 방문했던 것을 표시할 필요도 없다. import Foundation let input = readLine()!.split(separator: " ").map { Int(Str..

문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 N과 M(9)를 풀었다면 쉽게 해결할 수 있는 문제였다. 똑같이 중복되면 안되는 것을 생각해서 last라는 변수를 함수 내에 선언하고 dfs함수를 돌고 난 이후에 last값이 바뀌도록 하였다. 이 문제에서는 주어진 배열에서 현재 수보다 큰 인덱스를 가진 수만 표현하면 되므로 check같이 방문을 표시할 변수는 필요없다. import Foundation let input = readL..

문제 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 지금까지의 N과 M문제들과는 달랐따..푸는데 너무 오래걸림. 중복을 신경써야하는데 시간초과 안나는 방법이 떠오르지 않아서 다른 분들의 풀이를 참고해서 해결했다. 처음에는 DFS로 모든 경우를 만든 뒤 Set을 이용하고 정렬하여 출력해주었따. 누가봐도 시간초과 날 것 같은 코드다. 백트래킹을 이용하려면 중복되는 수가 들어왔을때는 넘어가도록 해야하는데 아이디어가 생각나지 않았다. 그러다 ..