본문 바로가기

코딩 테스트/탐색7

[백준 2110번] 공유기 설치 문제 풀이 (with Python) 이분 탐색을 이용하면 간단하게 풀린다. 거리를 이분 탐색의 변수로 놓는다는 생각이 새로운 문제였다. 공유기는 같은 집에 있을 수 없으므로, start = 1, end = 가장 먼 집의 거리로 놓고, 가운데를 mid로 놓아 mid 거리만큼에 공유기를 설치했을 때 설치되는 공유기의 개수와 C를 비교해서 start나 end의 크기를 바꾸어 주었다. import sys input = sys.stdin.readline arr = [] N, C = map(int, input().split()) for i in range(N): arr.append(int(input())) arr.sort() start = 1 # 두 공유기 사이의 거리 최소값 end = arr[-1.. 2023. 11. 10.
[백준 1027번] 고층 건물 문제 풀이 이 문제를 풀기 위해서는 i 번째 건물에서 (N-1)개의 건물들과 기울기를 구해서 비교해야 한다. 이때, i 번째 빌딩을 기준으로 왼쪽에 있는 경우, 가까운 건물들의 기울기 보다 작으면 보이고, i 번째 빌딩을 기준으로 오른쪽에 있는 경우, 가까운 건물들보다 기울키가 크면 보인다. 따라서, 가까운 빌딩들부터 순서대로 기울기를 구하고, 왼쪽의 경우 더 작은 기울기가 있으면 +1, 오른쪽의 경우 더 큰 기울기가 있으면 +1 해준다. N = int(input()) building = list(map(int, input().split())) INF = int(1e10) def angle(i, h1, j, h2): return (h2-h1)/(j-i) count.. 2023. 11. 5.
[백준 12919번] A와 B 2 문제 풀이 처음에는 s에서 t가 될 수 있는 지를 확인했다. from collections import deque s = input() t = input() def first_way(s): return s+'A' def second_way(s): s += 'B' s = ''.join(reversed(s)) return s def rotate(s): s = ''.join(reversed(s)) return s queue = deque() queue.append(s) for s in queue: # 현재의 s나 뒤집은 s가 t에 없으면 만들 수 없으므로 0출력 queue.pop() while len(s) < len(t): if first_way(s) in t: s = firs.. 2023. 11. 4.
[백준 1107번] 리모컨 문제 풀이 앞자리수 부터 해당 숫자가 있으면 해당 숫자를, 없으면 +1, -1의 값을 저장해서 모든 경우의 수를 최솟값으로 비교하려니 코드가 너무 복잡하고 길어졌다. 이 문제는 단순하게 for 문으로 가능한 모든 값을 하나씩 비교해서 최솟값을 구하도록 단순하게 생각해야했다. 이떄, 채널 0에서 -를 누른 경우에는 채널이 변하지 않지만, 채널은 무한대 만큼 있다는 조건이 있으므로, 채널을 밑으로 내려오는 경우를 고려해 채널 수인 50000의 2배인 100000까지 비교해야 한다. ++) 추가 for i in str(500): print(i) 위의 코드 결과값은 5 0 0 이 나온다. 각 자리수를 비교할 때 정말 유용할 것 같다👍👍 N = int(input()) M .. 2023. 9. 10.

티스토리툴바