- 문제 설명 - 문제 풀이 처음에 문제 설명을 볼때 문제 자체를 이해하는데 은근 오래 걸렸다. 간단하게 설명해서, 길이가 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 로 9개 있다.(0으로 시작하는건 제외) 길이가 2이면 10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98, 89로 총 17개가 있다. 여기서 중요하게 봐야할 점은 첫째 자리 수이다. 보면 0부터 시작해서 9로 끝나는 첫 째 자리 수를 순서대로 나열했는데, 이를 이용해 2차원 배열을 만들 수 있다. 길이 by 첫 째 자릿 수로 배열을 만들면 길이가 N이라고 할때 배열의 크기는 DP[N][10] 이 된다. 이때 편의상 코드에서는 DP[N+1][10]으로 해두겠다. 아래 그..
- 문제 설명 - 문제 풀이 백트랙킹의 가장 대표적인 문제 N-Queen이다. 기본적인 체스 룰을 알면 규칙은 쉽게 알 수 있다. 체스말 퀸은 같은 행, 열에는 위치할 수 없으므로 N*N 크기의 배열을 만들필요 없이 크키가 N인 일차원 배열을 만든 후 각 열에 몇번째 행에 퀸이 있는지 저장만 하면 된다. 한 행씩 퀸을 배치해가며 check 함수를 통해 배치한 퀸과 그 전에 배치했던 퀸들이 겹치지 않는다면 depth를 늘려간다. depth가 크기 N만큼 늘어났다면, 겹치지 않는 퀸의 경우의 수가 되었단 것이므로 경우의 수를 하나 늘려준다. 예를 들어, N = 4라면 아래와 같은 배치의 경우의 수 두 가지가 나온다. 같은 행과 열에 있는지에 대해서 체크하는건 간단하지만, 대각선에 대해서는 곧바로 생각해 내긴..
- 문제 설명 - 문제 풀이 각 팀의 능력치 합의 최소치는 백트래킹에 익숙하다면 쉽게 구할 수 있지만 두 팀을 중복되지 않게 짜기 위한 최적 방법을 찾아내는게 생각보다 헷갈렸다. 안그러면 계속 시간 초과가 된다. 때문에 재귀함수 인자를 넘겨줄때 pos(다음 값)값 + 1이 아닌 현재 반복값 + 1을 해줘야 된다. 팀은 한 팀만 구하면, 즉 n/2만큼만 구하면 나머지 다른 팀은 정해져 있으므로 depth는 n/2일 때 결과값을 갱신하면 된다. - 코드 #include #include using namespace std; int n; int S[22][22]; bool visit[12]; int result = -1; int start[12]; int link[12]; void make_team(int po..
- 문제 설명 어렸을 때 자주 해봤던 스도쿠 퀴즈이다. 이 문제는 백트랙킹 기법을 사용해 쓸모없는 연산을 최소화 시키는게 관건이다. 그러기 위해서 순차적으로 다음과 같은 방식으로 동작해야한다. - 문제 풀이 1. 9x9 크기의 배열을 만든다. 2. 빈 공간은 0으로 대체하기 때문에 값이 0인 곳들의 인덱스(x, y)를 저장할 배열을 추가로 만든다. 3. x, y를 저장한 배열을 처음부터 끝까지 돌면서 해당 좌표값에 1부터 9까지의 수를 넣으며 들어갈 수 있는 수라면 다음 좌표값을 진행하는 방식으로 동작한다. 4. 다음 좌표값에서 해를 찾지 못하면 그 전 좌표값에서 다른 해를 찾아본다. 5. 3,4 과정을 반복하며 모든 좌표값의 해를 찾았으면 진행중이 었던 백트랙킹을 중지시켜준다. (들어오는 입력은 스도쿠..
