반응형 알고리즘 썸네일형 리스트형 [BOJ 12920] 평범한 배낭 2 [문제] : https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 � www.acmicpc.net [필요 개념] - DP , 배낭 문제 (Knap-sack) - 비트마스크 [풀이] 전형적인 배낭문제 (Knapsack)처럼 보이나, 이 문제에서는 특별하게 고려해줘야 하는 부분이 있다. 바로 같은 종류의 물건의 개수가 2개 이상일 수 있다는 것이다. 원래 배낭문제에서는 각 물건이 하나씩 있어, 해당 물건을 넣거나 빼는 두가지 경우만 있었는데.. 소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법 어떠한 자연수 N이 소수인지를 판별하는 방법은 여러 가지 방법이 있다. 그중에서 너무 난도 높은 것은 제외하고 충분히 PS에서 쓸만한 방법을 알아보자. 우선, N이 소수인지를 판별하는 경우와 N이하의 소수가 몇개있는지, N이하의 소수를 모두 구하는 경우 두가지로 보통 나뉜다. 1. N을 2부터 N-1까지 모두 나누기 소수는 1또는 자기 자신으로만 나누어지기 때문에 위의 방법으로 N이 나누어 떨어지지 않는다면 N은 소수라고 할 수 있다. 만약, N이 어떤 두 수로 나누어진다고 한다면, N = p*q의 형태가 되고, p와 q 둘 중 하나는 반드시 $ \sqrt{N} $의 값 이하일 것이다. 따라서 N-1까지 나눌 필요는 없고, $ \sqrt{N} $까지만 나눠도 소수인지 판별이 가능하다. 물론, 이 방법을 .. [BOJ 2517] 달리기 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 세그먼트 트리(Segment Tree)를 이용한 문제이다. 각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다. 각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 여기.. [BOJ 2568] 전깃줄 - 2 문제 출처 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 유형의 문제이다. 전깃줄이 순서없이 입력되기 때문에 A 또는 B를 기준으로 정렬을 해주어야 한다. A를 기준으로 정렬한다면, 정렬된 후의 B 수열을 가지고.. LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 주어진 수열에서 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다. (당연히 어려운 문제로는 NlogN을 요구하는 문제가 나온다...) [개념] LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다. 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다. 예를 들어 위와 같은 길이가 8인 수열이.. [BOJ 11066] 파일 합치기 (https://www.acmicpc.net/problem/11066) 이 문제는 Dynamic Programming을 이용하는 문제이며, Knuth's Optimization을 이용하여 최적화를 한다. Knuth's Optimization 게시글 (https://wogud6792.tistory.com/20) 위 문제는 파일을 합치는 모든 경우 중에서, 합이 최소가 되는 경우를 찾는 문제이다. 만약 C1~C4를 합친다면, C1 + C2~C4 또는, C1~C2 + C3~C4 또는, C1~C3 + C4와 같이 부분문제가 만들어질 수 있다. 이 때, C2 ~ C4, C1 ~ C3의 경우도 또 다시 부분문제로 나뉘어 질 수 있다. ex) C2 + C3~C4 또는 C2~C3 + C4 / C1 + C2~C3 또는 .. Knuth's Optimization Knuth's Optimization은 Dynamic Programming의 점화식이 아래와 같은 특정 조건을 만족하는 경우 사용할 수 있는 "최적화" 기법이다. i) DP 점화식 형태 $ dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] $ $ (i\le k [BOJ 1725] 히스토그램 1725번 (히스토그램) 위의 문제는 분할 정복 알고리즘을 이용해서 해결할 수 있다. 분할 정복은 주어진 문제를 부분 문제들로 나누어 푸는 것이기 때문에 이 문제 또한 히스토그램을 나누어 푸는 것이 핵심이다. 따라서 주어진 n개의 막대그래프를 절반으로 나누게 되면 결국 찾고자 하는 가장 큰 직사각형은 다음 세가지중 하나에 속하게 된다. 1. 왼쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 2. 오른쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있는 경우 1번과 2번의 경우에는 재귀 호출을 이용하면 되고, 3번의 경우만 특별히 고려한다면 답을 구할 수 있을 것이다. 문제에서 출력이 20억을 넘지 않는다고 하였으니, 변수 자료형을.. 이전 1 2 3 4 5 6 7 다음
