NOIP 연습 세션 #1 상세 문제 풀이
문제 A: 점 쌍의 각도 최적화
이 문제는 두 점 사이의 관계를 최적화하는 전형적인 그리디 알고리즘 문제입니다. 데이터 범위를 고려했을 때 $O(n \log n)$ 시간 복잡도가 필요하며, 정렬을 활용해야 합니다.
핵심 아이디어는 좌표축을 45도 회전시키는 것입니다. 기존 좌표 $(x, y)$를 $(x+y, x-y)$로 변환하면, $y=x$ 또는 $y=-x$에 가장 가까운 값을 찾는 문제가 됩니 ...
6월 28일 01:33에 게시됨
:NOIP 시뮬레이션 경진대회 문제 풀이
T1 다채로운 색상
문제는 다음과 같습니다:
nxm 크기의 행렬이 주어집니다.
(i,j) 위치에는 색깔 ci,j가 있습니다.
네 모서리의 색상이 모두 동일하지 않은 모든 하위 행렬의 수를 구하세요.
시간 복잡도 O(n²m)으로 해결할 수 있습니다. 두 행을 선택한 뒤 열을 스캔하면서 해당 열의 값들이 같으면 답에 기여할 가능성이 있습니다. 이를 위해 카운트 배열을 ...
6월 17일 19:19에 게시됨
NOIP 2012 차량 여행 문제 해결: 양방향 연결 리스트와 이진 리프팅 최적화
문제 개요
NOIP 2012 심화 그룹의 '차량 여행' 문제는 두 운전자 A와 B가 번갈아 가며 동쪽(도시 번호가 증가하는 방향)으로 이동할 때의 경로를 시뮬레이션하고 최적의 출발지를 찾는 문제입니다.
운전 규칙: A가 먼저 운전하고 B가 다음에 운전하는 방식으로 번갈아 진행합니다.
도시 선택 기준:
운전자 B: 현재 도시와 해발 고도 차이의 절댓값이 가장 작은 도 ...
6월 8일 01:37에 게시됨
NOIP 13연속 모의고사 #2 풀이
A번: 역순 배열직접 패턴을 분석해보면 규칙을 발견할 수 있다. 인덱스가 홀수번째끼리, 짝수번째끼리 서로 인접하며, 전체 배열은 홀수/짝수 인덱스 그룹이 번아 등장하는 형태가 된다.구체적으로 다음과 같이 구성된다:n이 홀수: aₙ, aₙ₋₂, ... , a₁ 뒤에 a₂, a₄, ... , aₙ₋₁n이 짝수: aₙ, aₙ₋₂, ... , a₂ 뒤에 a₁, a₃, ... , aₙ₋₁시간 복잡도는 O(n)이다.#include <b ...
5월 28일 16:51에 게시됨