Codeforces Round 886 (Div. 4) 주요 문제별 최적화 알고리즘 해설
전반적으로 난이도가 낮았으나, 특정 문제에서는 접근 방식의 세부적 오류가 성능 저하를 유발할 수 있었다. 특히 E 문제와 같이 이분 탐색을 활용할 때는 범위의 정확한 설정이 중요했으며, F 문제에서는 초기 입력 해석의 부주의가 문제를 복잡하게 만들었다. 이하에서는 각 문제별로 효율적인 구현 방식을 검토하고 최적화 코드를 제시한다.
문제 D: 구간 연결성 최적 ...
9월 17일 14:08에 게시됨
이진 탐색을 활용한 피크 요소 찾기
문제 설명
LeetCode 162번 문제인 "피크 요소 찾기"를 해결하는 방법에 대해 알아보겠습니다. 이 문제에서는 주어진 배열에서 피크 요소(즉, 그 이웃보다 큰 요소)를 찾아야 합니다.
해결 전략
배열의 인접한 요소들은 서로 같지 않으며, 피크는 여러 개 존재할 수 있습니다. 전체 배열의 최댓값은 항상 피크 중 하나입니다. 따라서 단순히 배열을 순회하며 최 ...
9월 9일 01:15에 게시됨
C++ 환경에서의 효율적 데이터 탐색과 정렬 전략 분석
1. 정렬된 시퀀스 기반 검색 메커니즘
데이터가 순차적으로 정리되어 있는 배열이나 벡터 내 특정 값을 신속하게 locating 하는 것은 알고리즘 설계의 핵심 요소다. 여기서는 대표적인 비선형 탐색 기법 세 가지를 다룬다.
1.1 이분 탐색 (Binary Search)
범위를 반으로 나누어 목표값을 축소하는 고전적인 방법이다. 선형 검색의 O(n) 한계를 극복하고 로그 시간인 O(log ...
7월 17일 06:51에 게시됨
LeetCode 알고리즘 문제 분석: 이분 탐색을 이용한 최적해 도출 기법
문제 1: 일별 최대 작업 시간 최소화 (LCP 12)
특정 프로젝트 진행 시 전체 작업량을 $N$개의 과제들로 나누어 $M$일 동안 처리해야 하는 상황을 가정합니다. 각 과제에는 고유한 수행 시간이 존재하며, 반드시 순서대로 실행되어야 합니다. 다만, 매일 한 번씩 전문가의 도움을 받아 특정 과제의 소요 시간을 제로로 할 수 있는 기회가 주어집니다. 이 조건 하에서 $M$일 ...
7월 7일 04:35에 게시됨
Java 알고리즘 풀이: 텐센트 2018 상반기 채용 기출 문제
문제 1: 교차 부호 수열의 합
길이 n의 연속된 정수 수열 1, 2, 3, ... n에 대해, 매 m개마다 부호를 교차시키는 수열을 정의합니다. 초기 부호는 음수(-)이며, 부호는 -, -, ..., +, +, -, -, ... 순서로 반복됩니다. 이때 처음 n개 항의 총합을 구하는 문제입니다.
입력 조건: 두 정수 n, m (2 ≤ n ≤ 10⁹, 1 ≤ m), n은 2m으로 나누어 떨어짐
출력: 처음 n개 항의 합
...
6월 6일 22:56에 게시됨