TEN BILLION

가장 긴 증가하는 부분 수열 (LIS) 문제는 수열에서 오름차순으로 정렬된 가장 긴 부분 수열의 길이를 구하는 대표적인 알고리즘 문제입니다.입력: 10 20 10 30 20 50 출력: 4 (예: 10 → 20 → 30 → 50)이 문제를 해결하는 방법에는 O(N²)의 DP 방식과 O(N log N)의 이분 탐색 방식이 있는데,입력 수가 많아질수록 O(N log N) 방식이 훨씬 효율적입니다. 이 문제의 입력조건은' 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. ' 그래서 O(N²) 방식으로 풀 경우 시간초과 입니다. 그래서 O(N log N) 방식으로 LIS의 길이를 구해야 합니다.전체 코드 (Java)import java.io.BufferedReader;import ..

Java에서 단 하나의 값을 List로 만들어야 할 때, 굳이 ArrayList를 만들고 값을 넣을 필요가 있을까요?이럴 때 사용할 수 있는 간단하고 안전한 방법이 바로 Collections.singletonList()입니다.Collections.singletonList()란?Collections.singletonList()는 요소가 하나뿐인 List를 만드는 메서드입니다.위 코드는 "apple" 하나만 들어 있는 리스트를 만듭니다.왜 써야 하나요?1. 한 줄로 끝나니까 편하다리스트 하나 만들기 위해 new ArrayList() 이런 거 안 써도 됩니다.2. 수정할 수 없어서 실수 방지singletonList()로 만든 리스트는 절대 바뀌지 않습니다. 실수로 데이터를 바꾸는 걸 방지할 수 있어요.3. 단..

