2020 WONIZZ.LOG
안녕하세요? 정리하는 개발자 워니즈입니다. 2020년을 마무리하는 마지막날입니다. 1년의 마지막날은 WONIZZ.LOG를 기록해두며, 한 해동안 워니즈는 어떻게 살았는지 그리고 앞으로는 무엇을 할것인가에 대한 고민을 기억하기 위해서 글을 작성해보겠습니다. 2020년은 그야말로, 코로나로 인해서 너무나도 당연했던 일상들이 하나씩 사라졌던…
[Algorithms] BFS, DFS 알고리즘
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 기본 알고리즘중 하나인 BFS, DFS 알고리즘에 대해서 정리를 해보도록 하겠습니다. 그래프의 모든 노드를 방문하는 알고리즘으로, 면접시에도 많이 나오는 내용이라 필히 알아둬야 할 내용입니다 . 1. DFS 알고리즘 Depth First Search의…
[문제풀이] 군사도로망
1. 설명 군사도로망 문제 어떤 나라는 NN개의 도시로 구성되어 있다. 도시들을 연결하는 도로들이 있는데, 도로라는 것은 서로 다른 두 도시를 연결하는 기능을 하며, 양방향 통행이 가능하고 하나의 도시 쌍에 대해서는 최대 하나의 도로만이 존재 가능한…
[Algorithms] LCA 알고리즘
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 이진트리에서 최저 공통 조상을 찾아나가는 알고리즘인 LCA(Lowest Common Ancestor) 알고리즘에 대해서 정리를 해보도록 하겠습니다. LCA 알고리즘은 최소 공통 조상을 찾는 알고리즘이고, 트리의 두 노드로부터 최적의 공통 노드를 찾아 나가는 알고리즘입니다.…
[Algorithms] 세그먼트 트리
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 알고리즘 자료구조중 가장 많은 활용도를 보이는 세그먼트 트리에 대해서 정리를 해보도록 하겠습니다. 세그먼트 트리는 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법에 관한 것입니다. 예를들어, 배열에 1…
[Algorithms] 벨만-포드 알고리즘
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 최단거리 알고리즘중 음의 가중치도 계산이 가능한 벨만-포드 알고리즘에 대해서 정리를 해보도록 하겠습니다. 다익스트라보다 시간 복잡도가 높기에 어떤 상황에서 이용해야 할지 잘 생각하여 사용해야합니다. 1. 벨만포드 기본 개념 최단 경로를 구하기…