Programming

그리디 개념 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기 다양한 알고리즘에 두루 사용 # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 빈출유형 거스름돈 문제 거슬러 줘야 할 동전의 최소 개수 찾는 문제 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업 1이 될 때까지 N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산 최대한 많이 나누기가 문제 해결 아이디어 문제 해설 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 겨우 계산 모두 0으로 만드는 경우 모두 1로 만드는 경우 풀이 data = inp..

그리디 개념 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기 다양한 알고리즘에 두루 사용 # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 빈출유형 거스름돈 문제 거슬러 줘야 할 동전의 최소 개수 찾는 문제 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업 1이 될 때까지 N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산 최대한 많이 나누기가 문제 해결 아이디어 문제 해설 일반적으로 특정 두 수의 연산에서 '+'보다는 'x'가 더 값 크게 만듦 단, 0인 경우에는 '+' 연산이 효율적 즉, 두 수에 대하여 연산을 수행할 때, 두 수 ..

그리디 개념 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기 다양한 알고리즘에 두루 사용 # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 빈출유형 거스름돈 문제 거슬러 줘야 할 동전의 최소 개수 찾는 문제 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업 1이 될 때까지 N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산 최대한 많이 나누기가 문제 해결 아이디어 문제 해설 공포도가 가장 낮은 모험가부터 하나씩 확인 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 이를 그룹으로 설정 공포도가 오름차순으로..

위상 정렬 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 정렬 알고리즘의 일종 ex) 선수과목을 고려한 학습 순서 설정 * 진입차수(Indegree) : 특정한 노드로 '들어노는' 간선의 개수 문제 해설 위상 정렬 알고리즘 응용문제 각 노드(강의)에 대하여 인접 노드를 확인 더 오랜 시간이 걸리는 경우 시간 값 저장 & 결과 테이블 갱신 풀이 * 리스트의 값을 복제해야 할 때는 deepcopy( )함수 활용 from collections import deque import copy # 노드의 개수 입력받기 v = int(input()) # 모든 노드에 대한 진입차수는 0으로 초기화 indeg..

크루스칼 알고리즘 가장 적은 비용으로 모든 노드 연결 그리디 알고리즘 최소 신장 트리 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리 찾는 알고리즘 - 대표적으로 크루스칼 알고리즘 - ex) N개의 도시에서 전체 도시가 연결될 수 있게 도로 설치하는 경우 문제 해설 전체 그래프에서 2개의 최소 신장 트리 만드는 문제 최소 신장 트리를 찾은 후 가장 큰 간선을 제거하면 됨 풀이 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 녿를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 ..

서로소 집합 자료구조 서로소 집합정보(합집합 연산)가 주어졌을 때, 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘 union-find(합치기 찾기) 자료구조라고도 불림 두 집합이 서로소 관계인지 확인할 수 있다 = 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다 문제 해설 전형적인 서로소 집합 알고리즘 문제 N, M의 범위가 모두 최대 100,000이므로, 경로 압축 방식의 서로소 집합 자료구조 사용 풀이 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) r..