JUNGOL
-
JUNGOL...142일지 2021. 9. 23. 15:44
Intermediate_Coder/백트래킹-DFS/해밀턴 순환회로 문제 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면 알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다. 태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자. 입력 형식 첫 줄은 배달해..
-
JUNGOL...141일지 2021. 9. 20. 18:37
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들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법..
-
JUNGOL...140일지 2021. 9. 18. 15:57
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들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법..
-
JUNGOL...139일지 2021. 9. 17. 12:26
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들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법..
-
JUNGOL...138일지 2021. 9. 16. 01:51
N Queen > 문제은행 | JUNGOL : 정보올림피아드&알고리즘 JUNGOL www.jungol.co.kr 이상의 문제에서 새롭게 파악해야 할 용어가 존재하는데 크게 세 가지를 확인할 필요가 있어 보인다. 백트래킹 모든 경우의 수를 전부 파악하기 위한 알고리즘으로 상태 공간을 나타낼 수 있을 때 적합한 방식 상태 공간 특정 시스템에서 가능한 모든 구성의 집합 DFS 깊이 우선 탐색(Depth First Search)의 약자로 트리를 탐색할 때 가장 깊은 노드를 탐색한 뒤 다시 돌아가 루트에서 다음 노드의 탐색을 진행하는 탐색 방식 N Queen 문제 n 개의 퀸과 n * n 크기의 판이 주어질 때 모든 퀸이 서로를 공격하지 못하는 상태의 수를 구하는 문제 ※ 이 문제를 해결하기 위해 상태 공간 트리..
-
JUNGOL/Intermediate_Coder/자료구조/1124 : 색종이(고)코딩 테스트/JUNGOL 2021. 9. 15. 02:12
Intermediate_Coder/자료구조/색종이(고) 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 과 같은 모양으로 붙였다. 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다. 반면 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다. 검은색 색종이의 수와 각 색종이를 붙..
-
JUNGOL...137일지 2021. 9. 14. 22:02
Intermediate_Coder/자료구조/색종이(고) 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 과 같은 모양으로 붙였다. 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다. 반면 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다. 검은색 색종이의 수와 각 색종이를 붙..