새발블로그

1. 투 포인터(Two Pointers)란?정렬된 배열이나 리스트에서 두 개의 인덱스를 사용해 탐색 범위를 조절하는 기법목적: 모든 경우를 다 보지 않고(완전탐색), 필요 없는 탐색을 건너뛰어 시간 절약기본 구조: left와 right 두 개의 인덱스를 조건에 맞게 이동시키며 범위 탐색핵심 아이디어정렬 필요: 대부분 정렬된 상태에서 사용 (정렬 O(n log n))포인터 이동은 단조롭게 → 뒤로 돌아가지 않음 (O(n) 탐색)합/곱/조건을 만족하면 결과를 저장하고 범위를 조절2. 투 포인터 기본 패턴(1) 양 끝에서 시작int left = 0, right = arr.length - 1;while (left target) right--; else left++;}예시: 두 용액(백준 2470), 수 ..

1. 개념그리디 알고리즘은 매 순간 가장 좋아 보이는 선택(국소 최적) 을 해서 전체 문제의 최적해(전역 최적) 를 구하는 방식즉, "당장 눈앞에서 가장 이득인 선택" 을 반복장점: 구현이 간단하고 빠름 (O(n) ~ O(n log n) 수준)단점: 항상 정답을 보장하지 않음 → 문제에서 그리디가 유효한 조건이 있는지 확인 필수2. 그리디가 유효한 조건탐욕 선택 속성 (Greedy Choice Property)현재 선택이 이후의 선택에 영향을 주지 않고, 최적해의 일부가 될 수 있어야 함.최적 부분 구조 (Optimal Substructure)문제를 작은 부분 문제로 나눠도 그 해답이 전체 최적해의 일부여야 함.즉, 부분에서의 최적이 전체에서도 최적이어야 한다는 것!예: 거스름돈 문제(500·100·50..

1. 다익스트라 알고리즘이란?다익스트라 알고리즘은 가중치가 있는 그래프에서 하나의 시작점 → 모든 노드까지의 최단 거리를 구하는 알고리즘(특정 도착점 하나만 필요해도 같은 원리를 적용)특징음수 가중치가 없는 그래프에서만 사용 가능BFS + 우선순위 큐(Heap) 개념이 결합된 형태시간 복잡도: O(E log V) (E = 간선 수, V = 노드 수)2. 동작 원리모든 노드의 거리를 무한대(∞) 로 초기화, 시작 노드는 0으로 설정아직 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택해당 노드와 연결된 다른 노드의 거리를 더 작은 값으로 갱신2~3 과정을 모든 노드가 처리될 때까지 반복3. 간단 예시예를 들어 A → H까지의 최단 거리를 구한다고 하면 다음과 같은 순서로 진행된다.시작점 A의 거리를 0..

1. 우선순위 큐란?일반 큐(Queue)는 FIFO(First-In, First-Out) 구조로 먼저 들어온 데이터가 먼저 나온다.반면 우선순위 큐(Priority Queue) 는 우선순위가 높은 데이터부터 꺼내는 자료구조이다.예를 들어, 정수 데이터를 넣었을 때 작은 수가 우선되도록 설정하면, 입력 순서와 상관없이 가장 작은 수부터 꺼낼 수 있다.2. 자바에서 PriorityQueue 사용Java에서는 PriorityQueue 클래스를 사용해 쉽게 우선순위 큐를 구현할 수 있다.Queue pq = new PriorityQueue();pq.add(3);pq.add(1);pq.add(8);while (!pq.isEmpty()) { System.out.println(pq.remove());}결과138→..

1. 다이나믹 프로그래밍이란?다이나믹 프로그래밍(DP)은 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 저장(memoization 또는 tabulation) 하여 중복 계산을 줄이는 최적화 기법중복 계산 방지 → 한 번 계산한 결과를 저장하여 재사용점화식(Recurrence Relation) → 작은 문제의 해를 조합해 큰 문제의 해를 표현최적 부분 구조(Optimal Substructure) → 작은 문제의 최적해가 큰 문제의 최적해 구성에 기여2. DP를 적용할 수 있는 조건중복 하위 문제(Overlapping Subproblems)동일한 계산을 여러 번 수행해야 하는 경우최적 부분 구조(Optimal Substructure)작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있어야 함3...

순열 permutationn, r이 주어졌을 때import java.util.*;public class PermutationGenerator { public static List> permute(int n, int r) { List> ans = new ArrayList(); boolean[] visited = new boolean[n + 1]; // 1부터 n까지 숫자를 사용하기 위해 크기를 n+1로 설정 backtrack(n, r, new ArrayList(), visited, ans); return ans; } private static void backtrack(int n, int r, List curr, boolean[] visi..

1. backtrackingvoid backtrack(List path) { if (isFinished(path)) { // 종료 조건 만족 answers.add(new ArrayList(path)); // 현재 경로 저장 return; } for (int choice : getChoices(path)) { // 가능한 모든 선택 path.add(choice); // 현재 선택 추가 backtrack(path); // 다음 단계 탐색 path.remove(path.size() - 1); // 원래 상태로 되돌리기 (Backtracking) }}2. backtracking + pruningvoid backtra..

순열(Permutation)1. 정의순열은 주어진 n개의 원소 중 r개를 선택해 순서를 고려하여 나열하는 것을 의미같은 원소 집합이라도 순서가 다르면 다른 경우로 취급된다.2. 수학적 표현P(n,r)=n!(n−r)!n! : n개의 원소를 전부 나열하는 경우의 수(n-r)! : 선택하지 않은 원소들의 순서를 제거하기 위한 나눗셈즉, 첫 번째 원소를 n가지 중에서 선택하고, 두 번째를 n-1가지 중에서 선택하는 과정을 r번 반복하는 방식3. 예시n = 4, r = 2일 때:P(4,2)=4!(4−2)!=242=12P(4,2)=\frac{4!}{(4-2)!}=\frac{24}{2}=12가능한 순열:[1, 2], [1, 3], [1, 4],[2, 1], [2, 3], [2, 4],[3, 1], [3, 2], [3..