KoreanFoodie's Study

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. Floyd-Warshall (플로이드 와샬 - 최단거리 쌍) 플로이드 와샬(Floyd-Warshall) 알고리즘은 주어진 그래프의 모든 정점들에 대한 최소거리를 구하는 알고리즘이다. 원리는 매우 간단한데, 시작지점 i, 도착지점 j 의 거리 쌍을 중간 경유지 k 를 지나는 모든 경우에 대해 계속 relaxation 해주면 된다. 따라서 시간 복잡도는 (O^3) 이 나오게 된다. #include #include #define V 4 #define INF1000000 i..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 다익스트라 (최단 경로 알고리즘) 다익스트라는 주어진 시작 지점에서 최단경로를 구하는 알고리즘으로, 양의 가중치 간선들로 이루어진 그래프일 경우에 한 지점에서 특정 지점까지의 최단경로를 구하는 알고리즘이다. Naive 하게 모든 정점들을 체크하며, 거리값을 relaxation 해주는 경우 시간 복잡도는 O(V^2) 가 나온다. (dijkstra_slow 함수로 구현) Priority_Queue 를 사용하여 최소 거리의 정점을 Heapify 해줄 경우, 시간 복잡도는 ..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. DFS (Depth First Search) DFS 는 깊이 우선탐색으로, 깊이 자료구조 형을 사용하거나, 재귀적으로 방문 체크를 진행하며 구현하면 된다. 포인트는 map 을 이용하여 adjacency list 와 visited 를 처리한 방식이다. 구체적인 코드는 다음과 같다. #include #include #include #include #include class Graph { std::map g; std::map visited; public: void addE..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 문제 링크는 제목에 링크로 걸어두었습니다. BFS (Breadth First Search) BFS 는 넓이 우선탐색으로, 큐(Queue) 자료구조 형을 사용하여 방문 체크를 진행한다. 구체적인 코드는 다음과 같다. #include #include #include using namespace std; class Graph { int N; list* g; public: Graph(int n) : N(n) { g = new list[n]; } void addEdge(int..