💡그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토합니다. 그리디 알고리즘 예시 문제 - 문제 : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. - 입력 : N = 1260 - 풀이 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 식으로 풀이합니다. 먼저..

💡다이나믹 프로그래밍(DP)란? - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법입니다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. - 다이나믹 프로그맹의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성됩니다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 합니다. 다이나믹 프로그래밍 예시 - 피보나치 수열 n번째 피보나치 수를 f(n)라고 할 ..

위상 정렬💡 - 위상 정렬(Topological sort)는 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것입니다. - 모든 간선(u,v)에 대해 정점 u가 정점v보다 먼저 오는 순서로 정렬이 됩니다. 비순환 방향 그래프(DAG) - 비순환 방향 그래프는 사이클이 없는 방향 그래프입니다. - 왼쪽 그림과 오른쪽 그림의 차이는 정점2에서의 간선차이입니다. 정점끼리 사이클이 생기면 비순환 방향 그래프가 아니게 됩니다. 위상 정렬 동작 과정 진입차수(in_degree)가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 삽입 1) 모든 정점의 in_degree를 표시합니다...

Disjoint Set 분리 집합 분리 집합은 서로소 집합이라고도 합니다. 용어의 의미처럼 분리 집합은 다음과 같은 특징을 가진다. 전체집합 U에 대해, U의 분리 집합 A, B는 다음 조건을 만족한다. - A, B는 U의 부분집합이다. - A, B는 공통 원소를 가지지 않는다. - A, B의 합집합이 곧 전체집합 U이다. (A, B에 속하지 않는 U의 원소가 없어야 한다.) Union-Find 알고리즘 union-Find 알고리즘은 그래프 알고리즘 중 하나로 서로소 집합, 상호배타적 알고리즘이라고도 불립니다. 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어집니다. 동작과정 노..

프림(Prim) 알고리즘 프림 알고리즘은 인접한 정점 중 최소비용으로 이동가능한 정점을 선택하면서 방문하는 알고리즘입니다. 즉, 인접 리스트를 사용한 정점들 간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visit 정보를 기록합니다. 동작과정 최초 출발 정점에서 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 신장 트리에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 간선의 개수가 V-1개가 될 때까지 반복합니다. 모든 정점들이 간선으로 연결이 됐으면 종료합니다. 아래의 예제 그래프의 동작 과정을 그림을 통해 알아보겠습니다. 모든 과정을 통하면 위와 같은 그래프 형태를 나타냅니다. 프림(Prim) 알고리즘은 크루스칼..

스패닝 트리(Spanning Tree) 그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다. 위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다. 스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다. 최소 스패닝 트리(MST) 최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다. 위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다. 이렇게 최소 신장 트리를 효율적으로 찾..

💡이분 탐색 알고리즘이란 이분 탐색 알고리즘은 정렬된 리스트에서 검색 범위를 반으로 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이분 탐색은 배열 내부의 데이터가 정렬(오름차순)되어 있어야만 사용할 수 있는 알고리즘이다. BigO : O(log N) 반드시 정렬된 상태에서 시작해야하므로 로그실행시간을 보장합니다. 구현에 필요한 데이터 Start : data의 처음 값 인덱스 Mid : Start, End 합의 중간 인덱스 End : data의 마지막 값 인덱스 Target : 찾고자 하는 값 data : 오름차순으로 정렬된 리스트 구현 방법 1. 리스트가 정렬된 상태인지 확인합니다. 2. start, end, mid, target 을 확입합니다. 3. 찾고자하는 target이 mid값보다 크면 오른쪽..

📚순열(Permutation) - 순열은 서로 다른 n개의 원소 중 r개를 선택하여 일렬로 나열하는 것을 말합니다. 이 때, 같은 원소가 중복되지 않고, 순서가 중요합니다. 예를 들어, 3개의 원소 A, B, C 중에서 2개를 선택하여 만들 수 있는 순열은 AB, AC, BA, BC, CA, CB입니다. - nPr : 서로 다른 n개에서 순서를 고려하여 r개를 뽑는 경우의 수를 의미합니다. - 예를 들어 4P2일 경우 4! / (4-2)! = 12 가지입니다. 1,2,3,4 중 2개를 뽑는 경우의 수를 나타내면 다음과 같습니다. (1,2), (1,3), (1,4) -> 3가지 (2,1), (2,3), (2,4) -> 3가지 (3,1), (3,2), (3,4) -> 3가지 (4,1), (4,2), (4,3..