자라자

📍 문제 탐색하기동근이는 직사각형 모양의 블록 경계를 따라 상점의 위치로 이동해야 한다. 블록 중간을 가로질러 갈 수 없기 때문에, 블록의 가장자리를 따라 시계 방향 또는 반시계 방향으로만 이동해야 한다.주어진 상점들과 동근이의 위치를 기준으로, 최단 거리의 합을 계산하는 것이 목표이다.문제 조건 분석입력 조건첫째 줄: 블록의 가로 길이 w와 세로 길이 h둘째 줄: 상점의 개수 n이후 n개의 줄: 상점의 위치 (방향, 거리)마지막 줄: 동근이의 위치 (방향, 거리)방향 정보 (1~4)1: 블록의 북쪽 (북쪽 기준 왼쪽에서의 거리)2: 블록의 남쪽 (남쪽 기준 왼쪽에서의 거리)3: 블록의 서쪽 (서쪽 기준 위쪽에서의 거리)4: 블록의 동쪽 (동쪽 기준 위쪽에서의 거리)가능한 해결 전략블록을 일직선으로 펼..

📍 문제 탐색하기프로그래밍 대회 전날, 은상과 친구들은 술집에서 주어진 막걸리 주전자를 최대한 동일한 양으로 나눠 마시려고 한다.주어진 막걸리를 K명의 사람에게 똑같은 양으로 나눌 때, 최대 용량(ml)을 구하는 것이 목표이다.문제 조건 분석입력 조건첫 번째 줄:N (막걸리 주전자의 개수, N≤10,000)K (사람의 수, K≤1,000,000 )두 번째 줄부터: 각 주전자의 용량 (자연수, 최대 2^31 - 1)출력 조건나눠줄 수 있는 최대 막걸리 용량(ml) 출력가능한 문제 해결 전략완전 탐색 (Brute Force)1ml부터 최댓값까지 모든 용량을 시도하는 방법 → 시간 초과 가능성 높음시간 복잡도: O(K×N)이분 탐색(Binary Search) 적용 (최적 해법)가능한 용량 범위를 설정하고 이..

📍 문제 탐색하기양의 정수 A에서 K로 변경하는 최소 연산 횟수를 구하는 문제입니다.사용할 수 있는 연산은 다음 두 가지입니다:연산 1: 현재 수에 1을 더한다. → A=A+1연산 2: 현재 수에 2를 곱한다. → A=A×2목표:정수 A에서 시작하여 K로 만들기 위한 최소 연산 횟수를 출력한다.문제 조건1≤A최소 연산 횟수를 찾기 위해 최적의 경로 탐색이 필요함.연산이 빠르게 수행되도록 효율적인 방법 필요.가능 시간 복잡도완전 탐색(브루트포스): O(2^N) → 시간 초과 가능성.BFS(너비 우선 탐색): O(N) → 최적해 보장.역방향 탐색(탑다운 방식): O(log⁡N) → 효율적인 방식.📍 코드 설계하기이 문제를 해결하기 위해 탑다운 방식(역방향 탐색)을 적용했다.K에서 A로 거꾸로 접근하여 연..

