기록하는 습관 "기습"

문제https://www.acmicpc.net/problem/2178 풀이 먼저 코드부터 보자.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Miro { static class Node { int x; int y; int cnt; public Node(int x, int y, int cnt) { this.x = x; this...

https://www.acmicpc.net/problem/9184문제 설명재귀 함수를 사용해 정의된 함수 w(a, b, c) 를 효율적으로 계산하는 문제를 해결한 코드이다.해당 함수는 다음과 같은 규칙을 따른다.기저 조건:만약 a, b, c 중 하나라도 0 이하이면, w(a, b, c) = 1이다.상한 조건:만약 a, b, c 중 하나라도 20보다 크면, w(a, b, c) = w(20, 20, 20)로 계산한다.특수 조건:만약 a 그리고 b 인 경우,w(a, b, c) = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)로 계산한다.일반 조건:위의 조건에 해당하지 않는 경우,w(a, b, c) = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b,..

문제 설명길이가 N인 계단 수의 개수를 구하는 문제이다. 계단 수란, 0으로 시작하지 않으며, 인접한 모든 자리의 차이가 정확히 1인 수를 의미한다. 예를 들어, N=2일 때 가능한 계단 수는 다음과 같다. 길이 2의 계단 수: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 총 개수는 17개이다. 🔹 문제 요구사항N이 주어졌을 때, 길이가 N인 계단 수의 개수를 10^9로 나눈 나머지를 출력해야 한다. 문제 풀이동적 계획법과 재귀를 이용해 해결해야 한다.동적 계획법(DP)과 메모이제이션의 활용DP 테이블의 정의dp[loc][val]dp[loc][val]_은 **길이가 loc이고 마지막 자릿수가 val인 계단 수의 개수_를..

BOJ11054: 바이토닉 수열 - 가장 긴 바이토닉 부분 수열 구하기https://www.acmicpc.net/problem/11054설명1. 문제 개요입력된 수열에서 각 위치를 기준으로: 왼쪽 방향으로 증가하는 부분 수열을 계산한다. 오른쪽 방향으로 증가하는 부분 수열을 계산한다. 두 값을 합하여 가장 긴 바이토닉 부분 수열의 길이를 구한다. 2. 주요 변수와 데이터 구조 static int[] sq, dpr, dpl;sq: 원본 수열을 저장하는 배열. dpl: 각 위치에서 왼쪽 방향으로 증가하는 부분 수열의 길이를 저장하는 배열. dpr: 각 위치에서 오른쪽 방향으로 증가하는 부분 수열의 길이를 저장하는 배열. 3. 코드 동작 원리 1) 입력 처리 및 초기화: BufferedRea..

코드 설명1) 주요 변수와 클래스 선언:import java.io.*;import java.util.*;public class BOJ24511 { static Deque qs; static int n, m;qs: 프로그램의 핵심 데이터 구조인 Deque를 저장하는 변수다.n: 초기 데이터의 개수를 저장하는 변수다.m: 추가 작업에 사용할 데이터 개수를 저장하는 변수다.2) 메인 로직 구현:public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine(..

문제 개요백준 2346번 문제, 풍선 터뜨리기는 큐(Queue)를 활용하여 풍선이 터지는 순서를 출력하는 문제다. 이 문제는 자료구조와 덱(Deque)의 활용 능력을 테스트하는 데 적합하다. 주어진 풍선 번호와 이동 값을 기반으로 풍선이 터지는 순서를 계산하는 것이 핵심이다.코드 분석public class BOJ2346 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); Deque deque = new..

투 포인터투 포인터(Two Pointers) 기법은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 알고리즘 설계 방법이다. 이 기법은 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 부분 배열이나 쌍을 찾는 문제를 풀 때 자주 활용된다.투 포인터는 주로 다음과 같은 상황에서 유용하다:- 두 요소의 합이나 곱과 관련된 조건을 만족하는 쌍을 찾는 경우- 특정 조건을 만족하는 부분 배열의 길이, 개수 등을 구하는 경우- 슬라이딩 윈도우와 함께 사용하여 효율적으로 부분합을 계산하는 경우투 포인터의 동작 원리초기화: 두 개의 포인터를 각각 배열의 시작과 끝에 두거나, 특정 조건에 맞게 시작점을 설정한다.조건 검토 및 이동: 조건에 따라 포인터를 이동시킨다..

분할정복분할 정복은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 뒤 결과를 결합하여 원래 문제의 해를 구하는 알고리즘 설계 기법이다.이 방법은 재귀적 접근을 기반으로 하며, 특정 문제를 풀기 위해 문제를 반복적으로 쪼개어 더 단순한 형태로 만들고 이를 조합하여 해를 도출한다. 이 과정은 아래 세 단계로 구성된다:분할(Divide):원래 문제를 더 작은 부분 문제로 분할한다.일반적으로 이 단계는 입력 데이터를 나누거나, 문제의 범위를 축소하는 과정을 포함한다.정복(Conquer):나뉜 부분 문제를 재귀적으로 해결한다.하위 문제의 크기가 충분히 작아지면(예: 크기가 1인 경우), 직접 해결(기저 사례)한다.결합(Combine):각 부분 문제의 결과를 결합하여 원래 문제의 해를 구한다.결합 과..

누적합누적합(Cumulative Sum)은 배열이나 리스트의 특정 구간 합을 빠르게 계산하기 위해 사용하는 알고리즘 기법이다. 일반적으로 대량의 데이터에서 특정 구간의 합을 반복적으로 구해야 하는 경우, 단순히 반복문을 이용해 매번 합을 계산하는 것은 비효율적일 수 있다. 이때, 누적합 배열을 활용하면 원하는 구간의 합을 상수 시간 내에 구할 수 있다. 누적합의 원리누적합의 기본 원리는 배열의 각 위치까지의 값을 순차적으로 더해 새로운 배열을 생성하는 것이다. 이를 통해 배열의 특정 구간 합을 빠르게 계산할 수 있다. 예를 들어, 배열의 i번째 위치까지의 누적합은 원본 배열의 0번째 인덱스부터 i번째 인덱스까지의 합을 저장하는 형태다.누적합 배열을 S라고 할 때, 원본 배열 A에서 구간 [i, j]의 합..

동적 프로그래밍동적 프로그래밍에 대해서 다시금 공부하고 있다. 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제들로 나누어 해결한 후, 그 결과를 저장하여 재사용함으로써 문제 해결의 효율성을 높이는 기법이다. 이는 주로 하위 문제가 반복해서 나타나는 경우에 사용되며, 각 하위 문제의 결과를 기록(memoization)하거나 테이블 형식으로 정리하여 중복 계산을 방지한다. DP는 최적화 문제에서 자주 사용되며, 두 가지 주요 접근 방식이 있다: 상향식(Bottom-Up)과 하향식(Top-Down). 단순히 말하자면, 동적 프로그래밍은 "이전에 계산한 값을 저장해 두었다가 필요할 때 재사용하는 방법"이다. 이는 중복 계산을 줄이고 문제를 더 빠르게 해결할 수 있..