홍시홍의 프로그래밍

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 요구사항 1. 말과 map의 구현 말 구조체 사용, map은 vector 사용 2. 순서대로 이동하기 1~말의 갯 수 까지 순서..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) (1, j)는 ( www.acmicpc.net 요구 사항 1. 회전판 구현하기 deque로 회전판을 구현한다. 2. 회전판 회전하기 deque로 구현한 회전판을 시계방향, 시계..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 요구 사항 1. 구역 나누기 - 문제에 주어진 범위대로 구역을 나누어 준다 2. 합 구하기 - 범위마다 합을 구한다 3. 구역의..

구간 트리란 구간의 합을 구하기 위한 트리 시간 복잡도 O(logn) 트리 만들기 구간 별 합을 저장할 수 있도록 한다. 트리는 완전 이진 트리로 구성되어 있다 자식은 왼쪽 자식은 *2, 오른쪽 자식은 *2+1이다 위 점을 활용하여 각 구간의 합을 부모에 저장한다 트리 갱신 해당 Index를 포함하는 구간을 현 Index의 값과의 차이를 합하여 갱신한다 특징 1. 배열로 구성 - 배열의 크기는 보통 N*4 - 2^k로 N을 넘을수 있는 최소 수 구간 트리의 updata 그 수를 포함한 모든 노드들을 업데이트 시켜준다 구간 트리의 탐색 탐색은 4가지 경우가 발생한다 1. 탐색 구간이 겹치지 않는 경우 - 종료 2. 탐색 구간이 정확히 일치하는 경우 - 탐색 완료 3. 탐색 구간이 내부에 포함되는 경우 - ..