📍 문제 탐색하기용액 문제는 주어진 용액들 중 두 개의 용액을 선택하여 특성값의 합이 0에 가장 가까운 조합을 찾는 문제입니다.입력으로 주어진 용액들은 이미 오름차순 정렬되어 있으며, 음수와 양수로 구성되어 있을 수도 있습니다.이 문제의 목표는 시간 복잡도를 줄이기 위해 투 포인터(Two Pointers) 기법을 사용하여 빠르게 해결하는 것입니다.문제 조건용액의 개수 N: 2≤N≤100,000용액의 특성값 범위: −1,000,000,000≤ai≤1,000,000,000​입력 데이터 특징:오름차순 정렬되어 주어짐.중복된 특성값이 없음.산성 용액과 알칼리성 용액만으로도 조합 가능.가능한 시간 복잡도브루트포스(완전 탐색): O(N^2)→ N이 최대 100,000이므로 시간 초과.투 포인터(Two Pointe..

📍 문제 탐색하기나무 자르기 문제는 상근이가 필요한 나무의 길이 MMM을 확보하기 위해 절단기의 높이 H를 조정하여, 나무를 절단한 후 가져갈 수 있는 최대 절단 높이를 찾는 문제이다.각 나무의 높이보다 절단기 높이가 낮다면 해당 나무의 일부가 잘리며, 절단기 높이보다 낮은 나무는 잘리지 않는다.M 이상의 나무를 가져갈 수 있는 절단기의 최댓값을 구하는 것이 목표이다.문제 조건나무 개수 N: 1≤N≤1,000,000필요한 나무의 길이 M: 1≤M≤2,000,000,000나무의 높이 hi​: 0≤hi≤1,000,000,0000나무의 총 높이 합은 항상 M 이상이므로, 반드시 필요한 만큼 나무를 얻을 수 있음이 보장된다. 가능한 시간 복잡도완전 탐색(브루트포스) 사용 시:최댓값을 1부터 나무의 최대 높이까..

📍 문제 탐색하기선분 위의 점 문제는 1차원 좌표 상의 N개의 점과 M개의 선분이 주어졌을 때,각 선분에 속하는 점의 개수를 빠르게 구하는 문제이다.점의 좌표와 선분의 시작점, 끝점이 주어지며, 점의 좌표는 중복되지 않는다.문제 조건점의 개수 N: 1≤N≤100,000선분의 개수 MMM: 1≤M≤100,000점의 좌표: 서로 중복되지 않으며, 1≤xi≤1,000,000,000선분의 시작점과 끝점: 1≤li,ri≤1,000,000,000출력 조건각 선분마다 포함된 점의 개수를 한 줄에 하나씩 출력한다.가능한 시간 복잡도N,M이 최대 100,000이므로 단순한 선형 탐색을 수행할 경우 O(N×M)으로 비효율적이다.효율적인 탐색을 위해 이분 탐색을 사용하면 O(Nlog⁡N+Mlog⁡N)로 해결 가능하다.📍..

📍 문제 탐색하기어두운 굴다리 문제는 길이 N의 굴다리에서, 설치된 M개의 가로등이 굴다리 전체를 밝힐 수 있도록 최소한의 높이 HHH를 계산하는 문제이다.각 가로등은 높이HH만큼 주위를 밝힐 수 있으며, 모든 가로등의 높이는 동일해야 한다.문제 조건굴다리 길이 N: 1≤N≤100,000가로등 개수 M: 1≤M≤N가로등 위치 x: M개의 가로등 위치가 오름차순으로 주어진다.가로등의 높이 H: x에서 왼쪽으로 H, 오른쪽으로 H 범위를 밝힌다.출력 조건모든 구간(길이 0부터 N)이 밝아지도록 하는 최소 높이 H를 출력한다.입력 범위가로등 위치는 오름차순으로 주어짐.모든 가로등 높이는 동일해야 함.굴다리 길이가 크기 때문에, 선형 탐색 대신 이분 탐색이 필요하다.가능한 시간 복잡도이분 탐색: log⁡N가로..

📍 문제 탐색하기오목 문제는 19×19 바둑판에서 가로, 세로, 대각선 방향으로 같은 색의 바둑알이 정확히 5개 연속된 경우 승리를 판별하는 문제이다. 주어진 바둑판 상태에서 검은 돌(1) 또는 흰 돌(2)이 이겼는지 판단하고, 승리한 경우 해당 돌의 시작 좌표를 출력한다.문제 조건승리 조건:같은 색의 바둑알이 정확히 5개 연속된 경우.6개 이상 연속되면 승리가 아님.출력:승리한 돌의 색상(1 또는 2)과 가장 왼쪽/위쪽의 바둑알 좌표(1-based).패배 조건:승부가 결정되지 않으면 0 출력.입력 범위바둑판 크기: 19×19돌의 값:1: 검은색 돌2: 흰색 돌0: 빈 칸가능한 시간 복잡도모든 칸(19×19)을 탐색하면서 4방향에 대해 확인:O(361×4) = 약 1,444 연산.📍 코드 설계하기1...