본문 바로가기

알고리즘

 (82)
2022 KAUPC 2회 출제 후기 9월 17일에 제 2회 한국항공대학교 프로그래밍 경진대회 KAUPC가 개최됐다. 출제진으로 참가한 계기 문제를 풀면서 출제자의 의도가 무엇인지 생각하다 보니, 나라면 이 알고리즘을 사용해 어떤 문제를 만들 수 있을까에 대해서 생각하게 됐다. 이런 생각이 계속되다 보니 문제 출제에 관심이 생겼고, 마침 1회 KAUPC 출제진 참여 제안을 받아 출제진으로 참가하게 됐다. 하지만, 처음이라서 그런지 좋은 문제를 만들지 못했다. 그래서 다음 대회에도 출제진으로 나가는 것에 대해 고민을 하던 중 2회 KAUPC 출제진 제안을 받게 됐다. 그동안 구상한 문제들도 있었고 작년에 비해서 더 좋은 문제들을 만들 수 있다 생각해 수락을 했고 이렇게 2회 KAUPC 출제진으로 참가하게 됐다. 문제 제작 3문제를 구상했지만,..
백준 [1052] 물병 (Python3) 문제 링크 : https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 2의 제곱을 이용해 풀 수 있는 문제. 처음에 식을 만들어 문제를 풀었더니 WA를 받았다. 틀린 이유를 찾는 과정에서 1 ~ 10 개의 물병을 최대로 합칠 수 있는 경우에 대해 써본 결과 복잡하게 공식을 쓸 것도 없이 완전탐색을 통해 해결할 수 있단 것을 알았다. N 합치는 과정 1 1 -> 1개 2 1, 1 -> 2 -> 1개 3 1, 1, 1 -> 2, 1 -> 2개 4 1, 1, 1..
백준 [1059] 좋은 구간 (Python3) 문제 링크 : https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 2번 틀리고 해결한 문제, 이 문제에서 함정이 있는데, 예제만 보고 배열을 구성할 경우 20%에서 틀릴 것이다. 완전 탐색 입력 받은 집합 S를 오름차순 정렬해, N보다 처음으로 값이 큰 위치와 그 전 위치의 값을 각각 A, B라고 하자. 지문 범위에 맞추기 위해 A는 1 더하고, B는 1 뺀다. 만약, 정확히 일치하는 S의 원소가 있다면 0을 출력하고 프로그램을 종료한다. 최소 값이 A 부터 N - 1까지는 지정할 수 있는 최대 범위가 N ~ B이고, 최소 값이 N이면 지정할 수 있는 최대 ..
백준 [10164] 격자상의 경로 (Python3) 문제 링크 : https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 완전 탐색 BFS를 통해 격자까지 가는 경우의 수 * 격자에서 N * M 번 수가 있는 곳까지 가는 경우의 수를 곱한다. N크기가 작았기 때문에 AC를 받을 거라 생각했지만, 부분점수만 맞았다. 이유를 생각해보니 경우의 수를 세야 하기 때문에 이전에 갔던 곳을 또 갈 수 있다. 즉, 방문 처리를 하지 못하기 때문에 N, M이 커질 수록 탐색 횟수..
백준 [2225] 합분해(Python3) 문제 링크 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 완전 탐색 0 ~ N까지 중복 포함 K개를 골라 합이 N인지 확인한다. O(N ^ K) == O(200 ^ 200)이기 때문에 시간 초과다. 완전 탐색 최적화 - 탐색 횟수 줄이기 어떤 수 A가 있다면, 이 수는 아무튼 몇 개의 경우로 만들어진 수일 것이다. 각 수들이 각각 몇 개의 경우로 이루어질 수 있는지만 알 때 이 수들을 더해서 나온 B가 만들어질 수 있는 경우의 수는 B를 만드는데 사용된 수를 만들 수 있는 경우의 수를 더한 것과 같다. 완전 탐색 최적화 - DP 이차원 dp 테이블을 만든다. dp[..
백준 [14671] 영정이의 청소(Python3) 문제 링크 : https://www.acmicpc.net/problem/14671 14671번: 영정이의 청소 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 영정이의 자취방 바닥의 크기 N과 M, 그리고 바닥에 있는 곰팡이의 개수 K가 주어진다. (2 ≤ N, M ≤ 1,000) (1 ≤ K ≤ 100,000) 둘째 줄부터 www.acmicpc.net 완전 탐색 시간이 지날 때마다 곰팡이를 퍼뜨려, 곰팡이가 전부 퍼지는 때가 있는지 확인한다. 하지만, 특정 데이터셋의 경우, 시간이 아무리 지나도 곰팡이가 전부 퍼지지 않는다. 또한, 얼마나 시간을 두고 계산해야 할지에 대해 기준도 난해하다. 완전 탐색 최적화 - 탐색 범위 좁히기 곰팡이가 전부 퍼지게 되는 특정 상황을 찾아본다. 1. 곰팡이가..
백준 [14931] 물수제비(Python3) 문제 링크 : https://www.acmicpc.net/problem/14931 14931번: 물수제비 (SUJEBI) 급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리 www.acmicpc.net 완전 탐색 1 ~ 1,000,000 까지 순회하면서 간격을 1, 2, 3, ..., L을 두어 탐색했을 때 탐색한 값의 합이 가장 큰 걸 구한다. 간격별로 탐색 횟수를 나열해보면 아래와 같다. - 간격이 1일 땐, 1,000,000번 탐색. - 간격이 2일 땐, 500,000번 탐색. - 간격이 3일 땐, 333,333번 탐색. - 간격이 4일 떈, 250,000번 탐색. ...
백준 [1748] 수 이어 쓰기 1(Java) 문제 링크 : https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 완전 탐색 1부터 N까지의 수를 문자형 형태로 만들어 이어붙인뒤, 그 길이를 구한다. 하지만, 제한 시간이 c++ 기준 0.15초 이내로 풀어야 하고 메모리 제한도 128MB이기 때문에, 시간과 메모리 초과가 발생한다. 완전 탐색 최적화 - N의 탐색 범위 최소화 수를 나열해보면 다음 결과를 도출할 수 있다. - 1부터 N 까지의 수는 모두 일의 자리를 가지고 있다. - 만약, N이 10 이상이면, N - 9 개의 십의 자리를 가지고 있다. (1 ~ 9 총 9개) - 만약, N이 100 이상이면 N - ..

티스토리툴바