자라자

📍 문제 탐색하기용액 문제는 주어진 용액들 중 두 개의 용액을 선택하여 특성값의 합이 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가로..

다리 길이 w만큼 트럭이 동시에 올라갈 수 있고, 다리의 최대하중 L을 초과해서는 안 된다.트럭들은 1단위 시간에 1단위 거리씩만 전진할 수 있으며, 다리 위에 완전히 올라가지 못한 트럭의 무게는 아직 다리에 가해지는 무게로 계산하지 않는다는 점이 핵심이다.예시로, 다리 길이 w=2, 최대하중 L=10, 트럭 무게가 [7,4,5,6]일 때, 모든 트럭이 다리를 건너는 최단 시간은 8이 된다.문제 조건 및 분석트럭의 수 n: 1≤n≤1,000다리의 길이 www: 1≤w≤100최대하중 LLL: 10≤L≤1,000트럭 무게: 각 트럭의 무게 ai​는 1≤ai≤10이때, 모든 트럭이 다리를 건너는 최단 시간을 구해야 한다.입력 범위n이 최대 1,000이므로, 각 트럭을 순차적으로 확인하면서 시간을 계산해도 충분..

📍 문제 탐색하기오목 문제는 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...

📍 문제 탐색하기숫자 야구 문제는 숫자 조합을 이용해 가능한 정답 후보를 추려내는 문제이다.영수가 정한 세 자리 수를 민혁이의 질문과 영수의 답변을 바탕으로 추측한다.문제 조건영수가 정한 세 자리 수는 1~9의 서로 다른 숫자로 구성된 수이다.민혁이는 질문한 숫자와 스트라이크/볼 개수를 통해 힌트를 얻는다:스트라이크: 위치와 숫자가 모두 일치.볼: 숫자는 일치하지만 위치가 다름.모든 질문과 답변은 모순이 없도록 주어진다.입력 범위질문의 개수 N: 1≤N≤100숫자 조합: 9P3=9×8×7=504개의 후보가 존재.가능한 시간 복잡도각 후보에 대해 N개의 질문을 확인하므로 O(504×N) = 약 50,400 연산으로 해결 가능하다.알고리즘 선택모든 후보(1~9의 세 자리 수) 생성:가능한 모든 세 자리 수..

📍 문제 탐색하기로봇 문제는 정사각형 영역 SSS에서 로봇이 주어진 명령어 열에 따라 이동한 뒤 최종 위치를 계산하는 문제다.문제 조건영역 S는 (0,0)에서 (M,M)까지의 정사각형이다.로봇은 (0,0)에서 동쪽을 바라보고 시작한다.명령어는 두 가지:TURN dir:TURN 0: 왼쪽 90도 회전TURN 1: 오른쪽 90도 회전MOVE d: 현재 방향으로 d만큼 이동.명령어 수행 후 로봇이 S의 경계 또는 내부에 있어야 한다.모든 명령어가 유효하면 최종 위치를 출력하고, 하나라도 유효하지 않다면 −1을 출력한다.입력 범위1≤M,n≤1,000각 명령어의 d: 1≤d≤1,000시간과 메모리 제약을 고려해야 한다.가능한 시간복잡도명령어 n개에 대해 각 명령어를 상수 시간에 처리하므로 O(n)에 해결 가능하..