Algorithm/백준 BOJ 문제풀이 (4) 썸네일형 리스트형 [백준] 2220 힙정렬 문제풀이 C++ :: 그리디 알고리즘 :: DANIDANI 2220 힙 정렬 www.acmicpc.net/problem/2220 2220번: 힙 정렬 힙은 자료의 추가, 우선순위가 제일 높은 자료의 삭제가 가능한 자료구조이다. 이와 같은 힙에는 두 종류가 있는데, 각각 최소-힙, 최대-힙이다. 이 문제에서는 최대-힙을 다루기로 하자. 이와 같 www.acmicpc.net 문제를 보고, 먼저 예제의 답을 거꾸로 삭제해보았다. 삭제를 해보면서 보인 규칙은 크게 두 가지였다. 1. n번째 수를 삭제하면 n-1번째 수의 최대 swap 형태가 된다. 2. 항상 마지막은 1이다. 이를 바탕으로 생각한 문제 접근 방법은 다음과 같다. 1. 1부터 n까지 수를 차례로 힙에 넣는다. 2. 이때, k번째 수를 넣고 k와 1을 swap 한다. 3. 최대 힙을 구성한다. 4. 2-3.. [백준] 2293 동전1 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI 2293 동전1 https://www.acmicpc.net/problem/2293 동전 0 문제는 그리디 알고리즘을 활용했다면 동전 1 문제는 DP(Dinamic Algorithm, 다이나믹 알고리즘)을 사용한다. 예제에서 동전은 총 3 종류, 1 2 5 가 있다. arr 배열로 동전의 가치들을 저장해주고 문제는 dp 배열을 사용하여 접근한다. 먼저 dp [0]=1로 두는데, 이는 아무 동전도 선택하지 않은 경우도 하나의 경우의 수인 것이다. 각각의 동전에 대하여 for문을 돌린다. 먼저 동전 1에 대해서 10원을 만드는 경우의 수를 계산해준다. 1(=j)부터 10(=k)까지 dp[j] += dp[j - 1] 을 해준다. 동전 2에 대해서는 0원과 1원은 만들지 못하니 패쓰하고 j = 2부터 10(=k).. [백준] 1463 1로 만들기 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI 1463 1로 만들기 https://www.acmicpc.net/problem/1463 DP(Dinamic Programming, 다이나믹 프로그래밍) 으로 푸는 문제! 시간 복잡도는 O(N) bottom-up 방식으로 for문을 사용해서 풀었다. index 가 n+1 인 배열을 만든다. index가 문제에서의 연산하는 숫자! dp [1] = 0로 초기화를 해준다. (1일 경우 연산 안 해도 됨) 할 수 있는 연산은 3가지 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 3가지 경우의 최솟값을 저장하면 된다. 예를들어 dp [4]인 경우 2로 나누어 떨어지는데 dp[4/2] + 1 = dp [2] + 1 = 2, dp [3] + 1 =.. [백준] 1806 부분합 문제풀이 C++ :: 투 포인터 :: DANIDANI 1806 부분합 https://www.acmicpc.net/problem/1806 기본적인 투 포인터 알고리즘 문제! (시간복잡도 O(N)) 문제 딱 보고 이중 for문으로 풀면 시간초과 날 수 있다. (시간복잡도 O(N^2)) #include #include #include using namespace std; int main() { int n, s; cin >> n >> s; vector arr(n); for (int i = 0; i > arr[i]; int start = 0, end = 0, sum = 0, minLen = 0x7FFFFFF; while (start = s) {// 현재 포인터의 합이 s보다 크거나 같으면 start ++ minLen = mi.. 이전 1 다음
