hellogaon

탐욕법(Greedy)은 각 단계마다 지금 가장 좋은 방법만을 선택하는 기법입니다.이러한 방법을 이용하여 원하는 답을 무조건 찾을 수 있는지 증명하는 방법은 매우 어렵기에 대회에서는 이러한 방법이 예외가 없다고 생각이 된다면 증명없이 기법을 사용합니다.가장 좋은 방법만 선택하여 가기에 구현이나 시간복잡도는 크지 않지만문제가 탐욕법을 이용하여 푸는 문제인지 파악하기는 어렵기에 자주 나오는 유형을 풀어보는 것이 좋습니다. 기본 문제 11047번: 동전 015729번: 방탈출1931번: 회의실배정11000번: 강의실 배정

DP(Dynamic Programming)는 동적계획법이라고도 불리며중복되는 부분문제를 저장하는 기법입니다.문제의 답을 구하는 방법이 점화식을 이용하여 이전의 값들이 반복적으로 쓰이는 문제일 경우기저사례, 점화식을 기반으로 반복적으로 쓰이는 값들을 저장하면서 코드를 작성합니다.푸는 방법은 크게 재귀적 동적 계획법, 반복적 동적 계획법이 있으며재귀적 동적 계획법은 메모이제이션 기법을 사용하여 점화식을 그대로 코드로 옮기기에 직관적이다는 장점,반복적 동적 계획법은 슬라이딩 윈도우라는 기법을 이용하여 공간복잡도를 줄일 수 있다는 장점이 있습니다.DP를 응용한 문제 중 어떠한 방법을 거쳐서 이러한 최적화 답을 구하였는지,조건에 맞는 k번째 답을 계산하고 싶을 경우에도 작성했던 DP의 함수를 조금만 변형하여 구할..

분할정복(Divide and Conquer)은 둘 이상의 부분문제로 나눈 뒤각 부분문제에 대한 답을 재귀 호출로 계산하고, 계산한 답으로 전체 문제의 답을 계산하는 기법입니다.대표적인 예로 거듭제곱을 빠르게 계산하는 법이나 병합정렬(Merge Sort)등이 있습니다.각 부분문제를 합치는 방법이 전부 계산하는 방법보다 빠른 경우 이러한 기법을 사용합니다. 기본 문제 1629번: 곱셈1074번: Z2261번: 가장 가까운 두 점