본문 바로가기
728x90

알고리즘316

[python] 백준 1939 중량제한 문제 해결 처음에 BFS를 이용해서 문제를 풀려했지만 메모리 초과가 났다. 그러면 que안에 적게 넣어서 통과하는지를 확인해야한다. 방법이 잘 안떠올라서 다른 풀이를 참고했고 이분 탐색을 이용해서 통과할 수 있는 최댓값이 나올때까지 계속 돌려보는 방법이 있었다. 처음에 최솟값 1 최댓값 1000000000을 잡은 후 mid = (low+high)//2를 잡고 mid가 통과하면 low를 한칸 올려주고 통과하지 못하면 high를 한칸 내려주며 계속 시도하는 방식이다. 이를 low 2024. 1. 29.
[python] 백준 1138 한 줄로 서기 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 문제 해결 insert를 이용해서 순서를 정할 수 있는 문제 왼쪽에 큰 사람 수를 알 수 있으므로 큰 사람부터 차례대로 배열을 해서 어디에 들어가야 하는지 insert를 이용해서 리스트에 넣을 수 있다. CODE import sys input = sys.stdin.readline from collections import deque def solution(): stack = [] for i.. 2024. 1. 11.
[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.
728x90