본문 바로가기

알고리즘/백준

 (61)
백준 [15971] 두 로봇 (Python3) 처음부터 꼬아서 생각했다가 복잡하게 푼 문제 경로를 계산하는 방법은 3가지가 있다. A가 한 칸 뒤로 가고, B가 한 칸 앞으로 감. B가 한 칸 뒤로 가고, A가 한 칸 앞으로 감. A, B가 그냥 현재 위치에서 통신 위 3가지 경우를 고려하면 A부터 출발하든, B부터 출발하든 특정 간선 하나는 지나지 않는다. 이 간선은 바로 A부터 B 또는 B부터 A까지 가는 간선 중 가장 비용이 큰 간선이다. 이렇게 구한 총 비용 중, 가장 큰 비용을 빼면 답이 나온다. 나는 위 3가지 경우를 다 고려해서 A부터 B까지 모든 경로 구한뒤에 B부터 탐색을 시작해, 매 지점마다 저 3가지를 고려했다. 그래도 N의 범위가 작기 때문에 통과는 됐지만 좋은 해결책은 아니었다. from collections import de..
백준[17671] 로봇 (Python3) 다3 치고 생각보다 풀만했던 문제. 관찰을 하면서 탐색 범위를 조금씩 좁혀나간다면 충분히 해결할 수 있다. 랑이집사님이 알려주신 완전 탐색부터 시작하는 최적화를 잘 써먹은 문제 완전 탐색 로봇의 움직임을 3가지를 나눠 계산한다. 1. 왼쪽으로 한 칸 갈 때 2. 가만히 있을 때 3. 오른쪽으로 한 칸 갈 때 이 방법으로 문제를 해결할 경우 O(3^N)으로 시간 초과가 난다. 이를 줄이기 위해, 로봇이 움직이는 거리를 높이거나, 일부 로봇은 움직이지 않는 식으로 탐색 범위를 좁혀나가야 한다 생각했다. 완전탐색 최적화 1 처음부터 로봇을 최소한만 겹칠 수 있게 이동 겹치게 된다면 안 겹치도록 입력된 위치에서 + 를 해준다. 하지만, 이 방법은 로봇들이 서로 가까이에 있다면, 불필요하게 많이 이동하는 경우가 ..
백준 [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번 탐색. ...

티스토리툴바