DevLog

알고리즘/기술면접 완전 정복 올인원 패키지 Online 백트래킹 - N Queen 문제 이해 백트래킹 - N Queen 문제 파이썬 코드 작성 - 1 백트래킹 - N Queen 문제 파이썬 코드 작성 - 2 자료구조와 알고리즘 정리 - 필수 자료구조와 알고리즘 정리 길고 길었던 알고리즘 이론 부분의 마지막까지 왔다. 이제 강의의 절반 정도 학습한 것 같은데, 이제 챌린지도 막바지에 다달았다. 3개월동안 잘 할 수 있을까 스스로 의심도 하고, 포기도 생각할 때도 있었는데, 여기까지 왔다니 분명 스스로 더 성장했기를 바래본다. 백 트래킹 (backtracking) 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfactio..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 2 - 참고_개선된 프림 알고리즘 최소 신장 트리의 이해 2 - 개선된 프림 알고리즘의 시간 복잡도 백트래킹 - 백트래킹 기법의 이해 시간 복잡도 최악의 경우, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하므로 O(𝐸𝑙𝑜𝑔𝐸ElogE) 시간 복잡도를 가짐 개선된 프림 알고리즘 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식 초기화 - 정점:key 구조를 만들어놓고, 특정 정점의 key값은 0, 이외의 정점들의 key값은 무한대로 놓음. 모든 정점:key 값은 우선순위 큐에 넣음 가장 key값이 적은 정점:key를 추출한 후(pop 하므로 해당 정점:key 정보는 우선순위 큐에서 삭제됨), (e..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 2 - 프림 알고리즘이란 최소 신장 트리의 이해 2 - 프림 알고리즘 코드 작성 최소 신장 트리의 이해 2 - 프림 알고리즘 파이썬 코드 - 1 최소 신장 트리의 이해 2 - 프림 알고리즘 파이썬 코드 - 2 프림 알고리즘 (Prim's algorithm) 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 1 - Union_Find 알고리즘 최소 신장 트리의 이해 1 - 크루스칼 알고리즘 코드 작성 - 1. Path 최소 신장 트리의 이해 1 - 크루스칼 알고리즘 코드 작성 - 2. Union_by_rank union-by-rank 기법 각 트리에 대해 높이(rank)를 기억해 두고, Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함) 높이가 h - 1 인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시켜주고, 다른 쪽의 트리를 해당 트리에 붙여줌 초기화시, 모든 원소는 높이(rank) 가 0 인 개별 집..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 1 - 신장 트리와 최소 신장 트리 이해 최소 신장 트리의 이해 1 - 크루스칼 알고리즘 (Kruskal's Algorithm) 최소 신장 트리의 이해 1 - Kruskal 알고리즘과 Union_find 알고리즘의 차이 신장 트리 란? Spanning Tree, 또는 신장 트리라고 불림 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 최소 신장 트리 Minimum Spanning Tree, MST 라고 불림 가능한 S..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 그래프 고급 탐색 알고리즘 - 최단 경로 알고리즘 이해 - 2 그래프 고급 탐색 알고리즘 - 최단 경로 알고리즘 이해 - 3 그래프 고급 탐색 알고리즘 - 다익스트라 알고리즘 파이썬 구현 - 1 그래프 고급 탐색 알고리즘 - 다익스트라 알고리즘 파이썬 구현 - 2 강의 제목부터도 어려웠던 강의. 벌써 10주 차이고, 5월 15일까지 환급 챌린지를 하게 되는데, 시간이 굉장히 빠르면서도 얼마 남지 않은 게 믿기지 않기도 하다. 강의 수가 꽤 많아서 아직 절반 정도밖에 못한 것 같아서 마음이 급해지기도 한다. (꼭 강의를 끝내라는 규칙은 없었지만 스스로의 조급) 최단 경로 문제란? 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 가중치 ..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 탐욕 알고리즘 - 01. 탐욕 알고리즘의 이해 탐욕 알고리즘 - 02. 탐욕 알고리즘 예제와 실습 그래프 고급 탐색 알고리즘 - 최단 경로 알고리즘 이해 - 1 탐욕 알고리즘 이란? Greedy algorithm 또는 탐욕 알고리즘이라고 불림 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 탐욕 알고리즘 예 문제 1: 동전 문제 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 그래프 기본 탐색 알고리즘 - 01. 너비 우선 탐색(BFS) - 1 그래프 기본 탐색 알고리즘 - 02. 너비 우선 탐색(BFS) - 2 그래프 기본 탐색 알고리즘 - 03. 너비 우선 탐색(BFS) - 3 그래프 기본 탐색 알고리즘 - 04. 깊이 우선 탐색(DFS) BFS와 DFS 란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식: A - B - C - D - G - H - I - E - F..