αλγριθμο

https://codeforces.com/contest/1557 Dashboard - Codeforces Round #737 (Div. 2) - Codeforces codeforces.com 처음으로 써보는 코드포스 후기입니다. 사진을 보시면 아시겟지만 일단 망쳤어요. 쓸데없는 변명을 하자면 암흑기가 온 것 같습니다... 어쨌든, 대회 때 푼 거랑 업솔빙해서 푼 거 합쳐서 3솔을 햇구요, 푼 문제의 풀이를 올려보려 합니다. A. Ezzat and Two Subsequences 사용한 알고리즘: 정렬, 누적합 풀이 입력받은 배열을 정렬하고 각 \(i\)번째와 \(i - 1\)번째 사이를 갈라 두 구간으로 나눠본 다음 두 구간합의 평균의 합중 최대값을 구하면 됩니다. \((1 < i \leq N)\) 왜 굳..

문제 https://www.acmicpc.net/problem/2984 2984번: 고속도로 상근이네 트럭 운송 회사가 내야하는 고속도로 이용 요금의 최솟값을 출력한다. 이 값은 32비트 정수 범위를 넘어갈 수 있기 때문에, 64비트 정수(C/C++: long long)을 사용해야 한다. www.acmicpc.net 알고리즘 DP 풀이 입력에서 맨 처음에 \(N\)을 입력받은 후, \(N\)개의 쌍이 주어지는데, 각 \(i\)번째 쌍에서 첫 번째 수를 \(a_i\), 두 번째 수를 \(b_i\)라고 하겠습니다. 이번 문제는 간단하게 말하자면 입력받은 배열 \(a\)와 \(b\)를 적절히 재배치해서 새로운 쌍들을 만들었을 때 각 쌍의 두 수의 차의 합이 최소가 되게끔 만드는 문제입니다. 그냥 두 배열을 정..

문제 https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 알고리즘 그리디 구성적 풀이 LIS와 LDS의 공통 원소는 무조건 1개이므로 바이토닉 수열 형태로 문제를 해결할 수 있습니다. 먼저 \(N - M + 1\)부터 \(N\)까지의 수로 앞을 채우고, \(K - 1\)부터 \(1\)까지의 수로 그다음을 채웁니다. LDS의 첫번째 원소는 LIS의 마지막 원소이므로 \(K - 1\)개만 채우면 됩니다. 나머지 수들은 이 원리로 채워 나가면 되는데, \(N\)과 \(1\)을 채우지 않은 수들 중 최대값과 최소값으로 바꾸면서 범위를 줄여나갑니다. 그리고, \(M\)과 \(K\)는 바로전 LDS와 LIS..

문제 https://www.acmicpc.net/problem/2516 2516번: 원숭이 첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N이 주어진다. 단, N은 3이상 100,000이하의 정수이다. 둘째 줄부터 N개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭 www.acmicpc.net 알고리즘 그리디 구성적 풀이 어려워 보이지만 잘 생각해보면 의외로 간단한 문제입니다. 먼저 모든 원숭이를 한 곳에 집어넣은 다음, 각 원숭이마다 같은 우리 안에 있으면서 앙숙관계인 원숭이가 2마리 이상이라면 그 원숭이를 다른 우리에 넣는 방식으로 풀어나가면 됩니다. 각 원숭이마다 앙숙관계인 원숭이가 최대 3마리이므로, 각 원숭이마다 최대 3번 이동시키면 답을 구할 수 있습니다. 전체 코드..

문제 https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 알고리즘 Union-Find 풀이 배열 2개를 만들어 다음과 같이 정의합니다: \(uf[i]:\) \(i\)가 속한 집합의 루트 노드 \(dist[i]:\) \(i - i\)가 속한 집합의 루트 노드 UNKNOWN인지 아닌지는 \(find\) 함수를 사용해 같은 집합에 있는지 아닌지 확인하면 쉽게 알 수 있습니다. 입력 받은 \(a, b\)의 차를 구할 때는 \(..

문제 https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 알고리즘 DP 배낭 문제 슬라이딩 윈도우 (optional) 풀이 \(N\)개의 직사각형 블록을 이용하여 만든 높이가 같은 두 탑의 높이가 최대가 되게 해야 하며, 모든 직사각형 블록을 다 사용할 필요는 없습니다. 즉, \(i\)번째 직사각형 블록을 쌓거나 쌓지 않거나로 나눌 수 있습니다. 그러므로, \(dp[i][j]\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j..

문제 https://www.acmicpc.net/problem/5444 5444번: 시리얼 넘버 위대한 기타리스트 강토는 공연을 앞두고 있다. 이제 무대에 올라가야 하는데, 기타가 다른 사람들의 기타와 섞이고 말았다. 또, 강토는 어떤 기타가 자기 것인지 까먹었다. 다행히도, 모든 기타 www.acmicpc.net 알고리즘 DP 슬라이딩 윈도우 풀이 각 테스트케이스마다 \(N\)개의 시리얼 넘버 \(S_{1} ... S_{N}\)과 \(M\)이 주어졌을 때 \(dp[i][j]\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j]:\) \(i\)번째 기타까지 고려했을 때 시리얼 넘버의 합을 \(M\)으로 나눈 나머지가 \(j\)가 되게 하는 기타의 최대 개수. 위와 같이 정의한다면, \(dp[i][j..

문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 알고리즘 다익스트라 풀이 다익스트라의 원리와 우선순위 큐만 잘 사용하면 쉽게 풀 수 있습니다. 먼저, 기본적으로 그래프를 탐색할 우선순위 큐 \(Q\)를 생성합니다. \(Q\)를 사용하는 방식은 일반적인 다익스트라에서 쓰는 방식과 같습니다. 다음으로, 우선순위 형태의 배열 \(M\)을 생성합니다. \(M_{i}\)에 \(i\)번 도시로..