백트래킹

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 처음에는 조합으로 풀면 되겠다 싶어서 풀었다. 계속 안 풀렸는데, 공집합인 경우도 있어서 depth 가 0보다 큰 경우에 카운팅 하도록 했다. 그리고 제출 후, 구글링을 해보니 다 나랑 다른 풀이로 풀었었다. 가장 이해가 되는 사진이 있어서 가져와보면, 재귀인 것은 똑같지만, 현재 값을 포함하는 경우와 포함하지 않는 경우로 트리 구조로 가져가서 풀었다. 두 풀이..

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 전체 코드는 맨 마지막에 두었다. 문제를 풀기 전에 조합으로 팀을 나누고, 각 팀의 점수를 구한 뒤, 두 팀의 점수의 차 중 최솟값을 저장하면 되겠다 싶었다. 근데 우선 조합 구현을 순열로... 하고 있었고, 또 나는 조합 구현을 백트래킹으로 했고, 매개변수로 총 점수 합을 가져가는 식으로 구현했는데 다 풀고 찾아보니 조합때는 팀 편성만 담당하고, 마지막에 다 편성이 되면 그때 점수를 구하는 형태로 구현을 해둬서 나도..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 처음에 어떻게 풀지 하다가 그래도 구글링 하기 전까지 50%는 다 풀어놨었다 좀 더 시간 들였으면 다 풀었을 텐데 아쉽 일단 1. 백트래킹 + 2. 가로, 세로, 3*3칸 체크하기. 이 2개가 큰 흐름이고 여기까진 알았다. 근데 난 구현이 약한가보다 문제 푸는 순서는 다음과 같다. 9*9칸의 보드판을 2차원 배열에 입력받고 그 중 0인 칸을 따로 모아둔 후 백트래킹으로 0인 칸을 전부 돌면서..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 맨 밑에 전체 코드 있습니다. 문제설명 텀 프로젝트를 위해 학생들은 서로 팀을 이뤄야 한다. 팀의 조건은 다음과 같다. . 한 학생은 1명의 학생을 가리켜야 한다. 자기자신도 상관 없다. 학생들이 서로 가리키다가 싸이클이 형성되면 하나의 팀이 된다. 이때 자기자신을 가리키면 혼자 한 팀이다. 출력은 팀을 이루지 못한 학생 수이다 학생번호 1 2 3 4 5 6 7 학생이 가리킨 학생번호 3 1 3 7 3..