jaeiktech

이분탐색으로도 풀 수 있다고 하던데 전 투 포인터로 풀었습니다. package org.problem.투포인터;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// 골드 5 용액// 시간 제한 1초 수는 10만 n(logN)까지 허용public class b2467 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); i..

package org.problem.다익스트라;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;// 골드 3 파티// 문제// N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.// 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.// 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.// ..

package org.problem.벨만포드;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.StringTokenizer;// 골드 3 웜홀public class b1835 { static final int INF = Integer.MAX_VALUE / 2; static class Edge { int from; int to; int time; public Edge(int fr..

package org.problem.플로이드워셜;// 골드 4 플로이드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class b11404 { static final int INF = Integer.MAX_VALUE / 2; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cityTotal ..

package org.example;import java.util.*;/* * 유니온 파인드 (Union-Find) / 분리 집합 (Disjoint Set) - 코딩테스트 필수 알고리즘 * * 【기본 원리】 * - 서로소 집합들을 효율적으로 관리하는 자료구조 * - 두 개의 핵심 연산: Union(합치기), Find(찾기) * - 각 집합을 트리 구조로 표현하고, 루트 노드가 집합의 대표자 역할 * - "같은 그룹에 속하는가?"를 빠르게 판단할 수 있음 * * 【시간복잡도】 * - Find: O(α(n)) - 아커만 함수의 역함수, 거의 상수시간 * - Union: O(α(n)) - Path Compression + Union by Rank 적용시 * - 전체적으로 거의 O(1)에 가까운 성능 (실질적으..

package org.example;import java.util.*;/*=== 백트래킹(Backtracking) 알고리즘 ===【알고리즘 개념】백트래킹은 "모든 가능한 경우의 수를 체계적으로 탐색"하는 알고리즘입니다.하지만 단순한 완전탐색과 달리, "조건에 맞지 않는 경우는 즉시 포기(가지치기)"하여 효율성을 높입니다.★ 핵심 아이디어: "시도 → 검증 → 실패하면 되돌아가기(백트래킹)"【동작 원리】1. 선택: 가능한 선택지 중 하나를 선택2. 검증: 현재까지의 선택이 조건을 만족하는지 확인3. 완성: 목표에 도달했으면 답을 저장/출력4. 백트래킹: 조건을 만족하지 않거나 더 이상 진행할 수 없으면 이전 단계로 되돌아감5. 반복: 모든 가능성을 탐색할 때까지 1-4를 반복★ 왜 "백트래킹"이라고 부를까..

package org.example;import java.util.*;/*=== 다음순열(Next Permutation) 알고리즘 기본 개념 ===- 현재 순열에서 사전순으로 바로 다음에 오는 순열을 찾는 알고리즘- 모든 순열을 생성하지 않고도 순차적으로 다음 순열만 구할 수 있음- 시간복잡도: O(n) - 한 번의 다음순열 계산- 공간복잡도: O(1) - 추가 공간 불필요 (in-place 알고리즘)- 전체 순열 생성시: O(n! * n) - n!개의 순열 각각 O(n)시간=== 선수 지식 ===1. 배열 조작과 인덱스 개념2. 사전순(Lexicographic Order) 이해3. 순열(Permutation)의 기본 개념4. 배열 역순 정렬 알고리즘=== 코딩테스트에서 다음순열이 사용되는 문제 유형 =..

package org.example;import java.util.*;/*=== 그래프 표현 방법들 (Graph Representation) ===【기본 개념】그래프를 메모리에 저장하는 방법에는 크게 3가지가 있음:1. 인접 행렬 (Adjacency Matrix)2. 인접 리스트 (Adjacency List)3. 간선 리스트 (Edge List)【각 방법의 특징】1. 인접 행렬: 2차원 배열로 표현, 정점 간 연결 여부를 O(1)에 확인 가능2. 인접 리스트: ArrayList 배열로 표현, 메모리 효율적이고 인접 정점 탐색 빠름3. 간선 리스트: 간선 정보만 저장, 크루스칼 알고리즘 등에서 주로 사용【시간복잡도 비교】 인접행렬 인접리스트 간선리스트정점 추가 ..

package org.example;import java.util.*;/* * ===== 0-1 BFS 알고리즘 상세 개념 ===== * * 0-1 BFS란? * - 가중치가 0 또는 1로만 이루어진 그래프에서 최단경로를 구하는 특수한 BFS * - 일반 BFS는 모든 간선의 가중치가 동일할 때만 최단경로를 보장 * - 다익스트라는 모든 양의 가중치에서 작동하지만 우선순위 큐로 인해 느림 * - 0-1 BFS는 0, 1 가중치 한정이지만 일반 큐보다 빠른 덱을 사용해 효율적 * * 핵심 아이디어: * 1. 덱(Deque, 양방향 큐)을 사용 * 2. 가중치 0인 간선 → 덱의 앞쪽(front)에 추가 → 다음에 우선 처리 * 3. 가중치 1인 간선 → 덱의 뒤쪽(back)에 추가 → 나중에 처리 * 4...

package org.example;import java.util.*;//DFS 알고리즘 기본 개념//**DFS(Depth-First Search, 깊이 우선 탐색)**는 그래프나 트리를 탐색하는 알고리즘입니다. 한 방향으로 최대한 깊이 들어가다가 더 이상 갈 곳이 없으면 되돌아와서 다른 방향을 탐색합니다. 마치 미로에서 길을 따라 끝까지 가보고, 막다른 길이면 되돌아오는 것과 같습니다.// 시간복잡도: O(V + E) - V는 정점 수, E는 간선 수// 공간복잡도: O(V) - 재귀 호출 스택과 방문 배열에 필요한 공간// 먼저 알아야 할 기본 개념://// 재귀(Recursion): DFS의 핵심 구현 방법// 스택(Stack) 개념: 재귀 호출이 스택과 같은 원리// ..