DP두번 이상 반복 계산되는 부분 문제들의 답을 미리 저장(메모이제이션)해 한번만 계산 되도록 함으로써 속도의 향상을 꾀하는 방식의 알고리즘 패러다임 이항 계수를 계산하는 함수 bino(n,r)를 완전 탐색 방식으로 작성하면 아래와 같이 중복되는 부분 문제가 발생한다. 이때 DP를 적용하면 부분 문제를 중복 계산하지 않아 성능을 높일 수 있다. 중복되는 부분 문제가 많을수록 성능은 더욱 높아진다.[동작 방식]주어진 문제를 완전 탐색을 이용해 해결한다.중복된 부분 문제를 한번만 계산하도록 메모이제이션을 적용한다.최적화 문제와 DP최적화 문제란 문제의 답이 하나가 아닌 여러개 이고 그 중 어떤 기준에 따라 가장 좋은 답을 찾아 내는 문제를 말한다. 예를 들어 n개의 사과 중에서 r개를 골라 무게의 합을 최대..
Brute Force (완전 탐색)문제의 해가 될 수 있는 모든 경우의 수를 탐색하는 방식문제를 푸는데 있어, 그 문제의 해가 될 수 있는 모든 경우의 수를 파악하는건 매우 중요하다. 필자는 문제를 풀 때 먼저 완전 탐색으로 풀 수 있는지 확인하고, 모든 경우의 수를 머릿속으로 생각하는 편이다. 만약 완전 탐색으로 시간 내에 풀지 못하면 문제의 조건에 따라서 DP, 그리디, 이진 탐색, 적절한 자료 구조를 사용해 최적화한다. 완전 탐색 시 재귀 호출을 사용하면 모든 경우의 수를 만드는 코드(순열, 조합··)를 쉽게 작성할 수 있기에 매우 유용하다. 경우의 수는 문제의 해 후보이며, 문제에 따라 다양한 상태를 가진다. (경로 문제의 경우 경로라는 상태를, 4x4 슬라이딩 퍼즐게임인 경우 퍼즐 맵을 상태로 ..
순열 Brute Force시 경우의 수가 순열 또는 조합 형태로 나타날 수 있다. 아래는 N개의 수(1~N)에서 M개의 순열을 출력하는 코드이다. import java.util.*; import java.io.*; public class Main { static int N, M; static boolean[] select; static LinkedList numbers = new LinkedList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringToken..
Binary Search 리스트의 탐색 범위를 반씩 줄여나가면서 타겟의 위치를 찾는 알고리즘. 탐색 시 O(log n) 성능을 보인다. 리스트가 먼저 정렬되어 있어야만 binary seach 알고리즘을 적용할 수 있으며 분할 정복 기법을 사용한다. 리스트에서 타겟의 인덱스를 빠르게 찾거나 해가 존재할 범위에서 해를 빠르게 찾는데 사용된다. Java의 binary search 자바의 Arrays, Collections 클래스는 binarySearch 정적 메서드를 제공한다. binarySearch 메서드의 리턴 값은 아래와 같다. 리스트에서 키를 찾았으면 키 인덱스 리턴 리스트에서 키를 찾지못하면 키가 삽입되어야할 인덱스 값인 insertion point 값을 구한 뒤 -(insertion point + ..
투포인터, 슬라이딩 윈도우 리스트 완전 탐색 시 성능이 좋지 않을 때 적용할만한 알고리즘이다. 투포인터 : 리스트에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 방식의 알고리즘. O(n)의 성능을 낸다. 슬라이딩 윈도우 : 고정 크기의 윈도우가 이동하면서 원하는 결과를 얻는 방식의 알고리즘. 처음 윈도우만 계산한 뒤 윈도우를 이동시킨다. 이동시킬때 이전 윈도우의 값을 조작한다. O(n)의 성능을 낸다. 투포인터 투포인터 관련 문제이다. https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, ..
재귀 함수 재귀(Recursion)란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말하며 재귀 함수란 함수 안에서 자기 자신을 호출하는 함수를 말한다. 재귀 함수는 짧은 코드로 재귀적인 작업을 수행하는 강력한 함수이지만 그 이해가 쉽지 않다. 이 글에서는 재귀 함수를 잘 쓰기 위해 3단계로 작성하는 법을 소개한다. 재귀 함수 4단계 작성법 재귀 함수를 꼭 써야하나? 재귀 함수로 풀수 있는 문제는 대부분 반복문으로도 풀 수 있다. 반복문이 재귀 함수보다 성능이 좋기 때문에 반복문으로 구현하는 것이 좋다. 따라서 재귀를 쓰기 전에 반복문으로도 풀 수 있는지 고민해보자. 1. (가장 중요) 재귀 함수를 작성하기 전에 재귀 함수가 어떤 일을 하고, 어떤 함수인지 명확히 정의한다. 이를 통해 아래 단계를 쉽..
