본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 20310 타노스 문제 해결 Counter 함수를 통해 각각 몇 개씩 있는지 쉽게 알 수 있다. 문자열 처음부터 보면서 '0'은 Counter의 절반이 될 때 까지 만나면 정답 문자열에 넣는다. 문자열 처음부터 보면서 '1'은 Counter의 절반이 될 때 까지 만나면 패스한다. 문자열 처음부터 보면서 '1'은 Counter의 절반이 넘어가고 나서 만나면 정답 문자열에 넣는다. CODE import sys import math from collections import Counter input = sys.stdin.readline n = list(str(input()).strip()) X = Counter(n) a = X['0']//2 b = X['1']//2 answer = '' for i in range(len(n)).. 2023. 12. 23.
[python] 백준 2638 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 해결 전형적으로 그래프 안에서 이동해서 모두 공기가 되는데 까지 걸리는 시간이므로 bfs를 사용하는 것이 좋을 것이다. 그런데 문제는 치즈를 중심으로 보는 것이 아니라 공기를 중심으로 언제 녹는 벽(치즈)가 다 없어지는지 확인하는 문제이다. 따라서 While 반복문을 통해 시간을 측정하면서 언제 장애물을 안만나는지 확인하면 되는문제 BFS로 공기를 이동시키면서 어느 치즈지역이 공.. 2023. 12. 21.
[python] 백준 13904 과제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 해결 어떻게 일을 먼저 계획할 것인지 순서를 정하는 문제 당연히 점수가 높은 일을 먼저 계획을 해야한다.(중요하기 때문) 그다음 고려할 것은 가능하면 빨리 해결해야하는 문제이다. 따라서 힙(heap)을 사용할 것이다. 그리고 가능하면 마감기간에 처리를 하여 비록 비중이 적지만 빨리 처리해야하는 것도 처리할 수 있도록 한다. CODE import sys input = sys.stdin.readline import heapq def sol.. 2023. 12. 14.
[python] 백준 10835 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 문제 해결 사실 처음에 DFS를 이용해서 완전탐색을 하면 쉽게 풀 수 있겠다 싶었다. 하지만 DFS의 시간복잡도는 $O(2^{N})$ 이며 1≤$N$≤2,000이기 때문에 매우 복잡해질 수 있었고 시간초과로 부분점수밖에 얻지 못했다. 사실 숫자가 크고 완전탐색이 필요한 경우는 대부분 DP로 푸는 경우였다. 우선 왼쪽 카드 중 가장 큰 수가 오른쪽 카드 중 가장 큰 수보다.. 2023. 12. 13.
728x90