KoreanFoodie's Study

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 단절선 (Articulation Edge) 단절점과 단절선은 비슷한 원리로 구할 수 있다. DFS 를 통해 방문 노드의 순서와, 해당 노드를 포함한 자식 노드들에서 가장 먼저 방문한 노드의 순서(최저 방문 순서)를 저장한다. 그 후, 해당 노드의 최저 방문 가능 순서가 인접 노드의 방문 순서보다 클 경우(즉, DFS 방식으로 해당 노드를 방문하는 과정에서 다른 노드에서 해당 노드를 방문할 수 없는 경우) 해당 엣지는 단절선이라고 할 수 있다. 코드는 GeeksForG..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. Boggle : Find all possible words in a board of characters 다음과 같은 보드가 있다고 가정했을때, Dictionary에서 우리가 원하는 단어를 보드를 통해 만들 수 있는지 없는지 확인하는 코드를 짜 보자. 인풋과 아웃풋은 다음과 같다. 제약 조건은, 보드에서 상하좌우 + 대각선 총 8가지 방향으로 이동할 수 있다는 것과, 보드 위의 문자를 중복해서 방문하는 것은 안된다는 것이다. 해당 함수는 DFS 방식으로 구현해야 한다...

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 위상정렬 (Topological Sort) 위상정렬은 유향 그래프 (DAG, Directed Acyclic Graph) 에서 선후관계를 고려한 정렬 방식이다. 즉, A -> B 의 관계가 있다고 했을때, 위상정렬을 하면 반드시 A 가 B 보다 먼저 출력된다. 위상정렬을 하기 위해서는 Incoming Edge 의 값이 0 인 녀석들부터 순서대로 추출하여 출력하면 된다. 특정 Vertex 를 추출하면 해당 Vertex 가 가리키는 Vertex 의 Incoming Edge..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 크루스칼 알고리즘 (Kruskal - Minimum Spanning Tree) 크루스칼 알고리즘은 프림 알고리즘과 비슷하게 최소 신장 트리를 구하는 알고리즘이다. 다만 원리는 조금 다르다. 먼저, 모든 Vertex 들을 별도의 집합으로 만든다. 그 후, 모든 엣지들을 우선순위 큐에 넣고, 최소 가중치를 가진 녀석들부터 꺼내 두 Vertex 를 이어준다. 이때, 같은 집합인 경우는 연결하지 않는다. 집합이 같은지를 판별하는 것은 Union-Find 를 이용해 검사한다...

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 프림 알고리즘 (최소 신장 트리) 프림 알고리즘은 Greedy 한 방식으로 Vertex 들을 이어 최소 신장 트리를 만든다. 구체적으로는 : 해당 정점의 집합 대해, 연결된 {간선, 정점} 쌍을 정점 가중치 기준으로 우선순위 큐에 넣는다. 그리고 가중치가 기존의 가중치보다 작으면서, 도착 지점이 미방문인 노드를 집합에 넣고, 추가된 노드의 {간선, 정점} 쌍들을 다시 우선순위 큐에 넣는다. 해당 작업을 모든 Vertex 를 순회할 때까지 반복하면 된다. 시간 복잡도는..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 유니온 파인드 / 사이클 찾기 (Union-Find / Cycle Detection) 유니온 파인드는, disjoint set 들을 합쳐서 각 vertex 들이 같은 집합인지 아닌지 판별하는데 사용되는 알고리즘이다. parent 배열에 각 vertex 의 조상(root node) 의 정보를 저장하고, find, union 등의 함수를 이용해 부모 노드를 탐색하고 집합을 합친다. find 함수를 구현할 때, 재귀적으로 경로 탐색 도중 만난 vertex 들이 부모 노드를..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 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..