본문 바로가기

Algorithm245

[프로그래머스] 고득점Kit (9) - 이분탐색 (파이썬) 1. 입국심사 (Lv. 3) # 입국심사 def solution(n, times): answer = 0 times.sort() left, right = 1, max(times)*n while left = n: answer = mid right = mid - 1 elif temp < n: left = mid + 1 return answer right = max(times)*n : 가장 긴시간으로 n명이 입국심사를 했을 때가 최댓값 이분탐색 실시 - mid : 걸린 총 시간 - temp : 해당 시간 안에 입국 심사를 할 수 있는 사람의 수 - temp == n 을 목표로 이분탐색을 진행 2. 징검다리 (Lv. 4) # 징검다리 def solution(distance, rocks, n): answer = 0.. 2022. 3. 12.
[백준] 19236번 - 청소년 상어 (파이썬) # 청소년 상어 import copy dx = [0, -1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 0, -1, -1, -1, 0, 1, 1, 1] arr = [] fish = [[0]] for k in range(4): temp = list(map(int, input().split())) arr.append([temp[i] for i in range(0, len(temp), 2)]) for i in range(0, len(temp), 2): fish.append([temp[i], [k, i//2, temp[i+1]]]) def fish_move(arr, fish): for i, temp in enumerate(fish): if i != 0: x, info = temp if not ea.. 2022. 3. 12.
[프로그래머스] 고득점Kit (8) - DFS/BFS (파이썬) 1. 타겟 넘버 (Lv. 2) # 타겟 넘버 def solution(numbers, target): answer = 0 def dfs(target, k, result): nonlocal answer if k == len(numbers): if target == result: answer += 1 return else: dfs(target, k+1, result+numbers[k]) dfs(target, k+1, result-numbers[k]) dfs(target, 0, 0) return answer 재귀 함수를 이용한 dfs로 풀었다. k == len(numbers) 일 경우, target과 같은지 확인 return answer 2. 네트워크 (Lv. 3) # 네트워크 from collections i.. 2022. 3. 11.
[백준] 10282번 - 해킹 (파이썬) # 해킹 import heapq import sys input = sys.stdin.readline def hacking(n, start): dist = [sys.maxsize] * (n+1) dist[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: time, computer = heapq.heappop(q) for ntime, ncom in arr[computer]: total = time + ntime if dist[ncom] > total: dist[ncom] = total heapq.heappush(q, (total, ncom)) result_time = 0 result_com = 0 for x in dist: if x != sys.maxsiz.. 2022. 3. 11.
[백준] 2473번 - 세 용액 (파이썬) # 세 용액 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) arr.sort() result = sys.maxsize three = [] for i in range(N-2): left = i+1 right = N-1 while left 0: right -= 1 else: break print(*th.. 2022. 3. 10.
[백준] 2470번 - 두 용액 (파이썬) # 두 용액 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) arr.sort() result = [] min_result = sys.maxsize sum = 0 left = 0 right = N-1 while left 0: right -= 1 else: break sum = 0 print(*result) 투포인터 1. 정.. 2022. 3. 10.
[프로그래머스] 고득점Kit (7) - 동적계획법 (파이썬) 1. N으로 표현 (Lv. 3) # N으로 표현 def solution(N, number): arr = [0] for i in range(1, 9): temp = make(i, N, arr) if number in temp: return i arr.append(temp) return -1 def make(i, N, arr): result = set() temp = int(str(N) * i) result.add(temp) for half in range(1, i//2+1): for x in arr[half]: for y in arr[i-half]: result.add(x+y) result.add(x-y) result.add(y-x) result.add(x*y) if y != 0: result.add(x/.. 2022. 3. 10.

티스토리툴바