😎 공부하는 징징알파카는 처음이지?

220213 작성 https://www.youtube.com/watch?v=Mw8W56qNL8U&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=34 1. 서로소 집합을 활용한 사이클 판별 : 무방향 그래프 내에서의 사이클 판별 ( 방향 그래프에서의 사이클 여부는 DFS 를 이용하여 판별 ) : 사이클 판별 알고리즘 1) 각 간선을 하나씩 확인하며 두 노드의 루트 노드 확인 - 루트 노드가 서로 다르다면 두 노드에 대한 합집합 수행 - 루트 노드가 서로 같다면 사이클 발생! 2) 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복 python # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 ..

220213 작성 https://www.youtube.com/watch?v=Ha0w2dJa2Nk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=33 1. 서로소 집합 (Disjoint Sets)SS : 공통 원소가 없는 두 집합 2. 서로소 집합 자료 구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 -> 합집합 (union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 -> 찾기 (find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 : 합치기 찾기 자료구조라 불린다 1) 합집합 연산 확인, 서로 연결된 노드 A, B 확인 - A와 B의 루트 노드 A', B' 각각 찾기 - A'를 B'의 부모 노드로 설..

220213 작성 https://www.youtube.com/watch?v=liuUazQaLuU&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=32 전보 : N 개의 도시가 있다 : 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C 에서 보낸 메시지를 받게 되는 도시의 개수는 몇개, 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인가 : 한 도시에서 다른 도시까지의 최단 거리 문제로 치환 : 우선순위 큐(HEAP)를 이용한 다익스트라 알고리즘 python import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수,..

220212 작성 https://www.youtube.com/watch?v=hw-SvAR3Zqg&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=31 1. 플로이드 워셜 알고리즘 : 모든 노드에서 다른 모든 노드까지의 최단 경로 모두 계산 : 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행 ( 최단 거리 갖는 노드 찾기는 필요 X ) : 2차원 테이블에 최단 거리 정보 저장 : 다이나믹 프로그래밍 유형에 속한다 : 각 단계마다 특정한 노드 K 를 거쳐 가는 경우를 확인 ( a 에서 b 로 가는 최단 거리보다 a 에서 k 를 거쳐 b 로 가는 거리가 더 짧은지 검사 ) 1) 최단 거리 초기화 2) k 노드 거쳐 가는 경우를 고려하며 테이블 갱신 python INF = i..

220212 작성 https://www.youtube.com/watch?v=F-tkqjUiik0&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=30 1. 최단 경로 문제 : 가장 짧은 경로를 찾는 알고리즘 - 한 지점에서 다른 한 지점의 최단 경로 - 한 지점에서 다른 모든 지점의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로 : 각 지점은 그래프에서 노드로 표현 : 지점간 연결된 선은 그래프에서 간선으로 표현 2. 다익스트라 최단 경로 : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 : 음의 간선이 없을 때 정상적으로 동작 ( 현실세계 도로는 음의 간선으로 표현되지 x ) : 그리디 알고리즘으로 분류 ( 매 상황에서 가장 비용이 적은..

220211 작성 https://www.youtube.com/watch?v=tWX6FZwwQMI&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=29 개미전사 : 최소한 한 칸 이상 떨어진 식량창고를 약탈하자! : 인접한 식량창고 공격받으면 들킨다 : 식량창고 N개에 대한 정보가 주어졌을 때, 얻을 수 있는 식량의 최대값 구하기 1) a(i) = i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최대값) 2) k(i) = i번쨰 식량창고에 있는 식량의 양 python # 정수 N을 입력 받기 n = int(input()) # 모든 식량 정보 입력 받기 array = list(map(int, input().split())) # 앞서 계산된 결과를 저장하..

220209 작성 https://www.youtube.com/watch?v=rWbjQphRE9A&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=28 1. 다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 : 이미 계산된 결과 (작은 문제)는 별도의 메모리 영역에 저장 (다시 계산 X) : 두 가지 탑다운(위에서 아래, 하향식 ), 보텀업(아래에서 위, 상향식)으로 구성 : 동적 계획법 : 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 => 다이나믹은 별다른 의미 없이 사용 1. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답..

220209 작성 https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27 1. 파라메트릭 서치 (Parametric Search) : 최적화 문제를 결정 문제 (예 or 아니오) 로 바꾸어 해결 ( 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 ) 떡볶이 떡 만들기 : 절단기에 높이(H) 를 지정하면, 줄지어진 떡을 한 번에 절단 : 높이가 H 보다 긴 떡은 H 위의 부분이 잘리고, 낮은 떡은 잘리지 않음 : 손님은 잘린 떡 길이를 가져감 : 손님이 요청한 총 길이가 M 일 때, 적어도 M만큼의 떡을 얻기 위해, 절단기에 설정할 수 있는 높이의 최댓값 - 적절한..