본문 바로가기

코딩

(10)
BOJ 7469 K번째 수 (in Q log N!) https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net Step 1 ($O(M \log^3 N)$) 이 단계는 머지 소트 트리를 알고 있다면 누구나 풀 수 있습니다. 머지 소트 트리는 일반적인 세그먼트 트리와 비슷한데, $[l, r]$ 구간을 담당하는 노드에는 $[l, r]$ 구간에 있는 수들을 정렬해서 배열 형태로 저장해 둔 세그먼트 트리를 말합니다. 머지 소트 트리의 구축은 모든 노드에 대해 정렬을 독립적으로 하면 $O(N \log^2 N)$에 가능합니..
Problem Solving Diary #2 IOI 2015 Day 1. Teams 서브태스크 1, 2 (34점) $O(NQ)$로 풀 수 있는 경우 어떻게 쉽게 풀 수 있을까요? 그리디한 접근을 생각해 봅시다. 정원 수가 작은 프로젝트부터 보면, 현재 넣을 수 있는 사람들 중 $B_i$가 가장 작은 사람을 넣는 게 이득입니다. (나중에 가능성이 있는 사람을 남겨 둬야 하므로) 따라서 사람들을 $A_i$ 순서로 정렬하고 프로젝트를 정원 수에 따라 정렬한 뒤에, 힙을 사용하여 $B_i$가 작은 사람부터 뽑아내면 됩니다. 시간 복잡도는 $O(NQ \log N)$입니다. 더보기 #include #include "teams.h" using namespace std; typedef long long ll; int n; pair arr[500002]; void..
Problem Solving Diary #1 IOI 2020 Day 1. Comparing Plants 대회 때 멘탈이 제대로 갈려나간 문제입니다. 다음 대회를 망치지 않기 위해서는 이런 문제를 풀어야 한다고 생각해서 잡고 풀었습니다. 서브태스크 1 (5점) $k=2$로, 바로 옆의 식물과의 대소관계를 확실히 알 수 있습니다. 어떤 식물 $x$가 식물 $y$보다 확실히 크려면 (문제 조건에 의해 $x h_{x+1} > \cdots > h_{y-1} > h_y$ $h_x > h_{x-1} > \cdots > h_1 > h_n > \cdots > h_{y+1} > h_y$ 첫 번째 조건은 $s_x = s_{x+1} = \cdots = s_{y-1} = 0$에 대응되고, 두 번째 조건은 $s_1 = \cdots = s_{x-1} = s_y = \cdot..
2021 국대 멘토링 일지 - 3주차 이번 멘토링 셋은 JOI 2020으로, 4시간 동안 5문제를 풀어야 했습니다. 전체적인 난이도는 예상했던 것보다는 할 만했던 것 같습니다. 시간대별로 상황을 서술하겠습니다. 3주가 2주보다 먼저 올라오는 이유는... 아직 2주 문제들을 구현해보지 못했기 때문입니다. #1. Just Long Neckties (0:00 ~ 0:06) 만약 $A$와 $B$가 모두 정해진다면, 둘 다 오름차순으로 정렬한 뒤 같은 순서에 있는 것끼리 matching하는 것이 최적임을 쉽게 보일 수 있습니다. 따라서 $A$에서 가장 큰 것을 빼고 나머지끼리 matching시켜 답을 구한 뒤에, $A$의 값을 하나씩 바꿔 주면서 multiset 등을 이용해 계속 가장 큰 값을 찾아내면 됩니다. Time Complexity: $O(N..
2021 국대 멘토링 일지 - 1주차 이번 주부터 국대 멘토링 교육이 시작되었습니다. 내신 준비로 시간이 충분하지 않아 일부 문제들은 풀이만 생각하고 구현을 아직 해 보지 않았는데, 시험이 끝나는 대로 구현해 볼 예정입니다. 제가 배정받은 문제 세트는 다음과 같습니다. #1. Trous de Loop (BOJ 18368) 조건을 만족하는 가장 긴 구간을 찾는 문제이므로 투 포인터를 이용합니다. 각 구간에서 자기 내부의 길이 $d$ 구간 중 구간 합이 최대인 것을 찾아야 하는데, 이 문제는 사실 누적합을 이용하면 투 포인터를 돌리면서 구간 내의 최댓값을 빠르게 찾는 문제가 되고, 이는 덱으로 해결 가능합니다. 따라서 문제가 쉽게 풀립니다. Time Complexity: $O(N)$ #2. Highway Modernization (BOJ 183..
[초급] 그래프 이번 게시글에서는 그래프가 무엇인지에 대해서 살펴보겠습니다. 그래프 그래프는 정점들이 간선들로 연결되어 있는 형태를 말합니다. 여기서 정점은 교차로와 비슷한 개념이고, 간선은 도로와 비슷한 개념입니다. 왼쪽과 같은 그래프에서 정점은 총 6개이고, 간선은 총 8개입니다. 오른쪽 그래프에서 정점은 총 8개이고, 간선은 5개입니다. 간선에 방향이 있는 그래프를 유방향 그래프, 방향이 없는 그래프를 무방향 그래프라고 합니다. 위에 있는 그래프는 모두 무방향 그래프입니다. 아무 두 정점이나 잡았을 때, 간선을 통해 오고 갈 수 있다면 연결 그래프(connected graph)라고 합니다. 연결 그래프가 아닌 그래프(disconnected graph)에서, 간선을 통해 서로 오고 갈 수 있는 점들의 집합을 연결 성..
[초급] 비트마스크 이 글에서는 이진법의 성질을 이용해 문제 풀이를 쉽게 해 주는 기법인 비트마스크(Bitmask)에 대해 배워 보겠습니다. 이진법 대부분 아시겠지만, 먼저 이진법에 대해 간단하게 정리해 봅시다. 우리가 사용하는 수는 십진법입니다. 십진법은 0에서 9까지의 숫자를 이용해서 어떤 정수라도 표현할 수 있습니다. 컴퓨터는 이진법을 사용하는데, 이진법은 0과 1만으로 모든 수를 표현합니다. 십진법 수의 맨 오른쪽 자리는 일(1)의 자리입니다. 그 왼쪽 자리는 10의 자리이고, 한 칸 더 왼쪽으로 가면 $10^2 = 100$의 자리입니다. 이진법도 마찬가지입니다. 맨 오른쪽 자리는 1의 자리, 그 왼쪽 자리는 2의 자리이고, 계속 한 칸씩 왼쪽으로 갈수록 4의 자리, 8의 자리와 같이 커집니다. 간단한 예시로, 십진..
[초급] 백트래킹 이번에는 백트래킹에 대해 배워 보겠습니다. 백트래킹 백트래킹(Backtracking)은 모든 경우를 계산해 보는 기법을 말합니다. 비슷한 의미의 단어로 브루트 포스(Brute Force)가 있습니다. 여기서는 가장 일반적으로 사용되는, 재귀 함수를 이용한 백트래킹을 다루겠습니다. 백트래킹의 가장 중요한 개념은 막히면 되돌아간다라는 개념입니다. 이해를 돕기 위해 가장 대표적인 예시인 N-Queen 문제를 살펴봅시다. N-Queen 문제는 $N \times N$ 크기의 체스판에 $N$개의 퀸을 서로 공격할 수 없게 배치하는 문제입니다. 체스 문제 같아 보이지만, 이 문제를 여기서 설명하는 이유는 바로 이 N-Queen 문제가 유명한 NP 문제 중 하나이기 때문입니다. 아래 배경 지식은 읽으실 분만 읽고 넘어..