본문 바로가기
반응형

PS 문제 풀이/Jungol101

[Jungol] 정올 1161 하노이1 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=441&sca=2070 Input 3 Output 1 : 1 -> 3 2 : 1 -> 2 1 : 3 -> 2 3 : 1 -> 3 1 : 2 -> 1 2 : 2 -> 3 1 : 1 -> 3 ▶ hanoi(원판 수, 시작 기둥 번호, 도착 기둥 번호) hanoi(3, 1, 3)으로 3번 기둥의 바닥에 3번 원판이 놓여야 하므로 1, 2번 원판을 2번 기둥으로 옮겨야 한다. 결과적으로 3번 원판이 없다고 생각하면, hanoi(2, 1, 2)로 나타낼 수 있다. 즉, 도착 기둥번호가 3번이 아닌 2번으로 하면서 원판 개수도 2개인 문제와 같다. 위의 작업이 끝나서 1, 2번 원판이 두번째 기둥에 있다.. 2021. 2. 27.
[Jungol] 정올 1336 소수와 함께 하는 여행 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=615&sca=30 Input 1033 8179 Output 6 출발점으로 부터 숫자 자릿수 차이가 한 개가 발생하는 숫자들을 탐색해 갑니다. 이때, 자릿수 차이와 함께 소수여야 하므로 1000 ~ 9999까지의 수 중 에라토스테네스의 체를 이용해서 미리 소수를 구합니다. ※ 코드에서는 prime[i] = 1인 경우, 숫자 i는 소수가 아닙니다. 두 수의 자릿수 일치 정도 확인 #define _CRT_SECURE_NO_WARNINGS #include const int LM = 10000; struct Bus { int num, time; } que[LM]; int start, end; int .. 2021. 2. 26.
[Jungol] 정올 1078 저글링 방사능 오염 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=3040 Input 7 8 0010000 0011000 0001100 1011111 1111011 0011100 0011100 0001000 3 5 Output 9 0 입력받을 때, 저글링 표시를 『-1』로 해서 저장합니다. scanf("%1d", &map[i][j]);로 공백없는 숫자를 한 자리씩 받을 수 있습니다. 또한, BFS 탐색할 때, 저글링이 방사능이 걸려 죽는시간이 3초를 시작시간으로 합니다. ※ Input Data는 열의 크기, 행의 크기 순이므로 주의 #define _CRT_SECURE_NO_WARNINGS #include struct zergling { int x, y.. 2021. 2. 26.
[Jungol] 정올 1661 미로 탈출 로봇 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=50 Input 8 7 1 2 7 5 11111111 00000111 10110011 10111001 10111101 10000001 11111111 Output 9 ※ 주어지는 Input Data가 열의 크기, 행의 크기 순으로 주어지므로 2차원 배열을 구성할 때 주의. ※ map[][] 크기는 100 × 100이므로 Queue에 최대 담기는 개수는 10000개 입니다. ※ scanf("%1d", &map[i][j]);를 통해 공백없이 연속해서 받는 숫자를 한 자리씩 처리할 수 있습니다. #define _CRT_SECURE_NO_WARNINGS #include #define I.. 2021. 2. 26.
[Jungol] 정올 1006 로봇 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=285 Input 5 6 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 4 2 3 2 4 1 Output 9 ※ 방문 확인: visited[101][101][5] → visited[x][y][1~4]: (x, y) 지점을 1~4번 방향으로 방문표시 ① 로봇은 현재 바라보고 있는 방향에서 1~3칸 전진할 수 있습니다. 1~3칸으로 이동가능한지 확인할 때, 범위를 벗어나거나 중간에 장애물이 벗어나는 경우 break 합니다. ex) 1칸 전진했을 때, 장애물을 만난다면 로봇은 2, 3칸 이상 전진도 불가능합니다. 하지만 1칸 전진한 곳이 .. 2021. 2. 26.
[Jungol] 정올 2058 고돌이 고소미 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2275&sca=4040 Input 5 2 2 4 4 3 4 4 2 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 Output 3 보통의 BFS 문제는 지날 수 없는 곳을 제외해서 최단경로를 탐색합니다. 하지만 위와 같이 somi 집에 도착하여 움직이지 않게 되면 dori는 somi의 근처로는 지나갈 수 없으므로 dori의 집으로 돌아가는 길이 없습니다. 따라서, 위의 case 처럼 시작위치에서 실질적인 최단거리가 되지 않더라도 두 고슴도치가 모두 집에 도착하기 위해서는 어느 한쪽이 길을 비켜주는 경로가 필요하며 그 중에서 최소 이동거리를 찾아야 합니.. 2021. 2. 26.
[Jungol] 정올 1148 최종 울트라-퀵 소트 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=428&sca=60 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com 문제 내용에서 "인접한 두 수를 서로 바꿔서 주어진 수열을 오름차순으로 정렬" 한다고 해서 단순하게 버블 정렬의 원소 교환횟수를 묻는 문제로 생각해서 안됩니다. arr = {1, 3, 4, 5, 2}를 선택.. 2021. 2. 23.
[Jungol] 정올 3519 Tutorial : 합병(병합)정렬(Merge Sort) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2859&sca=3010 Approach ▶ 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com #include #define LM 500005 int N, arr[LM], copyArr[LM]; void input() { scanf("%d", &N); for (int i = 0; i < N;.. 2021. 2. 23.
[Jungol] 정올 1889 N Queen 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162 Input 4 Output 2 N이 4일 때, 나오는 경우는 두 가지이다. 한 행에 놓을 수 있는 여왕말의 개수는 1개 입니다. 그렇기 때문에 행마다 DFS 탐색을 하면서 1~N까지의 열에 놓을 수 있는지를 확입합니다. chk_vertical[i] = i 열에 여왕 존재 여부 check_diagonal_1[row + i] = 아래 그림의 대각선은 위치가 (x, y)일 때, (5, 5) ↔ (4, 6) ↔ (6, 4) ▶ x + y가 같습니다. check_diagonal_1[10] = 1에 해당 check_diagonal_2[row - i + N] = 아래 그림의 대각선은 위치가 (x,.. 2021. 2. 23.
[Jungol] 정올 1901 소수 구하기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1174&sca=20 Input 2 8 15 Output 7 13 17 ① M이 소수인지 아닌지 확인 ② M-i 혹은 M+i가 소수가 아닌지 확인합니다. (소수에 해당되느느 숫자 출력하고 종료) ※ 소수 여부 판단 소수는 1과 자기자신을 제외하고 나누어 떨어지지 않는 숫자를 의미합니다. 특정 숫자 Num이 소수인지 확인할 때, 2 ... Num-1까지 나누어 떨어지는지 확인하면 되지만 수학적으로는 Num의 제곱근까지 범위를 조정해도 상관없습니다. ex) 9의 제곱근 = 3 → [2, 3] 24의 제곱근 = 4.xx → [2, 4] 49의 제곱근 = 7 → [2, 7] bool isPrime(i.. 2021. 2. 21.
반응형

티스토리툴바