Computer Science/Algorithm13 [Algorithm/Kotlin] 백준 30804번 과일 탕후루: 투 포인터(슬라이딩 윈도우)로 최적화 문제 설명은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.과일의 종류는 1부터 9까지 있으며, 막대에는 앞쪽부터 차례대로 S1,S2,...,SN번 과일이 꽂혀 있습니다.그러나 주문을 다시 확인해 보니 과일을 두 종류 이하로 사용해야 한다는 요청이 있었습니다.새로 만들 시간이 없는 은하는 앞쪽에서 a개, 뒤쪽에서 b개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.즉, 막대의 연속된 구간 중에서 과일 종류가 2개 이하인 가장 긴 부분을 찾아야 합니다.이때, 남아 있는 과일 개수가 가장 많은 경우를 구하는 것이 목표입니다.입력첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200,000)둘째 줄에 탕후루에 꽂힌 과일을 나타내는 NNN개의 정수 S1,S2,...,SN이 공백으로 .. 2025. 3. 17. [Algorithm/Kotlin] 백준 2630번 색종이 만들기: 분할정복을 활용한 풀이법 1. 문제 설명주어진 N × N 크기의 색종이가 하얀색(0)과 파란색(1) 으로 칠해져 있을 때,이를 모두 같은 색이 될 때까지 잘라 각 색상의 개수를 구하는 문제입니다.문제 조건N은 2^k (k = 1~7) 형태로 주어집니다. (즉, 2, 4, 8, 16, 32, 64, 128 중 하나)색종이가 한 가지 색으로만 칠해져 있다면, 더 이상 자르지 않고 해당 색종이 개수를 증가시킵니다.혼합된 색상이 있다면, 정사각형을 4등분하여 동일한 방식으로 재귀적으로 처리합니다.예제 입력81 1 0 0 0 0 1 11 1 0 0 0 0 1 10 0 0 0 1 1 0 00 0 0 0 1 1 0 01 0 0 0 1 1 1 10 1 0 0 1 1 1 10 0 1 1 1 1 1 10 0 1 1 1 1 1 1예제 출력97 즉,.. 2025. 3. 4. [Algorithm/Kotlin] 백준 1260번 DFS와 BFS: 탐색 알고리즘 구현 및 원리 1. 문제 설명주어진 그래프에서 DFS와 BFS 탐색을 수행한 결과를 출력하는 문제입니다.방문할 수 있는 정점이 여러 개인 경우, 번호가 작은 정점부터 우선 방문해야 합니다.입력첫 번째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점 V가 주어집니다.이후 M개의 줄에는 양방향 간선이 연결하는 두 정점의 번호가 주어집니다.출력첫 번째 줄: DFS 탐색 결과두 번째 줄: BFS 탐색 결과정점 방문 순서대로 출력합니다.2. 문제 해결 아이디어DFS (Depth-First Search, 깊이 우선 탐색)스택(Stack) 또는 재귀(Recursion)를 이용해 탐색을 수행합니다.현재 정점에서 가능한 한 깊이 들어가며 방문한 후, 더 이상 갈 곳이.. 2025. 2. 27. [Algorithm/Kotlin] 백준 17626번 Four Squares: DP를 활용한 풀이법 문제 설명1770년, 라그랑주는 모든 자연수는 네 개 혹은 그 이하의 제곱수 합으로 표현할 수 있다는 사실을 증명했습니다. 목표:주어진 자연수 n을 최소 개수의 제곱수 합으로 표현하세요.입력:자연수 n (1 ≤ n ≤ 50,000)출력:n을 표현할 수 있는 제곱수의 최소 개수문제 해결 아이디어 1. 접근 방법처음에는 가장 큰 제곱수를 빼주면 되지 않을까? 하는 생각으로 그리디(Greedy) 접근법을 떠올렸습니다.예: n = 12인 경우가장 큰 제곱수인 9 (3²)를 선택12 - 9 = 3 → 나머지 3을 다시 제곱수 합으로 표현: 1² + 1² + 1²결과: 12 = 9 + 1 + 1 + 1 → 4개 사용하지만, 더 나은 해가 존재합니다:12 = 4 + 4 + 4 (2² + 2² + 2²) → 3개1: .. 2025. 2. 20. [Algorithm/Kotlin] 백준 11659번 구간 합 구하기 4: 누적 합(Prefix Sum)을 활용한 풀이법 문제 설명주어진 수열에서 특정 구간 [i, j]의 합을 여러 번 구해야 하는 문제입니다. 입력으로 N개의 수와 M개의 구간이 주어집니다. 각 구간에 대해 빠르게 합을 구하는 프로그램을 작성해야 합니다. 제한 사항1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N각 숫자는 1,000 이하의 자연수문제 해결 아이디어기본 접근법 (O(N × M), 시간 초과 가능) M개의 구간 합을 구하기 위해 for 루프를 사용해 N개의 값을 더하면 O(N × M) 시간이 걸립니다. N, M이 최대 100,000일 경우 10^10 이상의 연산이 발생하여 비효율적입니다.누적 합(Prefix Sum) 기법 (O(N + M), 효율적) 먼저 누적 합 배열을 생성하여 O(N) 시간에 각 위치까.. 2025. 2. 19. [Algorithm/Kotlin] 백준 1003번 피보나치 함수: DP를 활용한 풀이법 문제 설명주어진 문제는 재귀적으로 정의된 피보나치 함수에서 0과 1이 출력되는 횟수를 구하는 것입니다.C++의 재귀 구현을 보면, fibonacci(n)을 호출할 때 fibonacci(n-1)과 fibonacci(n-2)를 호출하는 방식으로 동작합니다. 이 과정에서 동일한 fibonacci 함수가 여러 번 호출되며 중복 계산이 발생합니다.예를 들어, fibonacci(3)을 호출하면 아래와 같은 과정이 발생합니다:fibonacci(3) -> fibonacci(2) + fibonacci(1)을 호출합니다.fibonacci(2) -> fibonacci(1) + fibonacci(0)을 호출합니다.fibonacci(1)이 1을 출력하고 반환합니다.fibonacci(0)이 0을 출력하고 반환합니다.fibonac.. 2025. 2. 7. [Algorithm/Kotlin] 백준 11723번 집합: 집합 연산 최적화 MutableSet vs. 비트마스크(Bitmask) 이번 글에서는 MutableSet과 비트마스크(Bitmask) 두 가지 방식을 비교하며, 새롭게 알게 된 비트마스크를 활용한 집합 연산 최적화 방법을 정리해보겠습니다.1. 문제 설명비어있는 공집합 S가 주어졌을 때, 다음 연산을 수행하는 프로그램을 작성하세요.add x : S에 x를 추가 (1 ≤ x ≤ 20)remove x : S에서 x를 제거check x : S에 x가 있으면 1, 없으면 0 출력toggle x : S에 x가 있으면 제거, 없으면 추가all : S를 {1, 2, ..., 20}으로 변경empty : S를 공집합 {}으로 변경입력M (1 ≤ M ≤ 3,000,000): 연산 개수이후 M개의 연산이 주어짐출력check 연산이 수행될 때마다 결과를 출력2. 문제 해결 아이디어이 문제를 해결.. 2025. 2. 3. [Algorithm/Kotlin] 에라토스테네스의 체(Sieve of Eratosthenes) 쉽게 이해하기 에라토스테네스의 체는 특정 범위에서 소수를 빠르고 효율적으로 구하는 방법입니다.작은 소수의 배수를 제거함으로써 소수만 남기는 아이디어를 기반으로 합니다.이 글에서는 코드와 함께 이해한 내용을 정리 해 두도록 하겠습니다.에라토스테네스의 체의 핵심 동작1. i의 범위 제한: i in 2..Math.sqrt(limit.toDouble()).toInt()이 범위는 왜 필요한가?소수의 배수 제거는 대칭적으로 이루어집니다.예: 16의 약수는 (2,8),(4,4)처럼 대칭적으로 나타납니다.따라서 sqrt(limit)까지만 확인하면 충분합니다.sqrt(16) = 4이므로 i=2,3,4까지만 반복하면 됩니다.코드 예제val limit = 16for (i in 2..Math.sqrt(limit.toDouble()).to.. 2025. 1. 20. [Algorithm/Kotlin] 백준 10816번 숫자 카드 2: 시간 복잡도를 계산해 시간초과 해결하기 이 문제를 풀때, 처음에는 단순히 이중 반복문을 떠올려 문제를 해결했지만 입력 크기를 고려하지 못해 시간 초과 실패를 경험했습니다. 이 경험을 토대로, 단순히 문제를 푸는 것에 그치지 않고 시간 복잡도를 계산하고 효율적인 알고리즘을 설계하는 것이 얼마나 중요한지를 배웠습니다.이후 시간 복잡도를 다시 계산하고, 효율적인 방법(groupingBy)을 도입해 문제를 해결할 수 있었습니다.각각의 문제 풀이법과 시간 복잡도 계산 내용을 정리해 두고자 합니다.문제 설명숫자 카드는 정수 하나가 적혀 있는 카드입니다. 상근이는 숫자 카드 N개를 가지고 있으며, 정수 M개가 주어졌을 때, 이 수가 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성해야 합니다.입력 조건첫째 줄: 상근이가 가지고 있는 숫자 카드의 개수 .. 2025. 1. 16. 이전 1 2 다음 반응형
