문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 골드5짜리 백트래킹 문제치고는 매우 쉬웠다. 조합을 구하는 방법에 대해만 알고있으면 쉽게 풀 수 있다. 풀이 백트래킹 + 약간의 구현 문제이다. 암호 C개를 입력받고 정렬 시킨 후 조합을 돌려주었다. 이때 암호로서 사용할 수 있는지 조건을 판별해주기 위해 canPassword 함수를 만들어주어 조건을 만족하면 true 아니면 false를 반환하게 하여 true인 조건에 대해서만 암호를 출력할 수 ..
문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 일반적인 백트래킹 문제이다. n개 중에서 m개를 뽑는 조합이라고 가정하였을때 n은 각 tc마다 바뀌는 vector의 크기가 되고, m은 6개로 고정이다. 이를 바탕으로 조합을 돌려 모든 경우의 수를 출력하면 된다. lotto와 isused를 초기화하는 것을 잊지말자. 코드 #include #include #include #include using namespace std; v..
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 SW 역량 테스트 기출 문제라고 한다. 문제의 80%정도까지 접근은 했지만 문제 이해를 잘못하고, 변수 초기화를 깜빡해서 시간을 많이 날렸다. 문제 자체는 그렇게 어렵지 않았다. 앞으로 문제를 잘 읽고 접근하도록 하자. 풀이 이 문제는 백트래킹의 응용 문제라고 할 수 있다. 보드의 크기(N)에 대해 N/2개의 대한 조합을 백트래킹으로 구하고 사용된 값/사용되지 않은 값으로 나누어서 각각 start/link ..
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 대표적인 백트래킹 문제인 N-Queen이다. 이 문제는 바킹독님의 영상을 참고하여 풀 수 있었다. 이제 문제를 풀어보자. cur은 행을 의미하고 for문 안의 i는 열을 의미하며 i를 0부터 N - 1까지 모두 돌며 퀸을 배치한다. 0부터 N - 1까지 열을 for문으로 도는 이유는 서로 공격할 수 없게 퀸을 배치하기 위해서는 모든 열에 대해 퀸을 배치해주어야 하기 때문이다. 이때 퀸의 배치에 따라 퀸..
