Develop/algorithm10 [알고리즘] DP (Dynamic Programming) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. DP는 두가지 종류가 있다. 탑다운 DP 바텀업 DP 그 중 탑다운 DP에 대해 알아보도록 하자. 0. 백트래킹 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 위 문제를 백트래킹을 이용해 풀어보자. 위와 같은 풀이가 나올 것이다. 그렇다면 이번엔 다음의 문제를 봐보자. https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며,.. 2024. 3. 7. [알고리즘] 백트래킹 2 (Backtracking) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 해당 필기는 2024.02.15 - [Develop/algorithm] - [알고리즘] 백트래킹 (Backtracking) 에서 이어집니다. 목차 1. 기존 백트래킹 변형 2. 2차원 백트래킹 1. 기존 백트래킹 변형 앞선 포스팅에서 우리는 3가지 형태의 템플릿을 보았다. 이번엔 이를 다른 형태로 변환해 사용해보도록 하자. 이전의 백트래킹(1, 2, 3 템플릿)은 cur가 채운 개수 기준이었다. 새로운 백트래킹 형식은 다음과 같다. 여기서의 cur는 여태까지 본 원소의 개수, cnt는 고른 원소의 개수가 된다. 이를 실제 문제풀이 형식에 맞추어 변형해보면 다음과 같이 바뀐다. 만약 위 코드를 응용해, 3개 이하의.. 2024. 2. 23. [알고리즘] 백트래킹 1 (Backtracking) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 목차 0. 백트래킹의 목적 1. 백트래킹의 특징 2. 기본 구조 3. 1번 템플릿 4. 2번 템플릿 5. 3번 템플릿 6. 가지치기 0. 백트래킹의 목적 코드를 짜다보면 n중 반복문을 짤 경우가 생기게 된다. 이를 하드코딩으로는 거의 해결할 수 없게되므로 재귀함수를 이용하여 짜게 되는데 재귀함수를 이용한 완전 탐색 알고리즘을 백트래킹이라고 한다. 간단히 말해서는 정해지지 않은 n중 for문을 짜기 위한 목적의 알고리즘이라고 생각해도 된다. 1. 백트래킹의 특징 백트래킹의 특징은 다음과 같다. 진입장벽이 높다. (재귀함수 사용) (후술할) 기본 템플릿에서 내용을 수정하려면 재귀에 대한 높은 이해도를 요구한다. 한번.. 2024. 2. 15. [알고리즘] 이진 탐색 (Binary Search) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 목차 0. Intro 1. 이진탐색의 아이디어와 기본 구현 2. 이진탐색 응용 3. 매개변수 탐색 0. Intro https://namu.wiki/w/%EC%97%85%20%EC%95%A4%20%EB%8B%A4%EC%9A%B4#toc 업 앤 다운 - 나무위키 가장 많은 경우에 룰로 사용하는 5번 안에 맞히기의 경우를 생각하여 보자. 중간값만을 부르는 전략(최적의 전략)을 선택한다면 log250≈5.64⋯\log_2 50 \approx 5.64 \cdotslog250≈5.64⋯이므로 이론상 namu.wiki 위 링크를 읽어보면 이진 탐색의 수학적 핵심을 알 수 있다. 요약하자면 중간값만을 부르는 최적의 전략을 .. 2024. 2. 2. 이전 1 2 3 다음
