티스토리

영벨롭 개발 일지

검색하기

블로그 홈

영벨롭 개발 일지

iridescent-zeal.tistory.com/m

영벨롭 님의 블로그입니다.

구독자: 2

방명록 방문하기

주요 글 목록

[알고리즘]MST 최소 신장 트리 알고리즘 - Kruskal & Prim [ Spanning Tree ] Spanning Tree(신장 트리)는 그래프 내의 모든 정점을 포함하는 트리입니다. 그래프의 n 개의 정점을 모두 연결하는 최소 간선의 수는 (n-1) 개이고, 이때 이루어진 그래프를 최소 연결 부분 그래프, 즉 Spanning Tree라고 합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리입니다. - Spanning Tree 특징 DFS, BFS를 이용하여 그래프의 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 신장 트리는 모든 정점들이 연결되어 있어야 한다. 신장 트리는 사이클을 포함해서는 안된다. 신장 트리는 n 개의 정점과 (n-1) 개의 간선으로 이루어져 있다. [ MST 최소 신장 트리 ] 최소 신장 트리(MST, mi.. 공감수 0 댓글수 0 2022. 6. 9.
[알고리즘]그리디 알고리즘 Greedy Algorithm [ 그리디 알고리즘 Greedy algorithm ] 그리디 알고리즘(greedy algorithm)은 매 단계에서 '가장 좋아보이는' 해답을 선택하는 알고리즘으로 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식입니다. 즉, 당장 눈 앞에 보이는 최적의 상황만을 쫓는 가장 단순한 형태의 알고리즘입니다. 때문에 욕심쟁이 또는 탐욕 알고리즘이라고 불리기도 합니다. ★ 그리디 알고리즘을 사용하기 적합한지 판단하는 기준 1. 최적 부분 구조(optimal substructure) 속성 : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우, 문제 P가 최적의 부분 구조를 갖는다고 말합니다. 2. 그리디 선택(greedy choice) 속성 : 주.. 공감수 0 댓글수 0 2022. 5. 10.
[알고리즘]분할정복을 이용한 정렬 알고리즘 - 병합 정렬 & 쾌속 정렬 [ 분할 정복 ] 분할 정복 (divide-and-conquer) 접근 방법은 주어진 문제의 규모가 클 때 문제를 작은 부분 문제로 나눠서 해결하는 방식입니다. 부분 문제로 나누는 작업을 반복하여 그 해답을 찾고, 다시 그 해답을 합쳐서 처음 문제에 대한 해답을 유도하는 것입니다. 분할 정복 알고리즘의 세 단계 1. 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 부분 문제로 나눕니다. 2. 정복(conquer) : 각 부분 문제에 대한 해답을 구합니다. 3. 결합(combine) : 각 부분 문제의 해답을 결합하여 전체 문제에 대한 해답을 구합니다. 일반적인 정렬 알고리즘(bubble sort, insertion sort, selection sort)은 한 쌍식 비교하여 정렬.. 공감수 0 댓글수 0 2022. 5. 6.
[알고리즘]이진 탐색 Binary Search 알고리즘 [ 선형 탐색 Linear Search ] 선형 탐색은 배열의 첫 번째 원소부터 차례대로 전체 원소를 방문하면서 해당 원소가 검색하려는 원소와 같은지 확인하는 방법입니다. 이 방법의 장점은 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작한다는 점입니다. 하지만 이 방법은 효율적이지 않으며, 주어진 배열이 정렬되어 있어도 그 점을 전혀 활용하지 못합니다. 선형 탐색 알고리즘의 시간 복잡도는 O(N)입니다. int linear_search(int N, vector arr) { for(int i = 0; i < arr.size(); i++){ if(arr[i] == N) return i; } return -1; } [ 이진 탐색 Binary Search ] 선형 탐색과 달리 이진 탐색은 정렬된 배열에서만 동.. 공감수 0 댓글수 0 2022. 5. 4.
[알고리즘]브루트 포스 알고리즘, Brute Force Algorithm 브루트 포스(Brute Force) 알고리즘 Brute 짐승, 동물 Force 힘 브루트 포스 알고리즘은 단어 뜻에서 유추할 수 있듯이 무식하게 모든 경우에 대해 모두 직접 탐색하는 완전탐색 알고리즘입니다. 가능한 모든 경우의 수를 모두 탐색하면서 원하는 결과를 도출합니다. 때문에 예외 없이 100% 학률로 정답을 얻을 수 있습니다. 브루트 포스의 종류 브루트 포스 알고리즘은 크게 두 가지 종류로 나뉠 수 있습니다. 1. 선형 구조: 순차 탐색 2. 비선형 구조: DFS, BFS, 백트래킹 https://iridescent-zeal.tistory.com/25?category=1261295 [알고리즘]그래프 탐색하기: BFS & DFS 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그.. 공감수 0 댓글수 0 2022. 3. 18.
[알고리즘]랜덤 미로 생성 알고리즘: 엘러(Eller)의 알고리즘 DFS나 BFS와 같은 여러 탐색 알고리즘들로 미로를 탐색할 수 있었죠? 오늘은 미로를 직접 만들어보겠습니다. 미로를 만드는 알고리즘에는 여러가지가 있는데 그 중 Eller's Algorithm 엘러의 알고리즘을 살펴보겠습니다. 랜덤 미로 생성 알고리즘 Eller's Algorithm 엘러의 알고리즘은 미로를 한 행 씩 차례로 생성해나가는 방법입니다. 가장 빠르게 미로를 생성하는 알고리즘 중 하나이다. 미로의 크기가 N이라면 시간복잡도는 O(N)으로, 미로를 선형시간 안에 만드는 엄청난 성능의 알고리즘입니다. 생성 과정 3x5 크기의 미로를 생성하는 과정은 다음과 같습니다. 1. 미로의 첫 번째 행을 초기화합니다. 이때 첫 번째 행에 속한 5개의 칸을 서로 다른 집합에 속하게 합니다. 2. 현재 행에서 .. 공감수 0 댓글수 0 2022. 3. 7.
[알고리즘]그래프 탐색하기: BFS & DFS 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 순회 문제(graph traversal problem)이라고 합니다. 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제(graph search problem)이라고도 합니다. 그래프 탐색에서 아직 방문하지 않은 노드들 중 다음으로 살펴볼 노드들의 리스트를 open list, 방문한 노드들의 리스트를 closed list라고 말합니다. 그래프 탐색 알고리즘으로 너비 우선 탐색(BFS, Breadth-First Search)와 깊이 우선 탐색(DFS, Depth-First Search)가 있습니다. 너비 우선 탐색(BFS, Breadth-First Search) BFS는 탐색 과정에.. 공감수 0 댓글수 0 2022. 2. 25.
[알고리즘]다이나믹 프로그래밍(Dynamic Programming, DP) 1. Dynamic Programming(동적 계획법)이란? 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다. 2. DP의 원리, Memoization 동적 계획법의 원리는 처음 진행된 연산은 기록해 두고 이미 진행했던 연산이라면 기록한 값을 가져와 중복 계산을 줄이는 것입니다. 이것을 메모이제이션(Memoization)이라고 합니다. 3. DP의 조건 작은 문제가 반복될 경우 같은 문제에 대한 결과가 항상 같을 경우 4. DP 사용 예시: 피보나치 수열 DP가 사용되는 예시로 피보나치 수열을 들겠습니다. (1) 재귀호출을 이용한 풀이 //재귀호출을 통한 피보나치 수열 구하기 int fibonacci(int n){ if(n 공감수 0 댓글수 0 2022. 2. 23.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.