본문 바로가기

Algorithm/프로그래머스 고득점 Kit11

[프로그래머스] 고득점Kit (10) - 그래프 (파이썬) 1. 가장 먼 노드 (Lv. 3) # 가장 먼 노드 import sys MAX = sys.maxsize def solution(n, edge): arr = [[] for _ in range(n+1)] for x, y in edge: arr[x].append(y) arr[y].append(x) return go(n, arr) def go(n, arr): visited = [MAX] * (n+1) visited[0], visited[1] = 0, 1 q = [] q.append(1) while q: node = q.pop() for nnode in arr[node]: if visited[nnode] > visited[node] + 1: q.append(nnode) visited[nnode] = visited.. 2022. 3. 13.
[프로그래머스] 고득점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.
[프로그래머스] 고득점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.
[프로그래머스] 고득점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.
[프로그래머스] 고득점Kit (6) - 그리디(2) (파이썬) 1. 구명보트 (Lv. 2) # 구명보트 def solution(people, limit): people.sort(reverse=True) answer = 0 i = 0 j = len(people) - 1 while i 2022. 3. 9.
[프로그래머스] 고득점Kit (6) - 그리디(1) (파이썬) 1. 체육복 (Lv. 1) # 체육복 def solution(n, lost, reserve): lost = set(lost) reserve = set(reserve) answer = 0 for x in (lost-reserve): if x-1 in (reserve-lost): reserve.remove(x-1) continue elif x+1 in (reserve-lost): reserve.remove(x+1) continue answer += 1 return n - answer 집합의 성질을 이용했다. (차집합 이용) 체육복을 잃어버린 인원 중, 여벌 체육복이 없는 인원들(lost - reserve)을 for문으로 돌면서 앞이나 뒤의 사람이 여벌 체육복을 가지고 왔으면서 체육복을 잃어버리지 않은 집합(.. 2022. 3. 5.
[프로그래머스] 고득점Kit (5) - 완전탐색 (파이썬) 1. 모의고사 (Lv. 1) # 모의고사 def solution(answers): answer = [] one = [1, 2, 3, 4, 5] two = [2, 1, 2, 3, 2, 4, 2, 5] thr = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] one = one*(len(answers)//len(one)) + one[:(len(answers) % len(one))] two = two*(len(answers)//len(two)) + two[:(len(answers) % len(two))] thr = thr*(len(answers)//len(thr)) + thr[:(len(answers) % len(thr))] result = [0, 0, 0] for i in range(len(answe.. 2022. 3. 4.

티스토리툴바