Doby's Lab

https://www.acmicpc.net/problem/3295 3295번: 단방향 링크 네트워크 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상호 네트워크를 이루는 노드의 수 n과 단방향 링크의 수 m이 주어진다. (n ≤ 1,000, m ≤ 50,000) 노드는 0번부터 n-1 www.acmicpc.net Level: Platinum II Solved By: Bipartite Matching, Hopcroft Karp 문제의 내용을 요약하면 링을 구성하는 노드의 개수와 선형 배열의 노드의 개수 - 1을 구하라는 뜻입니다. 여기서 파악해야 할 것은 링의 구성 노드가 N 개라면 간선도 N 개라는 것, 그리고 선형 배열의 노드 개수가 N 개라면 간선은 N - 1개라는 ..

https://www.acmicpc.net/problem/1671 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net Level: Platinum III Solved By: Bipartite Matching, Edmonds Karp 잡아먹는 상어와 잡아먹히는 상어들을 이분 그래프로 나누어줍니다. 여기서 제가 원하는 네트워크는 소스로부터 잡아먹는 상어들에게 capacity 2를 주며 연결하고(한 상어당 2개까지 먹을 수 있기 때문), 잡아먹는 상어들이 잡아먹히는 상어들을 잡아먹을 수 있다면 capcit..

이번 대회는 2 솔브로 마무리하고, 풀 수 있을 거 같던 애매했던 두 문제(C, D)까지 풀고 난 후, 4가지 문제까지만 솔루션을 작성해보려 합니다. 대회가 끝난 직후의 포스팅에서도 말했지만 대회는 자신의 약점을 객관적으로 볼 수 있게 하고, 이를 보완할 수 있는 좋은 기회가 되는 거 같습니다. 나머지 E, F, G, H는 쓰여졌던 알고리즘들을 더 공부하여 보완해보려 합니다. 정확히는 쓰인 알고리즘들이 어떻게 응용되는가가 주목할 점이라 생각합니다. 대회 문제 링크: https://www.acmicpc.net/category/detail/3231 4th UNIST Algorithm Programming Contest Uni-CODE 2022 www.acmicpc.net A. 가장 긴 막대 자석 🤔 문제의 ..

https://www.acmicpc.net/problem/26125 26125번: 두 도로 첫 번째 줄에 교차로의 수 $N$, 기존 도로의 수 $M$, 집의 교차로 번호 $S$, 회사의 교차로 번호 $T$가 공백으로 구분되어 주어진다. ($2\leq N\leq 300$; $0\leq M\leq 3\ 000$; $1\leq S,T\leq N$; $S\neq T$) 이후 $M$개 www.acmicpc.net Level: Gold III Solved By: Floyd Warshall 각 쿼리마다 다익스트라를 쓰기에는 총 시간 복잡도는 O(Q * ElogV)로 시간 초과를 받게 됩니다. 그래서 오프라인 쿼리 같은 방법이 있을까 했지만, 떠오르지 않았습니다. 여기서 문제점은 '최단 경로들을 가지고 있는 배열이나 ..

https://www.acmicpc.net/problem/26124 26124번: 조명 배치 $(1,1)$, $(1,3)$, $(4,5)$ 위치에 각각 밝기 $3$, $5$, $3$의 조명을 설치하면 설계도와 동일한 미로를 만들 수 있다. www.acmicpc.net Level: Gold V Solved By: BFS, Implementation 구현이 꽤 어려운 문제였습니다. 아이디어는 꽤 직관적입니다. BFS를 통해 현재 좌표값에서 조명을 켤 수 있는가, 없는가를 알아냅니다. 켤 수 있다면, check 2차원 배열을 통해 조명으로 비춘 지역들을 check 해주었습니다. 그리고, 켤 수 없는 경우에는 이미 BFS를 진행하는 동안 좌표값들을 여러 개 방문 체크를 했었는데 어떻게 해야 할지 고민했습니다. ..

https://www.acmicpc.net/problem/26123 26123번: 외계 침략자 윤이 외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 $N$개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 $i$번째 건물의 높이는 $h_i$이다. 윤이는 울산을 파괴하기 위해 www.acmicpc.net Level: Silver IV Solved By: Priority Queue, Prefix Sum h값들을 받으면서 MaxHeap(Priority Queue)에 넣어줬습니다. 이유는 레이저를 쏘며 높이를 깎아가는 데에 있어 h-1이 다음 레이저를 쏠 때 높이이기 때문에 높이를 깎는 과정에서도 다음 높이(다음 최댓값)를 알기 위해 우선순위 큐를 사용했습니다. 즉, 우선순위 큐는 현재 깎..

https://www.acmicpc.net/problem/26122 26122번: 가장 긴 막대 자석 막대 자석 문자열은 문자 N과 S로만 구성되면서 다음과 같은 조건을 만족하는 문자열이다: 막대 자석 문자열에 등장하는 N의 개수와 S의 개수는 동일하며, 문자열의 앞쪽 절반을 구성하는 문자는 www.acmicpc.net Level: Silver V Solved By: Stack, Implementation 확실히 다른 분들의 풀이를 보니 더 깔끔한 풀이들이 존재합니다. 스택을 사용할 필요도 없었던 거죠. 급한 마음을 다루는 연습이 필요하다고 생각합니다. 풀이는 이렇습니다. 문자열을 for문을 통해 탐색하면서 해당 문자에 대한 스택에 1을 담아줍니다. 그리고, 진행을 하면서 앞 전 문자와 다르다면 스택의 ..

https://www.acmicpc.net/contest/view/914 4th UNIST Algorithm Programming Contest Uni-CODE 2022 Open Contest 사용 가능한 언어 C++17 C11 PyPy3 Java 11 www.acmicpc.net 1년 만에 나가본 CP였습니다. 진짜로 1년이더군요. 경북대 대회 후기 대회가 끝난 직후에 쓰는 거라 풀었던 문제 2개는 나중에 업로드하겠습니다. 이번 대회는 UNIST에서 개최한 대회였습니다. 사실 CP를 그리 선호하는 편은 아니었습니다. '문제를 푸는 데에 있어서 왜 급하게 풀어야 할까?'같은 생각이 있어서 1년 전에 한 번 참여한 이후로는 CP에 참여하지 않았었습니다. 그러다가 참여를 안 하다 보니 실력을 한 번 확인해봐..