KoreanFoodie's Study

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

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요! 템플릿 클래스 인스턴스는 같은 타입일까? 템플릿 클래스로 만든 두 클래스에서 인자만 바꾼다면, 해당 인스턴스들은 같은 타입일까? 다음 코드를 보자. #include #include template class Array { T data[N]; public: Array() {} Array(T (&arr)[N]) { for (int i = 0; i < N; ++i) { data[i] = arr[i]; } } T* get_array() { return data; } int size() { return N; } void print_all() { for (int i = 0; i < N; ++i..

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요! 가변 길이 템플릿 C++ 템플릿을 이용하면 파이썬처럼 임의의 갯수의 인자를 받는 함수를 구현할 수 있다. #include template void print(T arg) { std::cout

바야흐로 예약대란이다. 유명하고 맛있는 곳을 방문하기 위해서는 사전작업이 거의 필수가 된 시대가 열렸다. 물론 너무 장사가 잘 되서, 굳이 예약 따위 받지 않는 음식점들도 부지기수다. 그런 곳들은 추운 겨울날 롱패딩을 부여 잡으며 같이 온 친구나 연인들과 펭귄 놀이를 할 준비를 해야한다. 아버지는 자칭 미식가이기에 맛집을 찾아가시는 편이다. 포장도 자주 해 오시고. 자칭 미식가인 아버지. 하지만 내가 생각하기에, 아버지는 혼(混)식가에 가깝다. 뭐든지 비비고 섞어 드시니까. 전문 용어로 쓰까 묵는다고 하던가? 맛집의 세계는 냉혹하다. 잘되는 곳은 잘되고, 안되는 곳은 안되는 법. 너무나도 당연한 말이지만, 음식점의 경우 그 편차가 제법 크다. 바로 옆집에 붙어 있어도 문전성시를 이루는 집과, 파리만 날리..