여행경로 (프로그래머스 Level 3 - 43164)1. 문제 설명주어진 항공권 정보 tickets를 바탕으로 "ICN"에서 출발하는 여행 경로를 찾되,모든 항공권을 한 번씩 사용하면서 사전 순으로 가장 앞선 경로를 구해야 한다.항공권 정보는 [출발지, 도착지] 형식경로는 항공권을 모두 사용한 순서대로 나열한 공항명 벡터2. 핵심 아이디어모든 항공권을 순회해야 하므로 DFS 백트래킹 사용사전순으로 가장 앞선 경로를 반환하기 위해 티켓 목록을 정렬경로가 완성되면 그 순간 바로 answer에 저장하고 리턴이미 경로를 찾았다면 더 이상 탐색하지 않도록 !answer.empty() 체크로 조기 탈출3. 코드 설명DFSvoid dfs(vector>& tickets, int depth) { if (depth ..

불 ! (백준 4179번)문제 개요문제 설명:미로에서 지훈이(J)가 불(F)로부터 탈출하는 최소 시간을 구하는 문제미로는 벽(#), 빈 공간(.), 불(F), 지훈이(J)로 구성됨불은 매 초마다 상하좌우 인접한 빈 공간으로 확산매 초마다 상하좌우로 한 칸 이동 가능하며, 벽이나 불이 있는 곳으로 이동 불가미로 밖으로 나가면 탈출 성공탈출이 불가능하면 "IMPOSSIBLE" 출력핵심 포인트:불의 확산과 J의 이동을 시간 단위로 동기화하며 시뮬레이션 해야 함BFS를 이용하여 J의 이동과 불의 확산을 순차적으로 처리접근 방법1. 불 확산과 지훈이 이동을 동시에 처리하는 BFS불의 현재 위치를 set에 저장해 매 시간마다 인접한 빈 공간으로 확산J의 위치를 queue에 저장해 BFS 탐색 진행J의 이동 시간이 ..

드래곤 커브 (백준 15685번)문제 요약격자 위에 여러 드래곤 커브를 그린 뒤, 정사각형 네 꼭짓점이 모두 드래곤 커브에 포함되는 개수를 구하는 문제이다.1. 문제 분석드래곤 커브 정의세대 $g=0$인 드래곤 커브는 시작점 $(x,y)$에서 방향 $d$로 한 칸 이동한 두 점을 잇는 선분이다.세대가 한 번 증가할 때마다, 기존 커브의 “끝점”을 기준으로 90도 시계 회전시킨 복제 선분을 뒤에 이어 붙여 커브를 확장한다.목표주어진 $n$개의 드래곤 커브를 모두 그린 뒤,격자 $(i,j),(i+1,j),(i,j+1),(i+1,j+1)$ 네 점이 모두 드래곤 커브 상에 표시된 칸(점)인 정사각형의 개수를 세어 출력.2. 핵심 아이디어드래곤 커브 생성 (세대별)기본 세대$(g=0)$: 두 점 $(x,y)), ..

파일 합치기 (백준 11066번)문제 개요여러 파일을 하나의 파일로 합칠 때, 두 파일을 합치는 비용은 두 파일의 크기의 합이다.여러 개의 파일을 주어진 순서대로 합칠 때,전체 합치는 비용을 최소화하는 합치는 순서를 찾는 문제이다.접근 방법: 동적 계획법 (DP)문제는 구간 DP 문제의 대표적인 예제로,파일 $ A_i $의 크기를 배열 $ \text{arr}[i] $로 두면,구간 $[i, j]$에 있는 파일들을 합치는 최소 비용 $ dp[i][j] $는 다음 점화식으로 구할 수 있다.1. 누적 합 (Prefix Sum)연속된 파일 크기의 합을 빠르게 계산하기 위해,누적 합 배열 $ \text{subtotal} $을 사용한다.$$\text{subtotal}[k] = \sum_{l=0}^{k-1} \text..

나머지 합 (백준 10986번)문제 개요문제 설명:길이가 $ n $인 수열이 주어지고, 정수 $ m $ 이 주어진다.수열의 연속 부분 수열의 합이 $ m $ 으로 나누어 떨어지는 경우의 수를 구하는 문제다.핵심 포인트:직접 모든 구간의 합을 구하면 시간 복잡도가 $ O(n^2) $ 가 되어 시간 초과 가능성이 높다.누적 합(presum)과 나머지 연산을 활용하면 효율적으로 $ O(n) $ 내에 해결할 수 있다.접근 방법1. 누적 합과 나머지 활용누적 합 정의:$  S_i = \text{v[0]} + \text{v[1]} + \dots + \text{v[i]} $ 그러면 구간 $ [i, j] $ 의 합은 $ S_j - S_{i-1} $ 이다.나머지 이용:구간 합이 $ m $ 으로 나누어 떨어진다는 것은$$..

수열의 합 (백준 1024번)문제 개요문제 설명:주어진 자연수 N 과 최소 길이  L이 있을 때, 연속된 자연수들의 합이  N이 되는 수열을 찾는 문제다.조건:수열의 길이는 최소  L이상이어야 하며, 길이가 100을 초과할 수 없다.수열에 포함된 수는 음수가 될 수 없다.만약 조건을 만족하는 수열을 찾지 못하면 "-1"을 출력한다.접근 방법문제를 효율적으로 해결하기 위해 수학적 접근법을 사용한다.연속된 $\text{len}$개의 자연수의 합을 수식으로 표현하면 다음과 같다.1. 연속된 수열의 합 공식연속된 $\text{len} $개의 정수 $ x, x+1, x+2, \dots, x+\text{len}-1 $의 합은:$$\text{Sum} = \text{len} \times x + \frac{\text{l..

문제: if (백준 15549번)문제 개요문제는 주관식으로, 자바 코드 내에서 아래 조건을 만족하는 변수 x의 타입과 값을 찾는 것이다.if (x != 0 && x == -x) { System.out.println("true");} else { System.out.println("false");}조건 분석조건을 만족하려면,x는 0이 아니어야 한다.x와 -x가 같아야 한다.일반적인 수학에서는 (x = -x)이면 (x)가 0이 되어야 하지만, 여기서는 0이 될 수 없으므로 특별한 상황(오버플로우)를 고려해야 한다.두의 보수와 오버플로우자바의 정수형(int)은 두의 보수(Two's Complement) 방식으로 표현된다.int의 범위: (-2^{31}) ~ (2^{31}-1) 즉, (-2147483..

Fly me to the Alpha Centauri (백준 1011번)문제 개요문제 설명:우주선이 $x$에서 $y$까지 이동할 때, 이동 거리에 따른 일정한 규칙을 따르는 “점프”를 사용한다.문제는 주어진 시작점 $x$와 도착점 $y$ 사이의 거리를 이동하기 위한 최소 점프 횟수를 구하는 것이다.이동 규칙 요약:첫 번째 점프는 무조건 1광년, 그 이후 점프 거리는 이전 점프 거리와 같거나 1 증가/감소할 수 있다.마지막 점프도 무조건 1광년이다.이러한 규칙을 종합하면, 거리를 이동하기 위한 점프 횟수는 일정한 패턴을 따르게 되며,(예: 거리 1→ 1회, 2→ 2회, 3→ 3회, 4→ 3회, 5,6→ 4회, 7,8→ 5회, 9→ 5회, …)접근 방법수학적 아이디어:기존의 정답 공식은 다음과 같다.$n = ..

문제: 찾기 (백준 1786번)문제 개요목표주어진 텍스트 문자열에서 패턴 문자열이 등장하는 모든 위치(인덱스)를 찾아, 등장 횟수와 위치를 출력하는 문제.핵심 포인트단순 문자열 검색(브루트포스)은 O(n×m) 시간 복잡도를 가짐KMP (Knuth-Morris-Pratt) 알고리즘을 사용하여 O(n+m) 시간에 해결1. 패턴 접두사 함수 (KMP 함수)목적패턴 문자열 내부에서 각 인덱스까지의 부분 문자열이 가지는 최대 접두사-접미사 일치 길이를 pi 배열에 저장예시 "ABABC"인덱스부분 문자열접두사-접미사 분석pi[i]0"A"접두사 길이 001"AB""B"와 "A" 다름02"ABA""A" (인덱스 2)와 "A" (인덱스 0) 일치13"ABAB"인덱스 3의 'B'와 인덱스 1의 'B' 일치24"ABABC"..

Prefix and Suffix Search (LeetCode 745)문제 개요문제 설명:주어진 문자열 배열 words에서, 특정 접두사(pref)와 접미사(suff)를 모두 만족하는 단어 중 가장 큰 인덱스를 반환하는 문제이다.문제의 어려움:단순한 선형 검색이나 해시맵 기반 방법으로는 모든 단어에 대해 접두사와 접미사를 확인해야 하므로 비효율적이다.따라서, 빠른 검색을 위해 Trie(트라이) 자료구조를 활용하는 최적화된 방법이 필요하다.접근 방식: Trie를 이용한 최적화핵심 아이디어:한 단어의 모든 가능한 접두사와 접미사 조합을 미리 Trie에 삽입해 놓는다.이를 통해 f(pref, suff) 함수 호출 시, suff + "{" + pref 문자열을 만들어 한 번의 탐색으로 원하는 단어의 인덱스를 찾..