알고리즘/문제 풀이50 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. 이전 1 ··· 3 4 5 6 다음
