알고리즘(51)
-
프로그래머스 실패율 코드 및 해설 (파이썬)
https://programmers.co.kr/learn/courses/30/lessons/42889?language=python3 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 입력으로 받은 stages를 오름차순으로 정렬합니다. 이후 Counter를 이용해 각 스테이지별 빈도를 딕셔너리로 저장하고, 이 딕셔너리의 키를 하나씩 받으며 실패율을 계산합니다. 실패율은 (현재 키의 빈도수) / (지금까지 남아있는 사용자 수)입니다. 처음의 사용자 수는 stages의 길이로 초기화하고, 이후 사용자 수에서 현재 ..
2021.08.04 -
백준 안테나 코드 및 해설 (파이썬)
https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 집들의 위치를 houses라는 리스트에 저장하고 이를 오름차순으로 정렬합니다. 집들의 개수를 N으로 저장하고, 정중앙의 집인 N을 2로 나눈 몫번째 집에 안테나를 설치합니다. import sys # 집의 개수 N = int(sys.stdin.readline()) # 집의 위치 houses = list(map(int, sys.stdin.readline().split())) # 정렬 houses.sort() # 정중앙의 집..
2021.08.03 -
어두운 길 코드 및 해설 (파이썬)
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 43, p 397 크루스칼 알고리즘을 이용해 최소 비용의 신장 트리를 탐색했습니다. 최종 반환해야 할 답이 절약할 수 있는 최대 금액이므로, 전체 도로에 가로등을 설치하는데 드는 비용을 total_cost로 저장하고, 최소 신장 트리를 만들었을 때 가로등을 설치하는데 드는 비용을 min_cost로 저장하여 둘의 차를 반환했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 집의 수 N = inputs[0] parent = [0] * N for i in range(N): parent[i] = i # 도로의 수 M = inputs[1] # (도로의 길이, 도로..
2021.07.14 -
탑승구 코드 및 해설 (파이썬)
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 42, p 395 비행기를 '최대' 몇 대 도킹할 수 있는지 출력해야 하므로 이진 탐색을 이용해 풀이했습니다. 먼저 도킹할 수 있는 비행기의 최소 대수를 1대, 최대 대수를 게이트의 개수인 G대로 설정합니다. 이후 중간값을 계산하고, 이 중간값만큼의 비행기를 도킹할 수 있는지 확인합니다. 비행기를 순서대로 도킹한다고 했으므로, 중간값 개수만큼의 도킹 정보를 가져오고, 이를 dock라는 함수에 전달합니다. dock 함수는 도킹 정보 리스트를 받아 모든 비행기를 도킹할 수 있으면 True, 아니면 False를 반환하는 함수입니다. 이는 힙을 이용해 구현했는데, 파이썬의 heapq는 Min Heap이므로, Max Heap으로 사용하기 위해 각 el..
2021.07.13 -
여행 계획 코드 및 해설 (파이썬)
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 41, p 393 서로소 집합을 이용해 여행 계획 안에 있는 여행지들이 모두 같은 집합에 속하면 예행 계획이 가능한 것으로, 그렇지 않으면 불가능한 것으로 풀이했습니다. 연결된 도시들의 정보가 리스트가 아닌 행렬로 주어지므로 행렬의 값 중 0이 아니라 1인 부분의 좌표를 통해 연결된 도시들의 정보를 담은 리스트 links를 생성했습니다. 이를 이용해 서로소 집합 알고리즘을 수행하고, 계획에 있는 도시들이 속한 집합을 확인해 이들이 모두 같으면 YES, 아니면 NO를 출력했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 여행지의 수 N = inputs[0..
2021.07.12 -
그래프 이론
1. 개선된 서로소 집합 알고리즘 - 서로소 집합Disjoint Sets: 공통 원소가 없는 두 집합 - 서로소 집합 자료 구조 = union-find 자료구조 (1) 개선된 서로소 집합 알고리즘 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b]..
2021.07.12