코딩 테스트/JUNGOL
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1106 : 장기코딩 테스트/JUNGOL 2021. 11. 25. 12:20
Intermediate_Coder/백트래킹-DFS/장기 문제 N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자. 입력 형식 첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다(1≤N, M≤100). 둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다. 단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다. 각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다. 출력 형식 말이 졸을 잡기 위한 최소 이동 횟수를 출력한다. 입력 예 9 9 3 5 2 8 출력 예 2..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/2217 : DNA 조합코딩 테스트/JUNGOL 2021. 11. 11. 09:54
Intermediate_Coder/백트래킹-DFS/DNA 조합 문제 도훈이는 학교에서 배운 유전자 실험을 이용해서 자신만의 실험을 계획하고 있다 (프로그램을 작성해주는 복제인간을 만드는 것이 목표라고 한다). 도훈이가 갖고 있는 DNA 조각은 n(2 TACAGATTA TACA+ACA -> TACA TAC+TACA -> TACA ATAC+TACA -> ATACA TACA+ACAT -> TACAT 입력 형식 첫 줄에 n이 입력되고, 두 번째 줄부터 n개의 줄에 걸쳐 각 DNA 조각이 입력된다. DNA조각의 길이는 1 ~ 7 이다. 출력 형식 첫 번째 줄에 n개의 DNA를 모두 조합해서 하나의 DNA 순열로 만들었을 때 최소 길이를 출력한다. 입력 예 4 | 3 GATTA | ABC TAGG | BCD ATC..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1409 : 벽장문의 이동코딩 테스트/JUNGOL 2021. 11. 5. 17:57
Intermediate_Coder/백트래킹-DFS/벽장문의 이동 문제 n개의 같은 크기의 벽장들이 일렬로 붙어져 있고 벽장의 문은 n-2개만이 있다. 한 벽장 앞에 있는 문은 이웃 벽장 앞에 문이 없다면(즉, 벽장이 열려있다면) 그 벽장 앞으로 움직일 수 있다. 그림은 7개의 벽장의 예이다. 그림에서 2번 벽장과 5번 벽장이 열려있고, 나머지 벽장은 닫혀 있다. 벽장 문은 좌우 어느 쪽이든 그 이웃 벽장이 열려 있다면 그 쪽으로 한 칸씩 이동할 수 있다. 그림에서 주어진 상태에서는 1번 벽장을 닫고 있는 벽장문을 오른쪽으로 한 칸 이동함으로써 1번 벽장을 사용할 수 있다. 이때 2번 벽장은 닫혀져 사용할 수 없다. 역시 5번 벽장이 열려 있으므로 4번 벽장 또는 6번 벽장 앞의 벽장문을 5번 벽장 앞으로..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1662 : 비숍코딩 테스트/JUNGOL 2021. 10. 21. 00:47
Intermediate_Coder/백트래킹-DFS/비숍 문제 서양장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다. 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다. 정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1824 : 스도쿠코딩 테스트/JUNGOL 2021. 10. 6. 11:39
Intermediate_Coder/백트래킹-DFS/스도쿠 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. (1) 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. (2) 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 ..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1027 : 좋은수열코딩 테스트/JUNGOL 2021. 9. 29. 11:38
Intermediate_Coder/백트래킹-DFS/좋은수열 문제 숫자 1 2 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다. 다음은 나쁜 수열의 예이다. (밑줄 부분때문에 나쁜 수열이다.) 33 32121323 123123213 다음은 좋은 수열의 예이다. 2 32 32123 1232123 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그 중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다. 입력 형식 입력파일은 숫자 N 하나로 이루어진다. N은 1 이..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1681 : 해밀턴 순환회로코딩 테스트/JUNGOL 2021. 9. 24. 17:27
Intermediate_Coder/백트래킹-DFS/해밀턴 순환회로 문제 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면 알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다. 태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자. 입력 형식 첫 줄은 배달해..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1889 : N Queen코딩 테스트/JUNGOL 2021. 9. 19. 23:12
Intermediate_Coder/백트래킹-DFS/N Queen 문제 체스에서 queen의 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다. 즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때, 그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다. N X N 크기의 정방형 체스판이 주어졌다. 우리는 거기에 N개의 queen을 배치하려고 하는데, 모든 queen들은 서로 잡아먹을 수 없어야 한다. 그렇다면 queen들을 어떻게 배치해야만 할까? 가능한 모든 경우의 개수를 출력한다. 입력 형식 queen의 수 N(1≤N≤13)을 입력 받는다. 출력 형식 N X N의 체스판에서 N개의 queen들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법..