kimgusxo 님의 블로그

1. DP(Dynamic Programming)이란?- 다이나믹 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하고 그 결과를 중복해서 다시 계산하지 않도록 저장하거나 차례차례 결과를 쌓아올리는 기법이다.- 분할정복과 비슷하지만 하위 문제가 중복되어 등장할 때 중복 계산을 제거하는것이 차이점이다. 1-1. 핵심 아이디어- 중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 등장하면 한 번 계산한 값을 저장해놨다가 재사용- 최적 부분 구조(Optimal Substructure): 문제의 최적 해가 하위 문제의 최적해들로 만들어져야 함 1-2. 장단점- 장점: 중복 계산을 제거하여 시간복잡도가 감소, 단계별 구현 패턴이 일정- 단점: 상태 저장용 메모리(배..

1. 비트마스킹(Bitmasking)이란?- 비트마스킹은 1개의 정수의 비트(0, 1)을 이용해 여러 개의 Boolean 상태(선택/미선택)을 압축해 표현 및 연산하는 기법이다.- 조합/부분 집합 문제, 탐색 및 DP 문제에서 자주 사용된다. 1-1. 핵심 아이디어- mask | (1 - mask & (~(1 - mask ^ (1 - mask & (1 1-2. 비트마스킹 장단점- 장점: int 하나면 N - 단점: 표현 가능한 상태의 수가 정수 비트 수로 제한된다. 1-3. 비트마스킹 자주쓰는 패턴- 부분 집합 열거: for(int mask = 0; mask - 서브마스크 열거: for (sub = mask; sub > 0; sub = (sub-1) & mask)- 상태 압축 DP: dp[mask][p..

1. 분할정복(Divide and Conquer)이란?- 분할정복은 문제를 작은 하위 문제로 분할(Divide)하고 각각을 재귀적으로 해결(Conquer)한 뒤 다시 합쳐(Merge) 전체 문제의 해답을 얻는 알고리즘 기법이다.- 대표적으로 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 큰 수 거듭제곱 문제 등이 있다. 1-1. 핵심 아이디어- 분할(Divide): 해결하고자 하는 문제를 더 이상 분할할 수 없거나 충분히 작아질 때까지 여러 하위 문제로 나눈다.- 정복(Conquer): 분할된 하위 문제를 재귀적으로 해결한다.- 병합(Merge): 각각의 하위 문제에서 구한 해답을 병합하여 원래 문제의 답을 도출한다. 1-2. 장점 및 단점- 장점: 큰 문제를 여러개의 작은 문제로 나..

1. 백트래킹(Backtracking)이란?- 백트래킹은 문제의 가능한 모든 해를 탐색하는 과정에서 조건을 만족하지 않는 경로를 조기에 포기하여 탐색 범위를 줄이는 기법이다.- 그리디나 단순 브루트포스와 달리 백트래킹은 모든 배치를 시도하지만 조건을 위반하는 경우 탐색을 중단하고 되돌아간다. 1-1. 핵심 아이디어- 문제 분할: 문제를 여러 하위 문제로 나눈 후 각 단계에서 선택할 수 있는 후보를 탐색한다.- 가지치기: 현재까지의 선택이 문제의 조건을 만족하는지 검사하고 만족하지 않으면 바로 이전 상태로 돌아가 다른 후보를 탐색한다. 1-2. 백트래킹 장단점- 장점: 문제의 해 공간이 크더라도 불필요한 경로를 빠르게 배제한다, 복잡한 문제도 재귀 호출과 조건 검사를 통해 간결한 코드로 구현 가능하다.- ..

1. 깊이 우선 탐색(DFS)이란?- DFS(Depth-First-Search)는 깊이 우선 탐색 알고리즘으로 그래프나 트리 구조에서 한 경로를 가능한 한 깊게 탐색한 후 더 이상 진행할 수 없으면 이전 단계로 되돌아가 다른 경로를 탐색하는 방식이다.- 시작 노드에서부터 한 방향으로 깊게 탐색하여 방문한 노드의 자식들 중 아직 방문하지 않은 노드를 우선적으로 탐색한다.- 주로 재귀나 스택을 활용하여 구현한다.- O(V+E)의 시간복잡도를 가지며 여기서 V는 정점의 수, E는 간선의 수이다.1-1. 활용 분야경로 탐색: 그래프에서 특정 노드에 도달하는 경로를 찾거나 모든 경로를 탐색할 때연결 요소 찾기: 그래프의 모든 정점을 방문하여 연결된 구성 요소를 찾을 때백트래킹: 퍼즐, 조합 문제 등에서 모든 가..

1. 너비 우선 탐색(BFS)이란?- BFS(Breadth-First-Search) 알고리즘으로 그래프나 트리에서 시작 정점으로부터 인접한 노드들을 먼저 탐색한 후 그 다음 단계(레벨)- 시작 정점 부터 인접한 모든 노드를 방문하고 방문한 인접 노드를 그 다음 순서로 탐색하는 계층적 탐색 기법이다.- 탐색 순서를 관리하기 위해 FIFO(First-In-First-Out) 방식의 큐를 사용하며, 각 단계별로 노드를 처리한다. 1-1. BFS의 장단점장점최단 경로 탐색: 가중치가 동일한 그래프에서 시작 정점으로부터의 최단 경로를 보장한다.레벨 정보 획득: 각 노드가 몇 번째 레벨에 있는지 쉽게 파악 할 수 있다.단점메모리 사용: 큐에 모든 인접 노드가 저장되므로 매우 넓은 그래프에서는 메모리 사용량이 많아질..

1. 그리디(Greedy) 알고리즘이란?- 그리디 알고리즘은 매 단계마다 현재 상황에서 가장 최적인 선택을 하는 알고리즘이다.- 매 단계마다 최선이라고 판단을 하는 지역 최적 선택(Local Optimal Choice)를 반복하여 전역 최적해(Global Optimal Solution)에 도달하려고 한다.- 구현이 단순하며, 문제의 구조를 직관적으로 이해할 수 있다.- 항상 전역 최적해를 보장하지는 않으므로, 문제에 따라서는 그리디 접근이 근사해만 제공할 수 있다. 2. 그리디 알고리즘 구현2-1. 활동 선택 문제- 여러 활동들이 시작 시간과 종료 시간을 가지고 주어질 때, 서로 겹치지 않게 선택할 수 있는 활동의 최대 개수를 구하는 문제이다.public class ActivitySelection { ..

1. 누적합(Prefix Sum)이란?- 배열이나 리스트의 각 원소까지의 합을 미리 계산해두고, 이를 이용하여 임의의 구간 합은 빠르게 구하는 기법이다.- 입력 배열의 앞에서 부터 누적된 합을 저장한 누적합 배열을 만들어서 사용한다.- 여러 구간 합, 평균, 최대/최소 문제 등을 빠른 시간으로 구할 때 사용된다. 2. 누적합 점화식- 누적합 배열 P와 일반 배열 A일때 - P[0] = A[0] - P[i] = P[i-1] + A[i] for i >= 1- 구간 [l, r]의 합은 다음과 같다. - 만약 l = 0이면, 구간 합은 P[r] - 만약 l > 0이면, 구간 합은 P[r] - P[l-1] 3. 누적합 구현- 누적합 배열을 생성하고 두 개의 구간합 쿼리를 해결하는 문제이다.publi..

1. 슬라이딩 윈도우(Sliding Window) & 투 포인터(Two Pointer)란?- 모두 배열이나 문자열 같이 순차적으로 저장된 데이터에서 연속된 구간(윈도우)을 효율적으로 탐색하기 위한 기법이다.- 연속 구간 내 조건데 따라 최대/최소 합, 길이 등을 빠르게 계산할 수 있다. 1-1. 유사점 및 차이점- 유사점: 둘 다 연속된 구간을 탐색하는데 초점을 맞추며, 포인터를 이동시키는 방식으로 중복 계산을 줄인다.- 차이점: 슬라이딩 윈도우는 고정 크기의 윈도우를 가지며 투 포인터는 2개의 인덱스를 통해 동적 윈도우를 가진다. 2. 슬라이딩 윈도우 & 투 포인터 구현2-1. 고정 길이(슬라이딩 윈도우) 구현- 정수 배열이 주어졌을 때 길이가 k인 연속 부분 배열의 합들 중 최대값을 구하는 문제pub..

1. 이분 탐색(Binary Search)이란?- 정렬된 배열에서 원하는 값을 빠르게 찾기 위해 사용하는 기본적인 알고리즘이다.- 정렬된 배열의 중앙값과 비교하면서 찾고자 하는 값이 중앙값보다 작으면 왼쪽 부분 배열, 크면 오른쪽 부분 배열로 범위를 좁혀나간다.- 탐색 범위를 매번 절반으로 줄이므로 O(logN)의 시간복잡도를 가진다.- 정렬이 필수적으로 되어있어야 한다.- 최적의 해, 임계값 알고리즘에 활용된다. 2. 이분 탐색 구현- left와 right, mid 변수로 시작과 끝, 중앙 인덱스를 설정하고 값과 비교하며 범위를 축소한다. public class BinarySearch { // 정렬된 배열에서 target 값을 탐색하여 인덱스를 반환 (찾지 못하면 -1 반환) public s..

1. 브루트포스(Brute Force)란- 문제의 가능한 모든 경우의 수를 하나씩 전부 시도(완전 탐색)하여 정답을 찾는 기법이다.- 최적화된 해법이 존재하지 않거나 문제의 크기가 작아 모든 경우를 탐색해도 충분할 때 사용된다.- 경우의 수가 많아지면 시간복잡도가 기하급수적으로 증가하므로 다른 방식을 찾아야한다.- 재귀 또는 반복을 통해 구현한다. 2. 브루트포스 구현- 주어진 문자열의 모든 부분 문자열을 출력하는 문제2-1. 모든 부분 문자열 구하기(반복)- 이중 반복문을 사용하여 시작 인덱스와 끝 인덱스를 결정하고 그 구간의 부분 문자열을 출력하는 방식이다.public class AllSubstringsIterative { public static void main(String[] args) {..

1. 재귀(Recursion)란- 재귀는 함수가 자기 자신을 호출하는 기법이다.- 문제를 여러개의 하위 문제로 분할하여 하위 문제를 해결한 후 이를 종합하여 전체 문제를 해결하는 방식- DFS, 백트래킹, 트리순회, 피보나치 수열 등의 알고리즘으로 활용된다. 1-1. 핵심 아이디어- 기저 조건(Base Case): 재귀호출이 무한히 반복되지 않고 종료되도록 하는 조건- 재귀 호출(Recursive Call): 함수가 자기 자신을 호출하여 하위 문제를 해결하는 부분 2. 재귀의 장단점- 장점: 문제 분할에 적합하고 반복문보다 간결한 코드로 표현할 수 있다.- 단점: 재귀 호출마다 함수가 스택에 쌓이므로 메모리 사용이 크고 동일한 문제를 여러 번 계산할 경우 성능 저하가 발생한다. 3. 활용 알고리즘3-1...

1. 셋(Set)이란?- 셋은 유일한 요소들을 저장하는 자료구조이다.- 같은 값은 한 번만 저장할 수 있으며 중복되는 데이터를 제거하는 용도로 활용된다.- 기본적으로 저장 순서에 대해 보장하지 않지만 구현체에 따라 삽입 순서나 정렬된 순서를 유지할 수 있다. 2. 해쉬셋(HashSet)- 해시 테이블을 기반으로 하며, 요소의 해시코드를 이용해 저장 위치를 결정한다.- 평균적으로 삽입/삭제/검색이 O(1)의 시간복잡도를 가진다.- 요소가 해시 값에 따라 저장되므로 저장 순서와 조회 순서는 일치하지 않는다.- 동일한 요소는 한번만 저장된다. 2-1. 해쉬셋 주요 메소드- add(E e): 새로운 요소를 해쉬셋에 추가한다.HashSet hashSet = new HashSet();hashSet.add("Appl..

1. 맵(Map)이란?- 키(Key)와 값(Value)의 쌍을 저장하는 자료구조이다, 각각의 키는 유일(Unique)해야하며 키를 통해 대응하는 값을 빠르게 검색, 삽입, 삭제할 수 있다.- 자바에서는 대표적으로 HashMap과 TreeMap을 사용하여 구현한다. 2. 해쉬맵(HashMap)- 해쉬맵은 내부적으로 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 기반으로 데이터를 저장하는 방식이다.- 평균적으로 삽입/삭제/검색이 O(1)의 시간복잡도를 가진다.- 해시 함수를 기반으로 데이터를 저장하기 때문에, 저장 순서와 검색 순서가 일치하지 않는다.- 하나의 null 키와 여러 개의 null 값을 허용한다.- 해시 버킷 배열에 키-값 쌍을 저장하며, 충돌시 체이닝을 사용한다. 2-1. 해쉬맵 주요..

1. 트리(Tree)란?- 트리는 계층적 구조를 갖는 자료구조로 노드(Node)와 간선(Edge)으로 구성되는 비선형 자료구조이다.- 한 노드는 부모(Parent)와 여러 자식(Child) 노드를 가질 수 있으며, 최상위 노드는 루트(Root)라고 부른다.- 트리 순회, 계층적 데이터 표현 알고리즘에 활용된다. 1-1. 주요 용어- 노드(Node): 트리의 기본 구성 요소로 하나의 데이터를 담고있다.- 루트(Root): 트리의 최상위 노드- 자식(Child) 특정 노드 아래에 연결된 노- 리프(Leaf): 자식이 없는 단말 노드- 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리- 깊이(Depth): 루트로부터의 거리 또는 트리의 최대 레벨 2. 트리의 종류- 이진 트리(Binary Tr..

1. 힙(Heap)이란?- 힙은 완전 이진 트리 형태로 구성되는 자료구조로 각 노드가 특정 순서(우선순위)를 만족하도록 구성된다.- 부모 노드의 값이 자식 노드의 값보다 작거나 같아 루트 노드에 최솟값이 있는 최소 힙(Min Heap)과 부모 노드의 값이 자식 노드의 값보다 크거나 같아 루트 노드에 최댓값이 있는 최대 힙(Max Heap)으로 구성된다.- 우선순위 큐의 기본 구현체로 사용되며 삽입과 삭제 연산이 O(logN)의 복잡도를 가지며 힙 정렬과 다익스트라 알고리즘에 활용된다. 2. 자바를 활용한 힙 구현- 배열 기반의 최대 힙을 구현한 예제이다.public class MaxHeap { private int[] heap; public int size; private int capa..