티스토리

Rootable의 개발일기

검색하기

블로그 홈

Rootable의 개발일기

dev-rootable.tistory.com/m

dev-rootable 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

허프만(Huffman) 알고리즘 📌 허프만 알고리즘이란? 압축 단위마다 문자의 출현 빈도를 조사하여 빈도가 높은 순서대로 비트 수가 적은 부호를 부여함으로써 데이터를 압축하는 방식 즉, 많이 사용된 문자는 더 적은 비트로 나타내고, 적게 사용된 문자는 더 많은 비트를 사용하여 효율적으로 문자열을 나타내는 방식을 말한다. 🧩 문자 압축 예제 AAAAAABBBBCDD => 'A' 6개, 'B' 4개, 'C' 1개, 'D' 2개 🏃‍♂️ 항 합치기 가장 적은 사용 빈도를 가진 두 항을 묶고 그 합을 적어준다. 이와 같이 한번 더 묶는다. 마지막 남은 A까지 묶어주면 다음과 같은 그림이 나온다. 🏃‍♂️ 비트 부여하기 루트 노드를 기준으로 왼쪽으로 한번 가면 0, 오른쪽으로 가면 1이라고 하겠다. A ➡ 0B ➡ 10C ➡ 110.. 공감수 0 댓글수 0 2024. 5. 29.
냅색(Knapsack) 알고리즘 📌 냅색(Knapsack) 문제란 어떤 가치를 가진 물건이 여러 개 있을 때, 특정 조건을 만족하는 조합을 구하는 문제로 작은 문제의 결과로 큰 문제의 결과를 해결하는 다이나믹 프로그래밍의 대표적인 문제 여기서는 물건의 가치를 쪼갤 수 없는 0-1 Knapsack 문제를 설명한다. 📌 점화식 다이나믹 문제를 해결하기 위해서는 먼저 점화식을 세워야 한다. 아래 그림을 보자 빈 상자에 20kg을 담을 수 있다. 해당 무게만큼 담을 때, 담은 공의 가격이 가장 높은 케이스를 찾는 것이다. 즉, 특정 조건 내에서 가장 가치합이 높은 조합을 찾는 것이다. 🔎 타뷸레이션 & 메모이제이션 타뷸레이션 : 작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법 메모이제이션 : 이미 계산된 값을 다시 계산해야 할 때, 이미.. 공감수 0 댓글수 0 2023. 11. 17.
메모이제이션과 타뷸레이션 📌 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 공감수 0 댓글수 0 2023. 10. 30.
이진 탐색(Binary Search) 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도 : O(logN) 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다. 📌 탐색 과정 현재 데이터셋의 중앙값을 선택 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 중앙값 < 타깃 데이터일 때 중앙값 기분으로 오른쪽 데이터셋을 선택 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 응용 문제로 특정 범위를 주고 정렬이 가능한 상태에서 O(logN) 내에서 탐색해야 할 때 사용할 수 있다. Reference: 공감수 0 댓글수 0 2023. 10. 29.
삽입 정렬(Insertion Sort) 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 시간 복잡도 : O(N^2) 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것 📌 정렬 과정 현재 index에 있는 데이터 값을 선택 현재 선택한 데이터가 정렬된 데이터 범위에서 삽입될 위치를 탐색 처음 자신보다 작은 값이 나올 때까지(오름차순) 처음 자신보다 큰 값이 나올 때까지(내림차순) 삽입 위치부터 index 위치까지 shift 연산(우측 이동)을 수행 삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산을 수행 마지막 index까지, 즉 선택할 데이터가 없을 때까지 반복 📌 알고리즘 import java.io.IOException; public class Main { public.. 공감수 0 댓글수 0 2023. 10. 26.
버블 정렬(Bubble Sort) 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 시간 복잡도: O(N^2) 📌 정렬 과정 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산 루프 범위가 끝날 때마다 2~3 반복 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외 비교 대상이 없을 때까지 1~5 반복 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 됨 📌 알고리즘 public class BubbleSort { public static void main(String[] args) throws IOException { BufferedWriter bw = new.. 공감수 0 댓글수 1 2023. 10. 26.
선택 정렬(Selection Sort) 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 시간 복잡도: O(N^2) 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것 📌 정렬 과정 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복 (반드시 N^2만큼 수행하므로 시간 복잡도를 줄이기 힘들다) 📌 알고리즘 public class SelectionSort { public static void main(String[] args) throws.. 공감수 0 댓글수 0 2023. 10. 26.
최소 신장 트리(Minimum Spanning Tree) 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 📌 특징 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다. 최소 신장 트리를 만드는 알고리즘으로 크루스칼과 프림이 있다. 📌 크루스칼(Kruskal) 알고리즘 최소 신장 트리를 만드는 알고리즘(Union-Find 이용) 🔎 에지 리스트(Edge List) 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. 클래스는 일반적으로 출발, 도착 노드와 가중치 변수로 구성된다. class Edge { int start; int end; int weight; public E.. 공감수 0 댓글수 0 2023. 10. 6.
유니온 파인드(union-find) 알고리즘 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘 📌 union, find 연산 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b) == A U Bfind 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환 📌 원리 🔎 1차원 배열 1차원 배열을 통해 초기 배열을 생성한다. 초기 배열은 인덱스가 곧 값이 되며, 이는 각 노드가 속한 집합이 없어 자신이 대표 노드가 된 상태인 것이다. 🔎 union 연산 2개의 노.. 공감수 0 댓글수 0 2023. 10. 5.
다익스트라(Dijkstra) 알고리즘 사이클 없는 양수 가중치 그래프에서 최단 거리를 구하는 알고리즘 시간 복잡도 : O(ElogV) (V : 노드 수, E : 에지 수) 📌 핵심 이론 🔎 인접 리스트 다익스트라 알고리즘은 인접 행렬보다 시각 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트로 구현하는 것이 좋다. 🔎 최단 거리 배열 초기화 최단 거리 값을 저장하기 위한 배열을 만든다. 출발 노드는 0, 나머지 노드는 매우 큰 값으로 초기화한다. 🔎 값이 가장 작은 노드 고르기 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 따라서, 출발 노드에서 시작하면 된다. 🔎 최단 거리 배열 업데이트 인접 리스트와 최단 거리 배열 값을 비교하여 둘 중 작은 값으로 최단 거리 배열을 갱신한다. Min(출발 노드의 최단 거리 배열의 값 +.. 공감수 0 댓글수 0 2023. 10. 4.
플로이드-워셜(Floyd-warshall) 알고리즘 📌 정의 시작점을 지정하지 않고 그래프에서 모든 노드와 관련된 최단 거리를 구하는 알고리즘 📌 주요 특징 기능 특징 시간 복잡도(노드 수: V) 모든 노드 간에 최단 경로 탐색 - 음수 가중치 Edge가 있어도 수행 가능 - 동적 계획법의 원리를 이용해 알고리즘에 접근 O(V^3) 📌 핵심 이론 최단 경로를 구했다고 가정했을 때, 그것을 이루는 부분 경로 역시 최단 경로이다. 예를 들어, A에서 B까지 최단 경로를 구했다고 가정한다. 이때, 해당 경로 위에 K 노드가 존재한다면 A에서 K 노드를 거쳐 B에 도착하는 경로 역시 최단 경로라는 것이다. 따라서 점화식은 다음과 같이 도출된다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 📌 접근 방법 🔎 초기 배열 D[S.. 공감수 0 댓글수 0 2023. 9. 30.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.