문제 설명정수로 이루어진 배열 numbers가 주어집니다.각 원소에 대해 자신보다 뒤에 있는 숫자 중에서 처음으로 자신보다 큰 수를 찾아야 합니다.그런 수가 없다면 -1을 대신 넣습니다.입력 예시int[] numbers = {2, 3, 3, 5};출력 예시[3, 5, 5, -1] 풀이이 문제는 단순히 이중 for문으로 O(N^2) 시간 복잡도로도 풀 수 있지만,최적화가 필요한 경우 스택을 이용한 역순 순회 방식이 효율적입니다.✅ 핵심 전략:배열을 오른쪽 → 왼쪽으로 순회자신보다 큰 수가 나올 때까지 스택 pop조건을 만족하는 수를 만나면 answer에 저장하고 현재 수를 다시 pushJava 코드 (스택)import java.util.*;class Solution { public int[] solu..

문제수열에서 증가하다가 감소하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.이를 위해 각 위치 i를 기준으로i까지의 최장 증가 수열 (LIS) 길이: inc[i]i부터의 최장 감소 수열 (LDS) 길이: dec[i]최종 결과는 inc[i] + dec[i] - 1 중 최댓값입니다. 바이토닉 수열이란?어떤 수열에서 증가하다가 감소하는 수열을 의미합니다.1 3 5 4 2 → 바이토닉1 2 3 4 5 → X (감소 없음)5 4 3 2 1 → X (증가 없음)바이토닉 수열의 최대 길이를 구하는 프로그램을 작성하려고 합니다. 자바 코드 ①: 조건문 방식import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException..

게임 캐릭터를 상하좌우로 움직이면서 **지나간 '서로 다른 길의 수'**를 구하는 문제입니다. 단, 한 번 지나간 길은 다시 지나가도 새로운 길로 취급하지 않습니다.문제 설명초기 위치: (0, 0)명령어:U: 위로 한 칸D: 아래로 한 칸L: 왼쪽으로 한 칸R: 오른쪽으로 한 칸좌표 제한: x, y ∈ [-5, 5]중복 경로: 같은 길은 한 번만 센다 (양방향 포함)풀이Set을 사용해서 중복되지 않는 경로만 저장한다.경로를 "x1,y1,x2,y2" 형식으로 저장하며, 양방향 모두 저장한다.예: (0,0) → (0,1) 와 (0,1) → (0,0)은 같은 경로로 간주경계 밖으로 이동하려는 명령은 무시한다.마지막에 Set 크기를 2로 나눠서 실제 경로 개수를 구한다.JAVAimport java.util.*;..

🧩 문제 설명철수는 동생에게 롤케이크의 절반을 공평하게 나눠주려고 합니다.롤케이크에는 여러 종류의 토핑이 순서대로 놓여 있고,철수는 토핑이 놓인 순서대로 한 조각씩 왼쪽으로 자를 수 있습니다.이때 자신과 동생이 갖게 되는 토핑의 종류 수가 같아지는 경우의 수를 구해야 합니다.❗예시입력: [1, 2, 1, 3, 1, 4, 1, 2]출력: 2 풀이방법전체 토핑 개수를 Map으로 세어둔다.왼쪽부터 한 칸씩 자르면서:왼쪽 토핑 종류는 Set으로 관리하고,오른쪽 토핑 종류는 Map에서 하나씩 감소시키며 관리합니다.양쪽의 토핑 종류 수(Set.size() vs Map.size())가 같으면 answer 증가JAVA 코드import java.util.*;class Solution { public int sol..

공통점둘 다 임계 영역(critical section) 을 보호하여 동시 접근 문제를 방지합니다.하나의 스레드만 임계 영역을 실행할 수 있게 락(Lock)을 사용합니다.Synchronized (Java 키워드)JVM 수준의 모니터 락을 사용합니다.사용법이 간단함:synchronized (object) { // 임계 영역}메서드 단위로도 사용 가능:public synchronized void method() { ... }장점코드가 간결하고 가독성이 높음.락 해제를 자동으로 처리 (예외 발생 시에도 자동 해제).JVM이 최적화를 잘 해줌 (예: biased locking 등).단점공정성(fairness) 조절 불가.타임아웃 또는 인터럽트 불가.세밀한 락 제어 불가 (조건 변수 등 사용 불가).Reent..

Java 17은 2021년 9월에 출시된 LTS(Long-Term Support) 버전으로, 11 이후 4년 만의 장기 지원 버전입니다.JDK 17은 최신 Java 기능들이 안정화되어 현업에서 도입하기에 가장 적합한 버전입니다. JDK 17 항목 내용 출시일2021년 9월 14일LTS 여부LTS (8, 11 이후 17)주요 기능Sealed Classes, Pattern Matching (instanceof), New macOS Rendering, Deprecations 등이전 버전과 비교JDK 11~16에서 실험된 기능들이 안정화된 버전 주요 기능 상세 정리1. Sealed Classes (봉인 클래스)하위 클래스의 상속을 제한하는 기능public sealed class Shape permits Ci..

스프링의 핵심 철학은 IoC(Inversion of Control) 입니다. 이 철학을 구현하는 가장 대표적인 기술이 바로 의존성 주입(Dependency Injection) 입니다. 1. 의존성 주입이란?의존성(Dependency): 객체가 다른 객체를 사용할 때, 이 관계를 ‘의존성’이라고 합니다.주입(Injection): 필요한 의존 객체를 직접 생성하지 않고 외부에서 넣어주는 것입니다.전통적인 방식 (의존 객체를 직접 생성)public class OrderService { private OrderRepository orderRepository = new OrderRepository(); // 직접 생성}DI 적용 방식 (외부에서 주입)public class OrderService { p..

🔍 문제 설명XYZ 마트에서는 일정 금액을 지불하면 10일 동안 회원 자격을 부여하고, 회원에게 매일 하나의 제품을 할인합니다.정현이는 자신이 원하는 상품들을 할인받기 위해 원하는 품목과 수량이 정확히 일치하는 10일 연속 할인 기간에 맞춰 회원 가입을 하려고 합니다. want = ["banana", "apple", "rice", "pork", "pot"]number = [3, 2, 2, 2, 1]discount = ["chicken", "apple", "apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana"]이 경우, 정현이가 원하는..