WannaBeDeveloper

13398번: 연속합 2 www.acmicpc.net 이 문제는 n개의 정수로 이루어진 임의의 수열에서 가장 큰 연속합을 구하는 문제이다. 단, 수열에서 수를 하나 제거할 수 있다. 우선 연속합을 구하는 방법을 생각해보자. 우선 N개의 정수로 이루어진 수열에서 N-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열로 나눈다. 그리고 N-1개의 정수로 이루어진 수열에서 구한 연속합의 최댓값을 구했다고 가정하자. 이때 1개의 정수로 이루어진 수열에서 연속합의 최댓값은 그 정수와 같다. 여기까지 하면 N-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열의 연속합의 최댓값을 구한 상태로, 여기에다가 N-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열에 걸쳐있는 연속합의 최댓값까지 고려..

2169번: 로봇 조종하기 www.acmicpc.net 이 문제는 N*M 크기의 지형에서 로봇을 왼쪽 위에서 오른쪽 아래로 보낼 때 탐사한 지역들의 가치의 합의 최댓값을 구하는 문제이다. 단, 로봇은 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있고, 한 번 탐사한 지역은 다시 탐사할 수 없다. 만약 로봇이 오른쪽, 아래쪽으로만 이동 가능했다면 어떤 경로로 이동해도 한 번 탐사한 지역은 다시 탐사할 수 없어 문제가 되지 않지만, 이 문제는 로봇이 왼쪽으로도 이동 가능하기 때문에 한 지역을 여러 번 방문할 가능성이 생긴다. 그래서 이 문제는 특별히 한 번 탐사한 지역을 다시 탐사할 수 없다는 조건이 붙는다. 로봇의 이동 경로를 예상한다면 위쪽으로는 이동이 불가능하기 때문에 결국 기껏해야 지그재그 형태의 경로로 이..

2056번: 작업 www.acmicpc.net 이 문제는 수행해야 할 작업과 각 작업마다 걸리는 시간이 주어질 때 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제이다. 단, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다. 이 문제는 이전의 ACM Craft 문제와 유사한 문제이나, 목표 정점에 도달하는데 걸리는 시간을 구하는 ACM Craft 문제와 달리, 모든 작업을 끝내는데 걸리는 시간을 구한다는 점에서 약간의 차이가 있다. 나머지는 ACM Craft 문제와 거의 같다. 백준 1005번 : ACM Craft in Python 1005번: ACM Craft www.acmicpc.net 이 문제는 위상 정렬 문제를 좀더 발전시킨 문제로, 위상 정렬을 통한 그래프 탐색에서 목표 정점까지 ..

1092번: 배 www.acmicpc.net 이 문제는 무게 제한이 서로 다른 N개의 크레인이 무게가 서로 다른 M개의 박스를 배에 싣는데 걸리는 최소 시간을 구하는 문제이다. 이를 해결하기 위해서는 되도록이면 각 크레인이 자기 자신의 무게 제한에 최대한 가까운 박스를 옮기도록 해야 한다. 왜냐하면 무게 제한에 가까운 박스부터 먼저 옮겨야 나중에 남은 박스는 무게가 작은 것만 남아 거의 모든 크레인이 옮길 수 있어 시간을 절약할 수 있기 때문이다. 그러므로 주어진 크레인의 무게 제한과 각 박스의 무게를 내림차순으로 정렬한다. 그리고 단위 시간마다 무게 제한이 큰 크레인부터 옮길 박스를 할당하는데, 이때 무게가 무거운 박스부터 살펴보면서 무게 제한보다 작은 박스가 나오면 해당 크레인에 박스를 할당한 뒤 다..

13904번: 과제 www.acmicpc.net 이 문제는 각 과제의 점수와 마감 기한이 주어질 때 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 단, 과제는 하루에 하나씩만 끝낼 수 있다. 각 과제는 마감 기한이 다를 뿐이지 각 과제를 해결하는데 걸리는 시간은 모두 하루로 동일하므로 되도록이면 점수가 높은 과제를 해결하는 것이 좋을 것이다. 단, 마감 기한이 짧은 과제도 충분히 고려할 수 있도록 마감 기한이 긴 과제는 되도록 나중에 해결해야 한다. 이를 코드로 구현하기 위해, 우선 min-heap을 만들고 여기에 N개의 input을 넣는데, 만약 마감 기한 d와 점수 w가 주어지면 [-w, -d]를 heap에 넣는다. 즉, 과제의 점수가 큰 순서대로, 만약 점수가 같은 경우에는 과제의 마감 기한이 늦..

