Rootable의 개발일기

📌 허프만 알고리즘이란? 압축 단위마다 문자의 출현 빈도를 조사하여 빈도가 높은 순서대로 비트 수가 적은 부호를 부여함으로써 데이터를 압축하는 방식 즉, 많이 사용된 문자는 더 적은 비트로 나타내고, 적게 사용된 문자는 더 많은 비트를 사용하여 효율적으로 문자열을 나타내는 방식을 말한다. 🧩 문자 압축 예제 AAAAAABBBBCDD => 'A' 6개, 'B' 4개, 'C' 1개, 'D' 2개 🏃‍♂️ 항 합치기 가장 적은 사용 빈도를 가진 두 항을 묶고 그 합을 적어준다.  이와 같이 한번 더 묶는다.  마지막 남은 A까지 묶어주면 다음과 같은 그림이 나온다.  🏃‍♂️ 비트 부여하기 루트 노드를 기준으로 왼쪽으로 한번 가면 0, 오른쪽으로 가면 1이라고 하겠다. A ➡ 0B ➡ 10C ➡ 110..

📌 냅색(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: