본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준1722 - 순열의 순서 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다. www.acmicpc.net 이 문제는 k번째 수열을 구하는 문제와 수열이 주어졌을 때 해당 수열이 몇번째이냐? 를 묻는 2개의 문제입니다. 그 중 첫번째 문제는 https://kosaf04pyh.tistory.com/192?category=1042517와 같은데 좀 다른 방법으로 문제를 해결하고 있습니다. 1. 1~n 범위의 수열이 있고 n과 k가 주어졌을 때 k번째 수열을.. 2020. 3. 11.
[알고리즘 문제] 백준10974 - 모든 순열 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net c++에서 순열을 구하는 api가 제공되기는 한데 한번 직접 코드로 짜보고 싶었다. 생각보다 쉽게 된 것 같다. dfs로 풀었고, 각 숫자가 중복되어 들어가면 안되기 때문에 각 숫자를 사용할 때 마다 체크를 해주었다. #include #include using namespace std; int n; int check[9] = {0}; void dfs(vector &v) { if (v.size() == n) { for (int i = 0; i < v.size(); i++) { cout 2020. 3. 10.
[알고리즘 문제] 백준9663 - N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net NxN판에 퀸을 놓을 수 있는 방법의 가지수를 구하는 문제 이다. 퀸을 놓을 수 있는 규칙은 자신의 대각선, 세로, 가로 방향에 다른 퀸을 놓을 수 없다는 점이다. 사실 N의 크기가 고정이라면 N중 for문으로 풀 수 있다. 하지만 N을 예측할 수 없기 때문에 재귀를 사용해야 한다. 문제자체는 dfs로 풀어야 하며, 퀸을 놓을 수 있는 조건을 만족할 떄까지 계속 놓다가 마지막 레벨까지 갔다면 하나의 경우의 수를 .. 2020. 3. 10.
[알고리즘 문제] 백준10793 - 이전 순열 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 10972문제와 비슷합니다. 10972문제에서는 다음 순열을 구했지만, 10973문제는 이전 순열을 구하는 문제 입니다. 앞에 다음 순열을 구하는 문제에서의 로직은 다음과 같습니다. 1. arr[k] < arr[k+1]을 만족하는 가장 큰 k를 구한다. 2. k 다음 위치부터 arr[k] < arr[i]를 만족하는 가장 큰 i를 구한다. 3. arr[k]와 arr[i]를 바꾼다. 4. k 다음 위치부터, arr[k+1] ~ arr[end]의 값들을 뒤집.. 2020. 3. 5.

티스토리툴바