C++/Algorithm

파일 합치기 (백준 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]}+\cdots +\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 문자열을 만들어 한 번의 탐색으로 원하는 단어의 인덱스를 찾..

문제: 암호 코드 (백준 2011번)문제 분석주어진 숫자 문자열을 알파벳으로 변환하는 경우의 수를 찾는 문제.'1' ~ '26'까지의 숫자는 각각 'A' ~ 'Z'로 변환 가능.'0'은 단독으로 존재할 수 없으며, 반드시 앞 숫자와 조합되어야 한다.풀이: 동적 계획법 (DP)1. DP 배열 정의dp[i] = 주어진 숫자에서 i번째 숫자까지 해석할 수 있는 방법의 수핵심은 한 자리, 두 자리씩 해석하는 경우를 고려하는 것이다.2. 점화식1자리 숫자로 해석 가능한 경우 (num[i-1] ≠ '0')→ dp[i] += dp[i-1]2자리 숫자로 해석 가능한 경우 (10 ≤ 두 자리 숫자 ≤ 26)→ dp[i] += dp[i-2]MOD 연산 적용: dp[i] %= 1000000문제에서 요구하는 값이 매우 클 수..

문제: 가장 큰 정사각형 (백준 1915번)문제 분석주어진 $(N\times M)$ 크기의 이진 행렬(0과 1로 구성된)에서,1로만 이루어진 정사각형 영역 중 가장 큰 정사각형의 넓이를 구하는 문제이다.즉, 행렬에서 연속된 1들로 구성된 정사각형의 최대 넓이를 구하면 된다.해결 방법: 동적 계획법 (DP)문제를 효율적으로 풀기 위해 동적 계획법(DP)을 사용할 수 있다.여기서 핵심 아이디어는,dp[i][j]를 (i, j)를 우측 하단 모서리로 하는 가장 큰 정사각형의 한 변의 길이로 정의하는 것이다.설명:(i, j) 위치에서 정사각형을 확장하기 위해서는 바로 위, 왼쪽, 그리고 대각선 왼쪽 위의 위치에 있는 정사각형 크기가 모두 일정 이상이어야 한다.이 세 방향 중 가장 작은 값에 1을 더하면 (i, ..

문제: 좋다 (백준 1253번)문제 분석이 문제는 주어진 수열에서 "좋은 수"의 개수를 찾는 문제이다.정의:수열의 한 원소가 다른 두 원소의 합으로 표현될 수 있다면, 그 원소를 "좋은 수"라고 한다.제한:한 원소는 자기 자신을 이용할 수 없다.같은 원소의 인덱스가 겹치면 안 된다.문제의 핵심은 모든 가능한 두 원소의 합을 고려해, 해당 합이 수열 내의 다른 원소와 일치하는지 확인하는 것이다.해결 방법자료구조 준비:벡터 v: 입력받은 수들을 저장.딕셔너리 dict: 각 숫자에 대해 (인덱스, 상태)를 저장하는 unordered_map 사용.키: 해당 숫자값: 해당 숫자가 등장하는 인덱스와, 아직 "좋은 수" 후보로 남아있는지를 나타내는 불리언 값→ true: 아직 후보→ false: 이미 한 번 사용하여..