Rootable의 개발일기

📌 냅색(Knapsack) 문제란 어떤 가치를 가진 물건이 여러 개 있을 때, 특정 조건을 만족하는 조합을 구하는 문제로 작은 문제의 결과로 큰 문제의 결과를 해결하는 다이나믹 프로그래밍의 대표적인 문제 여기서는 물건의 가치를 쪼갤 수 없는 0-1 Knapsack 문제를 설명한다. 📌 점화식 다이나믹 문제를 해결하기 위해서는 먼저 점화식을 세워야 한다. 아래 그림을 보자 빈 상자에 20kg을 담을 수 있다. 해당 무게만큼 담을 때, 담은 공의 가격이 가장 높은 케이스를 찾는 것이다. 즉, 특정 조건 내에서 가장 가치합이 높은 조합을 찾는 것이다. 🔎 타뷸레이션 & 메모이제이션 타뷸레이션 : 작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법 메모이제이션 : 이미 계산된 값을 다시 계산해야 할 때, 이미..

📌 DP(Dynamic Programming, 동적 계획법)이란 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 🔎 풀이 방법 ✔ 타뷸레이션(Tabulation) 작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법 예제: 피보나치 수열 import java.io.IOException; public class Main { static int[] A; public static void main(String[] args) throws IOException { int N = readInt(); A = new int[N + 1]; fibonacci(N); for (int i = 1; i

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도 : O(logN) 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다. 📌 탐색 과정 현재 데이터셋의 중앙값을 선택 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 중앙값 < 타깃 데이터일 때 중앙값 기분으로 오른쪽 데이터셋을 선택 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 응용 문제로 특정 범위를 주고 정렬이 가능한 상태에서 O(logN) 내에서 탐색해야 할 때 사용할 수 있다. Reference:

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 시간 복잡도 : O(N^2) 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것 📌 정렬 과정 현재 index에 있는 데이터 값을 선택 현재 선택한 데이터가 정렬된 데이터 범위에서 삽입될 위치를 탐색 처음 자신보다 작은 값이 나올 때까지(오름차순) 처음 자신보다 큰 값이 나올 때까지(내림차순) 삽입 위치부터 index 위치까지 shift 연산(우측 이동)을 수행 삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산을 수행 마지막 index까지, 즉 선택할 데이터가 없을 때까지 반복 📌 알고리즘 import java.io.IOException; public class Main { public..