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 ..

문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)을 구하고, 그 수열을 출력하는 문제입니다.예시:입력: 10 20 10 30 20 50출력:길이: 4수열: 10 20 30 50문제 조건수열의 길이 N: 1 ≤ N ≤ 1,000수열의 각 값 A[i]: 1 ≤ A[i] ≤ 1,000출력:가장 긴 증가하는 부분 수열의 길이그 수열 자체접근 방식N이 작기 때문에 O(N²)의 동적 계획법(DP) 방식으로 해결 가능경로 추적을 위해 prev[] 배열을 따로 구성하여 수열까지 복원 가능하게 구현문제 분석1. 배열 정의dp[i]: i번째 원소를 마지막으로 포함하는 LIS의 최대 길이prev[i]: i번째 원소 앞에 어떤 원소가 있었는지 기억..

문제 설명정수로 이루어진 배열 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..

🧩 문제 설명철수는 동생에게 롤케이크의 절반을 공평하게 나눠주려고 합니다.롤케이크에는 여러 종류의 토핑이 순서대로 놓여 있고,철수는 토핑이 놓인 순서대로 한 조각씩 왼쪽으로 자를 수 있습니다.이때 자신과 동생이 갖게 되는 토핑의 종류 수가 같아지는 경우의 수를 구해야 합니다.❗예시입력: [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..

🔍 문제 설명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"]이 경우, 정현이가 원하는..

📌 N-Queen 문제란?N × N 크기의 체스판 위에 서로 공격하지 않도록 N개의 퀸(Queen)을 놓는 방법의 수를 구하는 문제입니다.퀸은 다음 위치에 있을 수 없습니다:같은 행같은 열같은 대각선🧩 문제 접근 방식N-Queen은 완전 탐색으로는 시간 초과가 발생하기 때문에 백트래킹(Backtracking) 을 활용합니다.백트래킹은 말 그대로, 불가능한 지점을 만나면 돌아가서 이전 상태로 되돌아가며 탐색하는 방식입니다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static int N, count; static int[] bo..

문제 설명권투 대회에 참가한 n명의 선수들이 1:1로 경기를 치렀습니다.모든 경기 결과는 모순 없이 주어지지만, 일부 결과가 누락되어 있어 모든 선수의 정확한 순위를 알 수는 없습니다.정확한 순위를 매길 수 있는 선수의 수를 구하라조건 정리선수 수 n: 1 ~ 100경기 결과 수: 1 ~ 4,500results[i] = [A, B] → A가 B를 이김결과는 항상 일관됨 (A가 B를 이기고 B가 C를 이기면 A는 반드시 C를 이김)선수 번호는 1부터 시작핵심1. 그래프 기반 추론이긴 선수: 1진 선수: -1모르는 관계: 02차원 배열(n+1 x n+1)로 승/패 관계를 저장합니다.2. 플로이드-워셜 알고리즘 적용간접적으로 추론 가능한 승패를 계산A가 B를 이기고 B가 C를 이기면 → A는 C를 이긴다3. ..

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 이란?그래프에서 모든 정점 쌍 간의 최단 거리를 구하는 알고리즘입니다.즉, 정점 i에서 정점 j까지 가는 최소 비용을 모두 구합니다.특징 항목 설명 그래프 종류방향 그래프 (음수 간선 허용됨, 단 음의 사이클은 X)시간 복잡도O(N³)입력 형식인접 행렬핵심 개념경유지 k를 거치는 경로가 더 짧은지 확인하여 갱신 동작 방식 (점화식)모든 정점 i, j, k에 대해 다음과 같은 방식으로 최단 거리를 갱신합니다:dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])즉,i → j로 바로 가는 거리와i → k → j로 우회해서 가는 거리 중더 짧은 것을 선택합니다. 다음과 같은 방향 그래프가 있다고 ..

문제 설명프로그래머스의 "가장 먼 노드" 문제는 다음과 같은 내용을 가지고 있습니다.노드 수 n, **간선 정보 edge**가 주어집니다.1번 노드에서 가장 멀리 떨어진 노드의 개수를 구해야 합니다.이때, 거리는 "최단 경로 상의 간선 수"를 의미합니다.접근 방법이 문제는 전형적인 그래프 탐색 문제입니다."최단 거리"를 구하는 문제이므로, BFS (너비 우선 탐색) 을 사용하는 것이 적절합니다.BFS를 사용하는 이유DFS는 경로 탐색에는 적합하지만, 최단 거리 보장이 없습니다.BFS는 시작 노드에서 가까운 노드부터 차례로 탐색하므로, 최단 거리를 보장할 수 있습니다.풀이인접 리스트를 이용해 그래프를 표현합니다.1번 노드에서 BFS를 수행하여 각 노드까지의 최단 거리를 구합니다.distance 배열에서 가..