16234번: 인구 이동 www.acmicpc.net 이 문제는 각 나라의 인구수가 주어졌을 때 인구 이동이 몇 번 발생하는지 구하는 문제이다. 인구 이동의 조건은 위와 같다. 이 문제를 해결하기 위해서는 대략적으로 다음과 같은 과정을 거쳐야 한다. 우선 각 나라에 대해 그 나라를 포함하는 나라들의 연합을 만들고, 연합 내 모든 국가들의 인구 수를 모든 국가들의 인구 수의 평균으로 바꿔야 한다. 이를 방문하지 않은 모든 나라에 대해 수행하고 만약 인구 이동이 발생하지 않은 경우 위 과정을 끝내고, 인구 이동이 발생한 경우 다시 위 과정을 반복한다. 좀 더 구체적으로 위 과정을 구현하자. 우선 특정 나라의 위치가 주어질 때 그 나라를 포함하는 연합을 구하고 연합 내 나라들의 인구 수를 바꾸는 함수 BFS를..

16194번: 카드 구매하기 2 www.acmicpc.net 이 문제는 카드 i개(1

1316번: 그룹 단어 체커 www.acmicpc.net 이 문제는 주어진 단어 중 그룹 단어의 개수를 구하는 문제이다. 이때 그룹 단어란 단어에 존재하는 모든 문자에 대해서 각 문자가 연속해서 나타나는 경우만을 말한다. 이를 해결하기 위해서는 문자열의 각 문자마다 그 문자 a와 문자의 오른쪽에 이웃한 문자 b를 비교해 두 문자가 서로 다른 경우 a 뒤에 문자 a가 나오는지를 검사하면 된다. 만약 문자 a가 나오는 경우 해당 문자열은 그룹 단어가 될 수 없다. 이를 코드로 구현하면 다음과 같다. T = int(input()) cnt = 0 for _ in range(T): s = input() res = True for idx in range(0, len(s)-1): c = s[idx] if s[idx]..

9012번: 괄호 www.acmicpc.net 이 문제는 "("와 ")"로만 이루어진 문자열인 괄호 문자열이 주어질 때 괄호의 모양이 바르게 구성되었는지를 확인하는 문제이다. 괄호 문자열은 "("이 나올 경우 이에 대응하는 ")"가 반드시 나와야 한다. 이를 제대로 구현하기 위해서는 스택을 이용하면 된다. 문자열의 각 문자에 대해 순회하면서 만약 문자가 "("라면 스택에 넣고, ")"라면 스택의 맨 위에 있는 문자 "("를 제거한다. 이때 만약 스택이 비어있으면 ")"와 대응하는 "("가 없다는 뜻이므로 "NO"를 출력한다. 또한 이러한 과정을 모두 거쳤을 때 스택에 문자가 남아있다면, 스택에 남아있는 "("에 대응하는 ")"가 없다는 뜻이므로 "NO"를 출력한다. 만약 두 경우 모두 아닌 경우에는 모든..

1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net 이 문제는 친구 관계가 주어졌을 때 케빈 베이컨의 수가 가장 적은 사람을 구하는 문제이다. 이떄 어떤 사람의 케빈 베이컨의 수란 각 사람마다 몇 명의 친구를 거쳐야 도달할 수 있는지를 구한 뒤 이를 모두 더한 결과이다. 겉으로 보기에는 복잡해 보이지만, 사실 각 사람마다 BFS를 이용해 다른 사람과의 거리를 구하고, 이를 모두 더하면 케빈 베이컨 수를 구할 수 있다. 그러므로 BFS를 모든 사람에 대해 적용한 뒤 케빈 베이컨 수를 구하고 케빈 베이컨 수가 최소가 되는 사람을 구하면 된다. 이를 코드로 구현하면 다음과 같다. import sys from collections import deque N, M = map(int, input()..