직장인인강
패스트캠퍼스 챌린지 6일차
날짜 : 2021 년 11 월 6 일 시청 강의 : 프림 알고리즘 (1), 프림 알고리즘 (2) 오늘 시청한 강의는 프림 알고리즘이다. 내가 뭘들은건가싶다 주르륵.. 크루스칼은 이해가 좀 됬는데 역시 옛날부터 포기한 프림 알고리즘은 차원이 달랐다.. 일단 개념만 이해하고 코드는 나중에 이해하기로 결심했다. 크루스칼 vs 프림 알고리즘 1. 크루스칼 알고리즘 : 간선 정보를 정렬 -> 가장 가중치가 낮은 간선부터 사이클이 생기지 않도록 연결 2. 프림 알고리즘 : 시작 정점을 선택 -> 정점의 인접 간선 중 가중치가 최소인 간선을 연결 프림 알고리즘 https://www.cs.usfca.edu/~galles/visualization/Prim.html Prim MST Visualzation www.cs.us..
패스트캠퍼스 챌린지 5일차
날짜 : 2021 년 11 월 5 일 시청 강의 : 최소 신장 트리의 이해와 크루스칼 알고리즘 (1) ~ (4) 그래프 탐색 : 크루스칼과 프림 알고리즘은 최소 신장 트리를 활용하는 문제이다. 이중에서, 오늘은 크루스칼 알고리즘에 대해 배웠다. 신장 트리 (Spanning Tree) 전체 노드가 연결되어 있다. 사이클이 존재하지 않는다. 위 그래프에서, 그래프 G 는 사이클이 존재한다. 스패닝 트리는, 모든 노드가 연결되어있으면서 사이클이 존재하지 않는 그래프다 최소 신장 트리 가중치가 존재하는 신장 트리 중, 간선의 합(weight)이 가장 작은 트리 만약, 앞의 신장 트리가 다음과 같은 가중치를 가지고 있다고 가정해보자. 그렇다면, 최소 신장 트리는 가중치가 가장 작은 트리로 첫번째 스패닝 트리가 최..
패스트캠퍼스 챌린지 4일차
날짜 : 2021 년 11 월 4 일 시청 강의 : 최단 경로 알고리즘 이해 (1) , 최단 경로 알고리즘 이해 (2) , 최단 경로 알고리즘 이해 (3) , 최단 경로 - 다익스트라 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것 유형 1. 단일 출발 (다익스트라) 특정 노드 -> 모든 그래프 돌아다니면서 가장 짧은 경로 찾기 2. 단일 도착 모든 노드에서 출발 -> 특정 노드로 도착하는 가장 짧은 경로 3. 단일쌍 u~ V까지의 최소 경로 (1 개) 4. 전체쌍 모든 쌍에 대한 최단 경로 다익스트라 알고리즘 다익스트라 알고리즘은 우선 순위 큐를 사용한다 우선순위 큐를 활용하여 풀이하는 방식은 BFS 방식과 매우 유사한데, 이는 자식놔 연결된 노드를 체크하여 탐색하기 때문이다...
패스트캠퍼스 챌린지 3일차
날짜 : 2021 년 11 월 3 일 시청 강의 : 탐욕 알고리즘의 이해 (1) , 탐욕 알고리즘의 이해 (2) Greedy Algorithms 탐욕 알고리즘은 쉬운 문제는 정렬을 이용, 보통 DP를 사용하여 문제를 푸는 것 같다. 본 강의에 나온 예제는 누가봐도 정렬로 푸는 문제였지만 보통 탐욕 알고리즘은 코테에서 만났을 때 탐욕 기법으로 풀 것이라 상상도 못하는 것들이 많다고 하니 전형적인 유형들만 몇개 공부하면 될 것 같다. 문제 유형 : 1. 거스름돈 줄이기 손님이 지불한 금액에서 물건값을 제한 차액을 지불하는 문재. 동전을 최소한으로 주고 싶을 때 -> 주로, 500원 1000원이 아니라 400원 300원 이런식으로 나오기 때문에 정렬로 풀 수 없고 DP를 이용하여 풀어야한다 2. 설탕배달 ht..
패스트캠퍼스 챌린지 2일차
날짜 : 2021 년 11 월 2 일 시청 강의 : 그래프 이해와 자료 구조 , 너비 우선 탐색 (BFS) (1) , 너비 우선 탐색 (BFS) (2), 깊이 우선 탐색 (DFS) 그래프 기본 용어 그래프는 아이템들과 아이템 사이를 연결하는 관계를 표현한다 Vertex (정점) : 연결점 Edge (간선) : 연결 선 Degree (차수) : 정접에 연결된 간선 수 그래프는 vertex의 집합과 이들을 연결하는 edges의 집합으로 구성된 자료 유형 이미지 출처 : https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/tutorial/ 무향 그래프 (Undirected → 양방향) 유향 그래프(Directed) 가중치 그래..
패스트캠퍼스 챌린지 1일차
날짜 : 2021 년 11월 1 일 시청 강의 : 동적 계획법과 분할 정복, 병합 정렬 (1), 병합 정렬 (2) 동적 계획법과 분할 정복 동적 계획법 (DP) 입력 크기가 작은 부분을 해결하여 큰 문제 해결에 적용하는 방식 상향식 (sub problems -> main problem ) Memoization 기법 사용 Memoization 이란, 이전 값을 기억하여 runtime이나 memory 문제를 해결해준다. -> 백준 문제에서 유용하게 사용 분할 정복 (Divide and Conquer) 문제를 나눌 수 없을때까지 나누어 푼 후, 해답을 합친다 하향식 (main problem -> sub problems) DP vs 분할 정복 요약 DP 분할정복 common 문제를 쪼개어 (나누어) 풀이한다 D..