서론C++에서 데이터를 저장할 때는 다양한 방식의 배열들을 사용할 수 있다. C-Style 배열부터 array, vector, list, deque 등 C++에서 제공하는 여러 배열(시퀀스 컨테이너)들은 각각의 특성과 용도에 따라 선택적으로 사용된다. 이번 글에서는 이러한 배열들의 특징과 차이점에 대해 알아보자.C-Style 배열C++을 처음 배울 때 가장 먼저 접하게 되는 배열로, 별도의 STL 없이도 사용할 수 있는 C++의 가장 기본적인 배열 형태이다. Primitive array라고도 불리며, 가장 빠르고 리소스를 적게 사용하는 반면, 제공하는 기능은 매우 제한적이다.배열의 크기를 정해놓고 사용하거나, 동적 할당을 통해 런타임에 크기를 지정할 수도 있다. new를 사용한 동적 할당 시에는 반드시 ..

여행경로 (프로그래머스 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"..