본문 바로가기

Problem Solving

 (25)
16236 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기 상어가 물고기를 먹을 때마다 새롭게 BFS를 수행하면 된다. 조건만 빠뜨리지 않고 처리한다면 무난히 풀 수 있는 문제이다. 더보기 #include #include #include #include #include using namespace std; using mypair = pair; int n; int baby_shark = 2; int space[20][20]; int visited[20][20]; int cnt; int min_dist; mypa..
1005 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net DP라기 보다는 위상 정렬에 더 무게를 둔 문제이다. 각 건물의 선행 건물들과 선행 건물의 수를 그 건물에 대응되는 배열의 위치에 저장한 후 큐를 이용하여 건물들을 짓는 것에 조건을 만족하며 소요되는 최소 시간을 계산하는 방식으로 해결하였다. 더보기 더보기 #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullpt..
2134 Minimum Swaps to Group All 1's Together II Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Weekly Contest 275에 위치한 4점짜리 문제이다. 이 문제는 Medium 난이도답게 어렵게 생각할 필요 없이 직관적으로 두 단계를 거치면 해결할 수 있는 문제이다. 1. 배열에서 '1'의 개수 세기 2. 배열을 순회하며 각 지점에서 1이 연속적으로 위치하려면 얼마나 swap이 필요한지 세기 2번 단계의 경우 단순한 브루트 포스 방식으로 해결하면 시간이 오래 걸릴 수도 있지만 ..
17142 연구소3 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이번 문제는 간단히 정리하면 M개 이상 10개 이하의 임의의 지점을 선택해서 탐색을 진행했을 때에 모든 방을 탐색하는 것에 소요되는 최소 시간을 구하는 문제이다. 먼저 탐색 공간의 크기가 최대 50 X 50이고 바이러스는 최대 10개이기에 전역 탐색을 진행해도 빠르게 끝낼 수 있다고 판단되어 next_permutation 함수를 사용해서 바이러스를 활성화하는 모든 경우의 수를 탐색하였다. 그리고 활성화 바이러스는 인접한 지역으로 동시에 퍼지므로 사용한 알고리즘은 BFS를 ..
55 Jump Game Jump Game - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 배열의 i번째 위치에 도달할 수 있다면 i 이전의 모든 위치를 지날 수 있다는 점을 이용하면 간단하게 풀 수 있다. 솔직히 그냥 위 생각만 가지고 의식의 흐름으로 대충 풀었을 때 그냥 풀리는 수준의 난이도라 개인적으로 왜 Easy가 아니고 Medium인지 이해가 안 되는 문제였다. 더보기 더보기 class Solution { public: vector check; vector vec; bool ..
14476 최대공약수 하나 빼기 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 최대공약수를 구하는 것에 사용되는 유클리드 호제법에는 결합 법칙이 적용된다. 예를 들어 GCD(4,18, 14)의 결과는 GCD(GCD(4,18), 14)의 결과와 같다. 그리고 이 문제와 같이 배열에서 하나의 수를 제거했을 때의 최대공약수는 위 사실을 이용하면 간단히 해결할 수 있다. a b c d e f a gcd(a,b) gcd(a,b,c) gcd(a,b,c,d) gcd(a,b,c,d,e) gcd(a,b,c,d,e,f) gcd(a,b,c,d,e,f) gcd(b,c,d,..
1723 Find Minimum Time to Finish All Jobs https://leetcode.com/contest/weekly-contest-223/problems/find-minimum-time-to-finish-all-jobs/ 처음에 비트맵에 DP로 풀었다가 C++은 아슬아슬하긴 해도 통과하지만, 파이썬은 바로 시간 초과 나길래 그냥 Discussion에서 훌륭한 풀이를 가져왔다. https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/discuss/1042898/Most-performant-C%2B%2B-so-far-beats-100-runtime-99-memory C++ 더보기 class Solution { public: int minimumTimeRequired(vector& inputJob..
1722 Minimize Hamming Distance After Swap Operations source를 조합해서 만드는 배열들과의 target 사이의 Hamming Distance들 중, 최솟값을 찾는 문제이다. 얼마나 Swap 연산을 수행하던지 상관없기에 source의 각 위치에서 DFS를 통해 target에서 가능한 모든 부분을 방문하고, 방문하지 못한 위치들의 수가 Minimum Hamming Distance가 된다. 그리고 이 문제에서는 target의 원소가 중복될 수 있으므로 방문 여부를 확인할 때 인덱스를 이용했으며, Hamming Distance를 구할 때에는 Unordered map을 이용했다. 여담이지만, 이거 난이도가 왜 Medium인지 모르겠다. 보통 DFS 문제처럼 직관적으로 풀리면 모르겠는데, 그것도 아니고 중복되는 원소도 있고 Hard가 적당한거 같은데 Discuss..
728x90

티스토리툴바