그리디 알고리즘 (Greedy Algorithm)눈앞의 이익만 우선 추구하는 알고리즘을 총칭하여 `그리디 알고리즘`이라 한다.그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.📌 그리디 알고리즘은 최적화 문제를 대상으로 한다.최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 한다.do{ 가장 좋아보이는 선택을 한다; (매번 최선의 선택)} until(해 구성 완료)그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아 보이는 선택을 반복한다.그리디 알고리즘으로 최적해가 보장되는 예1) 최소 신장 트리 (MST)최소 신장 트리를 위한 프림 알고리즘, 크루스칼 ..

그래프에서는 모든 정점을 방문해야 할 때가 자주 있다.모든 정점을 방문하는 방법은 다양하지만, 대표적으로 BFS와 DFS 방법을 사용할 수 있다.두 방법은 매우 간단하나, 그래프 알고리즘에서 핵심적인 위치를 차지한다.∴ 두 탐색 방법에 대해 아주 깊은 직관을 가져야 할 필요가 있다.트리에 대해 BFS, DFS 수행루트를 시작으로 탐색을 한다면 `BFS`는 먼저 루트의 자식을 차례로 방문함,다음으로 루트의 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문= 루트에서 가까운 거리 순으로 방문`DFS`는 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려감더 이상 내려갈 수가 없으면 위로 되돌아 오다가 내려갈 곳이 있으면 즉각 내려감 일반적인 그래프 G =(V..

그래프(Graph)는 객체 간의 연결 관계를 표현하는 자료구조노드(Node) 또는 정점(Vertex)과 이를 연결하는 간선(Edge)으로 구성됨.그래프의 활용그래프는 연결 관계를 표현하는 자료구조로, 현실 세계의 다양한 개체와 관계를 모델링할 수 있음SNS 분석사용자 간의 팔로우 관계교통망 & 지도 데이터도시, 도로정거장, 정거장 연결 선컴퓨터 네트워크라우터와 그 연결 관계종류무방향 그래프 (Undirected Graph)간선에 방향성이 없는 그래프, 두 노드는 `양방향`으로 연결됨A → B로 갈 수 있고, B → A로 갈 수 있음 = 서로 연결된 상태방향 그래프 (Directed Graph)간선에 방향성이 있는 그래프, A → B로 향하면, A에서 B로만 이동 가능들어오는 간선과 나가는 간선으로 구분 ..

재귀는 큰 문제를 해결하기 위해 동일한 유형의 더 작은 문제로 나누는 방식자기 자신을 호출하여 반복적으로 작은 문제를 해결해 나가며, 궁극적으로 원래 문제를 해결함📌 완전 탐색, DP, 그래프, 트리 순회와 같은 알고리즘 문제를 푸는 데 중요! 구성 요소기저 조건 (Base Case)더 이상 문제를 쪼갤 수 없거나, 답이 명확해지는 종료 조건기저 조건이 없다면, 무한 호출되며 `Recursion Error` 발생재귀 호출 (Recursive Call)문제를 더 작은 문제로 나누고, 이를 해결하기 위해 자기 자신 호출시간 복잡도재귀의 시간복잡도를 구하는 건 어려움. 수학적으로 접근해 엄밀히 구하려면, 실용성이 떨어짐∴ 대략적으로 계산해야 함📌 시간 복잡도 = 재귀 함수 호출 수 X 재귀 함수 당 시간..