PS/백준 문제 풀이 (167) 썸네일형 리스트형 [백준 2616번/Java] 소형기관차 https://www.acmicpc.net/problem/2616 [문제 분석] 길이 N의 수열을 M개씩 3개로 묶을 때 최댓값을 구하는 문제이다.[알고리즘]1. 연속된 수열을 가져와야하기 때문에 누적합을 사용하여 시간을 단축한다.2. 이 문제는 결국 모든 경우의 수를 살펴봐야하는데 그것을 얼마나 효율적으로 메모이제이션하느냐에 따라 달려있다. DP[i][j] = i번 열차가 j번 수열까지 도달했을 때 최대 값 이 점화식은 배낭문제에서 아이디어를 가져올 수 있다. 다만 배낭문제는 각 배낭에 각 객체를 넣을 수 있을지 없을지 확인하는데 이것은 연속된 객체를 삽입할지 말지 결정해야하는 다른점이 있다. 그렇다면 점화식은 어떻게 구성해야할까 먼저 예제로 시뮬레이션 해보자. N = 7, M = 235 40 50 .. [백준 2240번] 자두나무 (C++) https://www.acmicpc.net/problem/2240 최댓값을 구하는 문제로 가장 먼저 그리디, 완전탐색, DP가 떠오르는 것이 일반적이다.어떻게 풀 수 있을까? 먼저 최대 자두가 떨어지는 숫자는 1000이고 움직일 수 있는 횟수는 30이다. 1. Greedy탐욕법으로 풀 수 있을까? 탐욕법이 성립하기 위해서는 지금 선택하는 조건이 이후의 선택에 영향을 주어선 안된다.즉, 2번에서 자두가 떨어질 때 이동하여 잡는 이 선택이 뒤에서 영향을 주어선 안되는데 조금만 생각해도 당연히 영향을 줄 수 밖에 없는 구조이다. 그러므로 탐욕법으로는 풀 수 없다.2. 완전탐색완전탐색으로는 정확도만 풀이가 가능하다. 한 지점에서 취할 수 있는 경우의 수는 두가지다. 이동하거나, 가만있거나 그러므로 2^30의 시.. [백준 2169번] 로봇 조종하기 (C++) https://www.acmicpc.net/problem/2169 꽤 생각할 것이 있는 다이나믹프로그래밍 문제였다. 먼저 이 왜 다이나믹 프로그래밍인가? 1. N이 약 1000으로 백트래킹으로 모든 경우의 수를 다 진행할 시 당연히 시간초과에 걸린다.2. 한 지점에 도착할 수 있는 경우의 수가 정해져있다.3. 2번에 의해 큰 문제를 작은 문제로 쪼갤 수 있다. 이 근거로 다이나믹 프로그래밍이라고 유출할 수 있겠다. 그렇다면 어떻게 풀어야할까? 처음에는 0,0 에서 시작하는 재귀 + DP를 생각했다. 그러나 문제가 있었다. 이 문제는 왼쪽과 오른쪽으로 이동을 할 수 있다. 1 2 34 5 67 8 9 라고 할 때 재귀를 진행하면 1번에서 2번으로 이동하면 2번은 다시 1번으로 이동할 수 있다. 그.. [백준 17298번] 오큰수 (C++) https://www.acmicpc.net/problem/17298 O(N^2)으로 풀면 쉽게 풀리지만 그러면 골드난이도가 아닐 것이다. N이 크기 때문에 O(N) 혹은 O(N Log N)으로 풀어내야한다.어떻게 최적화 할 수 있을까? 2, 9, 10, 2, 11 예제를막대로 그려보면 다음과 같다. 그리고 각 A, B, C, D, E의 꼭대기에서 오른쪽으로 갈 때 가장먼저 부딫히는 막대의 크기를 출력해야하는 문제다. 아하.. 그렇다면 맨 오른쪽에서부터 막대를 새우면서 진행하면 될 것 같다. 1. 11 막대를 새운다.2. 2막대를 새우고 11과 비교한다. 오큰수: 113. 10 막대를 새우고 2와 먼저 비교한다. 앗.. 2보다 10이 더 크다. 즉, 이제 2는 절대로 누군가의 오큰수가 될 가능성이 없다. .. [백준 1949번] 우수 마을 (C++) https://www.acmicpc.net/problem/1949 이전에 비슷한 문제의 유형을 풀어본적이 있기 때문에 트리에서 다이나믹 프로그래밍 문제라는 것을 알 수 있었다. 사실 말은 거창하지만 DFS + DP 와 다를 것이 없다. 문제를 살펴보자 '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.뭔가 조건이 많아보이는데 사실 1,2번을 만족하면 3번은 자동으로 될 수밖에 없다... [백준 1719번] 택배 (C++) https://www.acmicpc.net/problem/1719 위 그림에서 1번에서 4번으로 가기 위해 최단거리로 이동하는 방법은 3번으로 이동한 후 3번에서 4번으로 이동하는 것이다. 그리고 결과값으로 처음으로 이동한 노드의 번호를 출력하는 것이 문제다. 전체 노드의 개수는 200, 간선의 개수는 10000이므로, 다익스트라알고리즘을 N번한다고 하면 O(N^3) 으로 문제를 해결할 수 있다. 그렇다면 대략적인 알고리즘은 이렇게 될 것이다. 1. 큐에 현재 시작 노드의 이웃 노드들을 집어넣는다.2. 집어넣을 때 현재 시작 노드를 따로 관리하여 만약 다익스트라 DP가 갱신된다면 첫 입력값을 넣어준다. 오 문제가 해결된 것 같다. 코드로 바꿔보면 #include #include #define MAX.. [백준 1082번] 방 번호 (C++) https://www.acmicpc.net/problem/1082 방 번호는 무한으로 살 수 있으므로 N = 10이고 최대 값은 50이다. 이 때 모든 경우의 수를 다 해보는 것은 약 10^10으로 10억이상으로 엄청난시간이 걸린다. 중요한 추론은 숫자를 가장 길게 만들어야한다는 것이다. 그리고 91111 보다는 92000이 크고 100000이 더 크다. 즉 가장 비용이 적은 것들을 사용해서 먼저 가장 긴 방번호를 만들어둔 후 각 자리수마다 하나씩 비교하며 더 큰 값을 사용할 수 있을지 검사한다. 이 방법은 N^3 의 시간밖에 소요되지 않는다. 그리고 각 번호의 개수를 배열에 저장해두고 큰 값부터 다음 값이 가능한지 확인한다. 왜 큰 값부터 해야하냐면 만약 작은것부터 시행했을 때는 다음과 같은 문제가 .. [백준 1033번] 칵테일 (C++) https://www.acmicpc.net/problem/1033 1:3, 4:7 등 여러 비율이 주어지고 결국 이어지는 길목을 똑같이 이어줘야하는 문제이다. 만약 1번 : 2번 = 4 : 72번 : 3번 = 3 : 10 이라하면 1번 : 2번 : 3번이 성립하는데 비율이 다르기 때문에 이것을 통일해줘야한다.2번이 처리해야하는 비율은 3과 7이다. 그렇다면 21로 비율을 맞출 수 있다. 21로 맞추면 1번에는 x3을 해줘야하고 10에는 x7을 해줘야한다. 그렇다면 12 : 21 : 70 이고 이것이 정답이다. 만약 2번:4번 = 5 : 3 이라면 2번은 3,5,7을 갖고있고 이것을 통일해야한다. 문제는 가장 적은 비율을 요구한다. 그러므로 최소공배수를 구해야한다는 것을 알 수 있다. 또한 문제가.. 이전 1 2 3 4 ··· 21 다음
