알고리즘52 P2110. 공유기 설치 문제 링크: https://www.acmicpc.net/problem/2110 설명 이 문제는 어떤 풀이를 써야할지 잡히지 않아 어려움이 있었다. 일단 가장 인접한 두 공유기 사이의 거리를 최대로 라는 말이 이해가 가지 않았다. 이 말은 즉, 공유기 사이의 거리가 최대한 떨어져있도록 설계하라는 말이다. 이분탐색으로 풀려면 어떻게 해야할까? 가장 인접한 두 공유기 사이의 거리를 이분 탐색으로 구하여, 해당 거리에서 설치해야하는 공유기 개수를 만족하는지 확인하는 것이다. 예시를 살펴보자. 예시는 공유기 사이의 거리가 차례로(정렬된 상태에서) 1, 2, 4, 8, 9이다. 이때 최소한의 거리는 1이고 최대는 8이므로 거리의 중앙값은 (1 + 8) // 2로 4가 mid가 된다. 그럼 이 값을 기준으로 현재 집.. 2023. 5. 4. P2493. 탑 문제: https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 설명 하나의 리스트에 넣고 오른쪽부터 시작하여 비교하면서 빼는 방식으로 하면 시간초과가 발생한다. 처음에 리스트에 넣을 때부터 비교하면서 넣는 방법은 어떨까? 주어진 값은 6-9-5-7-4 이다. stack = [] : 최댓값을 저장할 스택, 이후에 들어오는 값들과 비교한다. result = [] : 결과값을 저장할 스택 일단 신호를 수신받으려면, 최댓값이 크거나 같아야 한다. 스택이 비.. 2023. 5. 4. P2805. 나무 자르기 - 문제: https://www.acmicpc.net/problem/2805 설명 이 문제를 풀 때 계속 실수한 점은 M 미터의 나무를 잘랐다고 반복을 멈췄다는 것이다. 문제를 읽어보면 이때, **적어도 M미터**의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 **높이의 최댓값**을 구하는 프로그램을 작성하시오. 적어도 M미터, 높이의 최댓값에서 최적값이 따로 있을 수 있기 때문이다. 여기서 최소한 M미터를 챙겨가는 절단기의 최대 높이 K를 구한다는 최적화 문제는 '결정 문제'로 바꾸어 풀 수 있다. 이것을 파라메트릭 서치라고 한다. 자세한 내용 참고: https://sarah950716.tistory.com/16 즉 우리는 나무의 높이 배열이 주어졌을 때, 절단기의 높이가 x인 경우 잘린 나무.. 2023. 5. 4. P11053. 가장 긴 증가하는 부분 수열 문제: https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 문제, 줄여서 LIS(Logest Increasing Subsequence)라고도 한다. 크게 완전탐색, DP, 이진탐색 방식으로 풀이할 수 있다. 유사한 문제가 여럿 있는데 이 문제는 DP(Dynamic Programming)방식으로도 풀리는 문제이다. 이번에는 위 3가지 방식으로 모두 풀이하겠다. 일단 LIS란 무엇일까? LIS는 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분 수열 중 가장 긴 수열을 말한다. 꼭 부분수열의 원소들이 배열에 이어져있지 않아도 된다. 완전 탐색 증가 부분수열은 다음 특징을 갖는다. 정수 i,j에 대해 i < j이면, S[i] < S[j]이다.(0 인접한.. 2023. 5. 4. Greedy 문제 풀이 - 잃어버린 괄호, 신입사원, 멀티탭 스케쥴링 Greedy 문제는 특별한 방식이 있기보다는 그리디 문제임을 확인하고, 문제를 최적화할 수 있는 우선 순위를 찾는 것이 필요하다고 생각한다. 최적화이기 때문에 모든 문제에 범용적으로 적용되는 것은 아니고, 문제마다 최적화할 수 있는 방안을 빨리 캐치하는 것이 필요하다. 이때 직관을 요구한다고 생각한다. 문제를 풀이하기 위한 아이디어를 간략하게 정리해보겠다. 1541. 잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 적당히 괄호를 쳐서 식의 최솟값을 구하는 것이다. 예를들어, 55-50+40.. 2023. 5. 3. P11047. 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 설명 K원을 만드는데 필요한 동전 개수의 최솟값을 구하기 위해 K원보다 작은 수 중 가장 인접한 수부터 하나씩 빼기 시작했다. 이진 탐색 본인은 인접한 수를 찾을 때, 이진 탐색을 사용했는데 값을 업데이트할 때마다 K원보다 작은 수 중 가장 인접한 수를 찾고 빼는 방식을 사용한다면, 시간 초과가 발생한다. 이를 해결하기 위한 방법은 .. 2023. 5. 3. DP(Dynamic Programming)이란? - 스티커, 동전, LCS, 행렬 곱셈 순서 동적 프로그래밍이란? 동적 프로그래밍은 큰 문제를 풀 때, 큰 문제의 일부인 작은 문제를 푸는 과정에서 발생하는 중복을 해결하는 방법이다. 이때 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 것을 최적 부분 구조(Optimal Substructure)를 가졌다고 표현한다. 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 다음의 정의를 갖는다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 즉, n은 n-1과 n-2 피보나치 수를 모두 갖고 있다. 만약 이 문제를 재귀호출로 푼다면 어떨까? fib(n) { if (n == 1 or n == 2) then return 1 else return (fib(n-1) + fib(n-2)) } 이렇게 푸는 방식은 매우 비효율.. 2023. 5. 3. 이전 1 ··· 3 4 5 6 다음
