문제https://www.acmicpc.net/problem/26086 26086번: 어려운 스케줄링첫째 줄에 업무의 고유번호의 범위 제한 $N$과 명령 횟수 $Q$, $k$가 주어진다. ($1\leq N,Q \leq 100\,000,\ 1\leq k \leq$ '0번 명령의 등장 횟수') 둘째 줄부터 $Q$개 줄에 걸쳐 명령에 대한 정보가 주어진다.www.acmicpc.netstack 구조의 스케쥴러를 이용해 명령을 수행하고 k번째로 처리할 업무를 찾는 문제였다. 명령은 다음과 같다.0 p : 스케줄러의 맨 앞에 번호 p인 업무를 추가한다.1 : 스케줄러의 업무를 p 기준으로 오름차순 정렬한다.2 : 스케줄러의 업무 처리 순서를 뒤집는다.명령 횟수는 100000, 시간 제한은 1초였다. 문제 풀이명령 ..
문제https://www.acmicpc.net/problem/31476 31476번: :blob_twintail_thinking:첫째 줄에는 양갈래 굴의 방 중 가장 깊은 곳의 깊이 $D(1 \le D \le 12)$와 파손된 길목의 수 $N(0 \le N \le 2^D-2)$, 각 블롭 세력이 기본적으로 탐색하는 시간인 $U(1 \le U \le 100)$와 양갈래 블롭들이 갈라www.acmicpc.net트리를 레벨 순회, 중위순회 하는 문제였다. 양갈래 블롭같은 레벨은 가장 오래 걸린 시간이 소요된다.이때, 분기할 때마다 소요 시간이 T만큼 증가한다 (U+T, U+2*T, U+3*T...)포니테일 블롭중위순회 하면서 갔다가 돌아오는 길에도 탐색 시간이 U만큼 소요..
문제 https://www.acmicpc.net/problem/24461 24461번: 그래프의 줄기 그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 $0$이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다. 우리는 이 그래프의 정점 중에서 연결된 www.acmicpc.net 가장자리 정점을 '동시에' 없애는 행동을 가장자리 정점이 2개 이하로 남을 때까지, 즉 일직선이 될 때까지 반복하고 남은 일직선의 정점을 오름차순으로 출력하는 문제였다. 문제 풀이 그래프를 생성하면서 in, out 배열을 만든다. 초기 가장자리 정점 queue를 생성한다. in, out이 모두 1인 정점이 가장자리 정점이 된다. 가장자리 정점 제거 queue에 담긴 정점을 제거한다. 제거..
문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 수열의 공통 부분 수열 중 가장 긴 것을 찾는 문제였다. 문제 풀이 dp를 사용해 풀었다. dp 점화식을 말에서 식으로 바꾸는 것이 조금 헷갈렸지만 표를 그려보니 바로 이해가 됐다. 주어진 예시를 이용해 dp 배열을 만들면 위와 같은 모양이 된다. 0행 1열은 AC와 C의 LCS 길이, 1행 2열은 ACA와 CA의 LCS 길이가 된다. 그 ..
문제 https://www.acmicpc.net/problem/15573 15573번: 채굴 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., www.acmicpc.net 채굴기의 성능 D보다 강도가 약하고, 공기와 맞닿은 광물만 채굴할 수 있을 때 K 이상을 채굴할 수 있는 최소 강도 D를 구하는 문제였다. 문제 풀이 D가 최대 1000000이고, map의 크기가 최대 1000000인 문제였기 때문에 완전 탐색이 불가능했다. 이전에 이와 비슷한 문제를 푼 적이 있어서 바로 이분탐색으로 D를 구하는 방법을 생각했다. 각 D마다 bfs를 진..
문제 https://www.acmicpc.net/problem/12892 12892번: 생일 선물 첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0 www.acmicpc.net 가격의 차이가 D 미만이 되는 최대 만족도를 구하는 문제였다. 문제 풀이 투포인터를 사용하는 문제였는데 정렬을 한 후에 투포인터를 이용해 구간을 옮기며 해당 구간의 만족도를 구하고 최댓값을 갱신해 해결했다. /* 가격의 차이가 최대 D가 되는 최대 만족도 구하기 정렬 후 투포인터 */ int main() { int N, D; v..
문제 https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 모든 사람은 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다. 다음과 같은 이용 규칙으로 모든 사람이 기다리지 않는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하는 문제였다. 문제 풀이 처음에 비어있는 자리 중 번호가 가장 작은 자리에 앉는다는 규칙을 제대로 보지 않아서 틀렸었다. ..
문제 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 해당 조건에 맞게 짠 가장 많은 팀 수를 구하는 문제였다. 문제 풀이 Union-Find 알고리즘을 이용해 풀었다. 친구와 원소 그래프 벡터를 따로 만들었고 조건에 맞게 makeUnion 해주는 과정을 반복했다. 친구끼리는 makeUnion을 해줬으며 원수일 경우에는 해당 원수의 원수 리스트 모두에 대해 makeUnion을 해줬다. team 개수를 찾을 때에는 set을 이용해서 다른 parent를 가진..
