KoreanFoodie's Study

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

2020년 삼성 코딩테스트(SW역량테스트) 하반기 시험 후기 및 조언 일단 후회가 굉장히 많이 드는 시험이었다. 나름대로 준비를 한다고 기출문제 약 50개 정도를 풀고 갔는데, 첫 시험이라 그런지 너무너무 긴장을 해서, 실력발휘를 제대로 하고 오지 못한 것이 너무나 아쉬웠다. 다음 번에 이런 코딩테스트를 또 보게 된다면, 집에서 느긋한 마음으로 문제를 풀지 않고, 딱 시간을 정해서 3시간 동안 2문제를 푸는 실전훈련을 해야 겠다는 생각이 들었다. 1번은 N*N 격자판에서 중앙 지점에서부터 시작하여 나선 모양으로 손가락을 이동하면서, 모래를 확산시키는데, 이때 격자판 바깥으로 나가는 모래의 양을 구하는 문제였다. 매우 쉬운 문제였다. 그런데 나는 이걸 코드를 짜 놓고, 복붙을 하는 과정에서 오타를 냈고, ..

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다! 해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 코드에 대한 설명은 주석을 참고해 주세요 :) 0. SW 역량 테스트란 무엇일까? ... 그렇다고 한다. 출제 유형은 크게 4가지로 정리되는데, 각 유형마다 꼭 풀어보면 좋을 문제들의 링크와 해답을 각각 아래에 정리해 놓았다. 백준에 올라온 기출문제를 포함해, 풀어보면 좋을 문제들을 모아 봤으니, 코딩테스트를 준비하기에 좋은 문제 셋이라고 생각한다! 1. 완전 탐색, 백트래킹 (BFS, DFS) (필수) [모의 SW 역량테스트] 수영장 / 해답 (필수) [백준] 사다리 조작 / 해답 (필수) [백준] 테트로미노 / 해답 [모의 SW 역량테스트] 디저트 카페 / 해답 [모의..