Dior2ky의 it's IT

백준 14889번 스타트와 링크 문제이다. 이번 문제는 설명이 매우 길다. 사람을 두 그룹으로 나누어 묶고 시너지 표를 보고 각 그룹의 시너지의 차이를 구하면 된다. 이해가 잘 안된다면 입출력 예시를 본다. 이번 문제도 백트래킹 문제이기 때문에 한 그룹에 사람을 한명씩 넣어가도록 한다. 한 그룹에 사람이 반절 차게 되면 다른 한 그룹도 정해지게 된다. 그룹이 정해지는 순간 시너지 표에서 각 그룹의 시너지 합을 구해 차를 비교해준다. 차가 최솟값이 되어야 하기 때문에 최솟값으로 구해진 값과 비교하여 갱신해준다. 여기서 생각해줘야 할 점은 solve 함수에 들어간 k값이다. k 값을 넣음으로써 그룹에 한 사람이 들어갔다면 다시 처음사람부터 확인하는 것이 아니라 k번째 다음 사람부터 확인이 가능하다. def ..

백준 14888번 연산자 끼워넣기 문제이다. 연산자 끼워넣기 문제이다. 역시 백트래킹 문제이고 이전에 N과 M 문제는 숫자를 하나씩 넣어가면서 수열을 만드는 것이었다면 이번에는 연산자를 하나씩 넣어서 확인하는 방식이다. 숫자와 연산자 갯수를 배열에 넣어주고 연산자를 하나씩 골라가면서 연산을 해주면 될 것으로 보인다. 최댓값, 최솟값을 구해야 하기 때문에 연산자를 모두 쓰는 순간, 나온 값을 최댓값 최솟값과 비교하여 갱신해주면 될 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStream..

백준 2580번 스도쿠 문제이다. 스도쿠에 대한 규칙은 일반 스도쿠와 동일한 것으로 보인다. 빈칸을 0으로 표시하고 있다. 빈칸에 숫자를 하나씩 넣어가면서 확인해주는 백트래킹 방식이다. 이번에도 하나씩 넣어가는 solve 함수와 다음 빈칸에 숫자를 넣으러 넘어갈지를 판단해주는 promise 함수로 이루어져 있다. promise 함수에서는 가로 세로, 포함된 3x3 칸에 숫자가 있는지 확인하여 있다면 false를 리턴하여 다음으로 넘어가지 않도록 하였다. 여기서 3x3칸을 확인할 때에는 가로 세로 값인 i 와 j를 3으로 나눈 몫을 확인하여 0, 1, 2 값으로 3구역으로 나뉘기 때문에 어느 3x3 구역인지 확인하도록 하였다. import sys def promise(i, j, k): for m in ra..

백준 9663번 N-Queen 문제이다. 백트래킹으로 가장 유명한 문제라고 할 수 있는 체스판에 퀸을 놓는 문제이다. 이번 문제에서는 하나씩 놓아가면서 놓았을때 퀸이 놓일 수 있는 조건을 확인해서 놓도록 해주었다. func 함수를 통해 재귀 방식으로 하나씩 놓아가도록 하였고 promising 함수를 통해 놓는것이 가능한지 파악하였다. 언어는 C++을 사용하였다. #include using namespace std; int n; int result = 0; int arr[15] = {0,}; bool promising(int i){ for(int j = 0; j < i; j++){ if(arr[i] == arr[j] || abs(arr[i] - arr[j]) == (i - j)){ return false;..

백준 15652번 N과 M (4) 문제이다. 역시 N과 M 문제이다. 단계별로 풀어보기 백트래킹 항목에 있는 마지막 N과 M 문제이다. (다른 N과 M 문제들은 더 있다...) 이번에는 비 내림차순이라고 한다. 다른말로 하면 오름차순에 중복까지 가능하다고 생각하면 된다. 역시 백트래킹 문제이므로 비슷하게 풀어준다. N과 M (2) 문제와 비교하면 편할 것 같다. (2) 문제에서는 숫자 하나를 사용하면 그 숫자까지의 check 배열을 증가 시켰지만, 이번에는 그 숫자가 중복이 가능하므로 그 숫자 하나 아래 값 까지만 check 배열의 값을 증가시킨다. 이번 문제는 ruby 언어를 사용하였다. def func(cnt) if cnt == $m for i in 0...$m print $arr1[$arr2[i]]..

백준 15651번 N과 M (3) 문제이다. 문제는 다음과 같다. 이전 N과 M 문제들과 비슷하다. 이번에는 중복이 허용되어 있다. 역시 같은 백트래킹 문제이다. 이번에는 중복이 허용되기 때문에 check 배열이 필요가 없다.(만들어놓고 쓰질 않았다...) 그대로 모든 경우를 돌려 수열이 완성되면 출력하도록 만들어주었다. 언어는 java를 이용하였다. 입출력을 System을 이용하여 했더니 시간초과가 나와서 Buffer를 사용해주었다. 백준에서 풀때는 항상 이 방법을 사용하도록 해야겠다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader..

백준 15650번 N과 M (2) 이다. 이전 N과 M (1)과 문제가 비슷하다. 이번에는 오름차순이어야 한다는 조건이 추가되었다. 이번에도 역시 백트래킹 문제이다. 이번에는 한 숫자를 골랐다면 다음자리에는 그보다 작은 숫자가 올 수 없기 때문에 check 배열에서 고른 숫자 이하의 자리는 모두 +1 해주고 빠져나오면 -1을 해 주었다. 물론 고를때에는 1이 아닌것으로가 아닌 0인지로 판단해주었다. 언어는 python을 사용하였다. def func(cnt): if cnt == m: for i in range(m): print(list1[list2[i]], end = ' ') print() for i in range(n): if check[i] == 0: for j in range(i+1): check[j..

백준 15649번 N과 M (1) 문제이다. 문제는 다음과 같다. 문제만으로 규칙을 모르겠다면 입출력을 봐주자. 문제가 파악되었다면 문제를 풀어보자. 이번 문제는 백트래킹 문제이다. 두번째 입력값인 m이 수열의 길이이기 때문에 이 값을 하나씩 증가시키며 모든 경우를 살펴보고 조건에 맞다면 출력하도록 짜준다. 언어는 C++을 이용하였다. #include using namespace std; int n, m; int arr[8]; int arr2[8]; int check[8] = {0,}; void func(int cnt){ if(cnt == m){ for(int i = 0; i m; for(int i = 0; i < n; i++){ arr[i] = i + 1; } ..