TOOLS_스터디

이 시리즈는 저희 학교내 동아리인 Tools 동아리의 친한 형이 진행하는 알고리즘 스터디를 들으며 배운 내용을 스스로 정리하며 작성해나갈 것 입니다.Brute force는 완전 탐색을 의미합니다. 빠르고 정확한 컴퓨터의 장점을 이용해서 모든 경우의 수를 하나씩 확인하는

Week2

Graph란 정점과 간선으로 이루어진 자료구조를 말한다. 정점은 어떤 자료를 표현하며 간선은 정점들 사이 관계를 나타내기위해 사용된다.단순경로 : 특정 출발점에서 도착점으로 이동하는 동안 같은 정점을 최대 한 번만 방문한 경로.사이클 : 출발점과 도착점이 같은 경우.루

DP DP는 Dynamic programming으로 동적 계획법을 뜻합니다. 문제를 작게 나누어서 해결하는 기법입니다. DP는 다음 두가지 조건을 만족하여야합니다. Optimal substructure 작은 문제들을 이용하여 전체 문제를 해결할 수 있는 경우. 풀고

Optimal SubstructureX를 1로 만드는 방법은 X-1, X/2, X/3을 1로 만든 방법을 이용하여 구할 수 있습니다.Overlapping SubproblemX는 X+1, 2X, 3X를 계산할 때 사용됩니다. 즉 어떤 정수 X는 최대 3번 계산 되어야합니

우선순위 큐는 큐와 비슷한 자료구조이지만, 가장 먼저 들어온 데이터를 가장 앞에서 처리하는 것이 아닌 우선순위가 가장 높은 데이터를 앞에서 처리하는 자료구조입니다.Binary tree자신보다 낮은 곳에 위치한 곳엔 우선순위가 낮은 데이터가 저장되어 있음가장 끝에 데이터

Divide & Conquer은 분할 정복을 뜻합니다. 분할 정복은 큰 문제를 작은 문제로 분할하여 푼다는 관점에서 DP와 유사합니다. 하지만 DP에서 나타나는 특징인 overlapping subproblem이 나타나지 않습니다. 분할 정복은 크게 아래에 있는 세 가지

Tree Tree는 아래의 조건들을 만족하는 그래프입니다. 사이클이 존재하지 않는다. 어느 한 정점 u에서 다른 정점 v로 이동할 수 있는 경로가 유일하다. 정점의 갯수를 V개라고 하면 간선의 갯수는 V-1개이다. 모든 정점의 in-degree(한 정점을 기준으로 들

최단 경로 문제는 그래프를 이용한 문제에서 매우 흔히 보이는 유형입니다. 그럼 최단 경로의 정의는 무엇일까요? 최단 경로란 말 그대로 가장 짧은 경로를 뜻합니다. 정점들 사이에 가중치가 있다고 가정하였을 때, 그 가중치의 합이 최소가 되는 경로를 뜻하는 것이죠. 이러한

MST란 최소 신장 트리(최소 스패닝 트리)를 뜻한다. 먼저 신장 트리(스패닝 트리)란 주어진 그래프에서 모든 정점을 포함하면서 간선의 수가 가장 적은 그래프를 뜻한다. 이 때, 사이클이 존재하면 안된다. 그리고 이 스패닝 트리를 구성하는 간선들의 가중치의 합이 최소가