코딩 (9) 썸네일형 리스트형 BOJ 4013 : ATM 문제 링크 : https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net SCC 응용 문제입니다. 간단해 보이지만 처리해줄게 많고 구현량이 많아 생각보다 어려웠습니다. 문제를 간략하게 정리하면, 그래프가 주어지며 각 정점은 현금을 가지고 있습니다. 이때, 시작 정점과 도착가능한 정점이 주어질 때 인출할 수 있는 현금의 최댓값을 출력해야 합니다. 현금의 액수는 0이상의 정수이기 때문에 하나의 SCC에서는 모든 정점의 현금을 인출하는 것이 이득.. Problem Solving Review #2 [06.04~06.06] 기회가 생겨 3일동안 많은 문제를 풀게 되었습니다. 문제가 많았고 다른 대회들이나 기말고사와 겹치다 보니 많이 늦어졌지만 좋은 문제들이 많았기에 정리해서 올리게 되었습니다. BOJ 20960. Po 아이디어는 간단하지만 이를 파악하기가 어려웠습니다. 결론적으로는 스택을 이용하여 간단하게 해결할 수 있습니다. 입력받은 배열 \(a\)를 순차탐색하면서 스택에서 \(a[i]\)보다 큰 원소들을 제거하고 알맞은 위치에 삽입해주면 됩니다. 다만, 스택에 이미 \(a[i]\)와 같은 값을 가진 원소가 존재한다면 \(a[i]\)값을 만들기 위해 추가적인 increasing의 작업을 거칠 필요가 없기 때문에 스택에 \(a[i]\)를 추가해주지 않아도 됩니다. 결과적으로 스택에 \(a[i]\)를 삽입한 횟수를 세어 출력.. USACO 2022 March Silver 후기 및 풀이 https://www.acmicpc.net/category/655 USACO 2022 US Open Contest www.acmicpc.net 2021-2022 USACO 대회가 이번 US Open 을 끝으로 종료되었습니다. 목표했던 만큼은 아니지만 그래도 만점을 받고 Gold Division에 갔다는 사실에 만족하고 있습니다. 이번 문제들은 상대적으로 조금 쉬웠던 것 같습니다. 0:00 ~ 0:30 간단하게 3문제를 읽고 입력만 구현해놓았습니다. 1번은 대충 그래프일 것 같았고, 2 3번은 문자열좀 끄적이다 보면 풀이가 나올 것 같았습니다. 0:30 ~ 0:55 : COW Operations 3번 문제의 예제를 접근하다보니 규칙만 찾으면 풀릴 것 같아 3번부터 풀었습니다. 먼저 문자가 1개, 2개, 3.. Problem Solving Review #1[2022.3월 1주 - 3월 3주] 3월의 시작부터 3주차까지 풀었던 문제들과 개념들을 정리해보고자 합니다. 앞으로 문제를 풀어나가는데 있어서도 정리해둔 것이 도움이 될 것 같고, 알고리즘을 자꾸 까먹는 저에게 가장 필요한 습관이 아닐까 생각이 들어 지속적으로 작성하려고 합니다. BOJ 2631. 줄세우기 KOI 2001 > 중등부 2번 간단한 관찰을 통해 한 가지 사실을 발견한다면 해결할 수 있지만, 처음 볼 때는 의외로 관찰이 떠오르지 않았습니다. LIS(Longest Increasing Sequence) 에 포함되는 아이들을 고정해놓고 나머지 아이들을 움직여야지만 최소의 아이들을 옮길 수 있기 때문에 간단히 DP로 LIS를 구현하여 해결할 수 있습니다. #include using namespace std; int n, a[202], .. BOJ 15972 : 물탱크 문제 링크 : https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net 우선순위큐와 BFS를 이용한 문제입니다. 결론적으로 물이 마지막에 빠져나가는 구멍은 바깥과 연결된 구멍일 것입니다. 따라서, 역으로 바깥과 연결된 구멍이 있는 칸부터 우선순위큐에 저장합니다. 우선순위큐에서는 {물의 높이, 칸의 x 좌표, 칸의 y 좌표}를 저장하며 물의 높이에 따라 오름차순으로 정렬됩니다. 이후 우선순위큐에서 BFS를 돌리는 과정에서 관찰이 필요합니다. 현재 칸과.. Codeforce Round #771 (Div. 2) 풀이 대회 링크 : https://codeforces.com/contest/1638 A번 문제 : Reverse 순열을 한번만 뒤집어 사전순으로 가장 빠르게 만들어야 하는 문제입니다. 순열과 사전순이라는 특성을 이용하여 입력받은 순열을 순차탐색하면서 \(p[i] != i\) 인 최초의 지점을 찾고 \(i\)를 값으로 가지는 순열의 위치를 찾아 두 개의 지점을 양 끝점으로 하여 reverse 연산을 해주면 사전순으로 가장 빠른 순열을 만들어줄 수 있습니다. #include using namespace std; typedef long long ll; int t, n, p[505]; int main() { scanf("%d", &t); while(t--) { scanf("%d", &n); int fir = 0; /.. USACO 2021 December Silver 풀이 https://www.acmicpc.net/category/612 USACO 2021 December Contest www.acmicpc.net UPD : USACO 2021 December Silver 1번 문제 풀이를 Silver 2, 3번을 추가하여 Silver 풀이로 업데이트 하였습니다. 1번 문제 : Closest Cow Wins 입력받는 patch의 위치와 Nhoj의 소들의 위치를 하나의 배열로 만듭니다. 오름차순으로 배열을 정렬하여 순차탐색하면서 patch의 값을 더해주다가 Nhoj의 소가 등장한다면 값을 우선순위큐에 저장하는 방식으로 해결할 수 있습니다. 다만, 두 마리의 Nhoj 소들 사이에 존재하는 patch가 여러개라면 이 값들을 나누어 저장해야 할 수도 있습니다. 이때 구간에 아무리.. KOI 2021 2차 고등부 2번 풀이(그래프 균형 맞추기) https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 1번 DP 생각해내는게 2번 풀이보다 어려웠다 2번 문제 해석과정에서 연립방정식을 생각해낼 수 있고, 이를 확장시키는 방식이다 먼저, 문제에서 주어진 예제를 해석해보았다. 왼쪽과 같은 그래프가 주어졌을 때 (1)번 정점의 값 C1을 기준으로 잡았을 때, 간선의 값을 반영하여 각 정점의 값을 표현해보면 C3 = 5 - C1 C5 = 3 - C3 = C1 - 2 C2 = -4.. 이전 1 2 다음
