[알고리즘] 분할정복(Divide and Conquer)
·
컴퓨터 과학/알고리즘
오늘은 분할정복에 대해서 설명해보도록 하겠습니다. 우선 분할정복이란 문제를 여러 개의 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다. 이렇게보면 동적계획법이랑 다른게 없어 보일 수 있습니다. 하지만 이 두 알고리즘은 두 차이점이 존재합니다. 분할정복vs동적계획법분할정복 (Divide and Conquer)아이디어: 문제를 여러 개의 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다.특징하위 문제들이 서로 독립적입니다. 즉, 서로 겹치지 않으며, 동일한 부분 문제를 여러 번 해결하지 않습니다.예시는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary..
[알고리즘] 프림 알고리즘(Prim)
·
컴퓨터 과학/알고리즘
프림 알고리즘(Prim's Algorithm)은 그래프에서 최소 신장 트리를 찾는 그리디 알고리즘입니다. 최소 신장 트리란, 모든 노드가 연결되면서 그 가중치 합이 최소가 되는 트리를 의미합니다. 이 알고리즘은 네트워크 설계, 전선 연결 등에서 활용될 수 있습니다.알고리즘 개요프림 알고리즘은 그래프에서 시작 노드를 선택한 후, 가장 작은 가중치를 가진 간선을 하나씩 선택해 나가는 방식입니다. 즉, 트리를 단계적으로 확장해 나가는 그리디한 접근을 사용합니다. 프림 알고리즘 과정시작 노드 선택: 임의의 노드를 시작점으로 선택합니다.트리 확장: 트리에 포함되지 않은 노드 중에서, 트리에 가장 작은 가중치로 연결될 수 있는 간선을 선택하여 해당 노드를 트리에 포함시킵니다.반복: 트리에 속하지 않은 모든 노드가 ..
[알고리즘] Greedy Algorithm - Interval Scheduling
·
컴퓨터 과학/알고리즘
Interval scheduling Job j starts 𝑠𝑗 and finishes at 𝑓 𝑗.Two jobs are compatible if they don’t overlapGoal: find maximum subset of mutually compatible jobs일을 가장 많이 사용하는 방법을 찾는 경우를 찾는다고 했을 때 문제입니다.직관적으로 봤을 때 b, e, h를 고를 시 가장 많은 경우의 수를 고려하지만 직관적으로 해결 하는 것이 아닌 다양한 접근법을 이용해서 해결 해보겠습니다.Approach 1) Earliest start time: Consider jobs in ascending order of 𝑠 𝑗일이 시작되는 시간 중에서 가장 먼저 시작되는 일을 기준으로 시작한다...
[알고리즘] 비트마스크(BitMask)
·
컴퓨터 과학/알고리즘
비트마스크란?비트마스크(Bitmask)는 이진수의 비트를 사용해 여러 상태나 조합을 효율적으로 표현하는 기법입니다. 각 비트는 특정한 상태를 나타내며, 비트 연산을 통해 다양한 조합을 처리할 수 있습니다. 비트마스크는 조합 문제나 상태 추적 문제에서 특히 유용하게 사용됩니다. 장점메모리 효율성: 비트를 사용해 여러 상태를 간단하게 저장할 수 있어, 메모리 공간을 절약할 수 있습니다.속도: 비트 연산은 빠르기 때문에, 대량의 데이터를 신속하게 처리할 수 있습니다.조합 관리: 비트마스크를 사용하면 여러 상태를 조합하는 문제를 쉽게 해결할 수 있습니다.코드의 간결성: 비트 연산을 사용하면 코드가 간결해지고 가독성이 좋아질 수 있습니다.단점이해의 어려움: 비트마스크의 개념이 초보자에게는 다소 복잡하게 느껴질 수..
[알고리즘] 투 포인터(Two Pointer)
·
컴퓨터 과학/알고리즘
투 포인터 기법은 배열이나 리스트를 탐색하는 데 매우 효율적인 알고리즘 기법입니다. 두 개의 포인터를 사용하여 문제를 해결하는 이 기법은 주로 정렬된 데이터에서 특정 조건을 만족하는 쌍을 찾는 데 유용합니다. 이 기법은 많은 경우에 O(N) 또는 O(N^2)의 시간 복잡도를 가지며, 최적화된 솔루션을 제공합니다. 투 포인터(Two Pointer) 기본 개념투 포인터 기법은 다음 두 가지 주요 방식으로 사용됩니다:양 끝에서 시작하기적용 예: 정렬된 배열에서 두 수의 합이 목표 값과 일치하는 쌍을 찾는 문제방법: 배열의 시작과 끝에 각각 포인터를 두고, 두 포인터가 가리키는 값의 합을 계산합니다. 합이 목표 값과 같으면 쌍을 찾은 것이고, 그렇지 않으면 포인터를 조정합니다.같은 방향으로 이동하기적용 예: 특..
[알고리즘] 이분 탐색(Binary Search)
·
컴퓨터 과학/알고리즘
이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누면서 원하는 값을 찾는 방식으로 동작하며, 시간 복잡도가 O(logn)입니다. 이는 선형 탐색(Linear Search)의 O(n)과 비교할 때 훨씬 더 효율적입니다. 이분 탐색 알고리즘의 동작 원리시작과 끝 설정: 배열의 시작점(low)과 끝점(high)을 설정합니다.중간점 계산: 시작점과 끝점의 중간 인덱스(mid)를 계산합니다.중간값 비교: 배열의 중간 값(arr[mid])과 찾고자 하는 값(target)을 비교합니다.만약 arr[mid]가 target과 같으면, 해당 인덱스를 반환합니다.만약 arr[mid]가 target보다 크면, target은 ..
[알고리즘] 최소 공배수(LCM, Least Common Multiple)
·
컴퓨터 과학/알고리즘
최소공배수(LCM, Least Common Multiple)를 구하는 여러 가지 방법이 존재하며, 이 중에서도 유클리드 호제법을 활용한 방법이 가장 효율적입니다. 아래에서는 여러 방법을 비교하고, 각 방법의 특징과 효율성을 설명하겠습니다. 1. 완전 탐색 기반 방법 (Brute Force)이 방법은 두 수의 배수를 계산하고, 가장 작은 공통 배수를 찾는 매우 직관적인 방법입니다. 알고리즘a와 b의 배수를 각각 계산합니다.두 수의 배수 중에서 가장 작은 공통 배수를 찾습니다.def lcm_brute_force(a, b): max_ab = max(a, b) lcm_value = max_ab while lcm_value % a != 0 or lcm_value % b != 0: lc..
[알고리즘] 최대 공약수(GCD, Greatest Common Divisor)
·
컴퓨터 과학/알고리즘
이번에는 최대공약수(GCD, Greatest Common Divisor)를 구하는 여러 알고리즘을 소개하겠습니다. 각 방법은 효율성이나 구현 방식에 차이가 있습니다. 1. 완전 탐색 방법 (Brute Force)첫 번째는 완전 탐색 방법을 이용한 최대 공약수를 구하는 방법 입니다.가장 직관적인 방법으로, 두 수의 공통된 약수 중에서 가장 큰 값을 찾는 방법입니다. 알고리즘두 수 중 작은 수를 선택합니다.그 수로부터 1까지 모든 수에 대해 두 수 모두를 나눌 수 있는지 확인합니다.두 수를 모두 나눌 수 있는 가장 큰 수가 최대공약수입니다.def gcd_brute_force(a, b): min_num = min(a, b) for i in range(min_num, 0, -1): if ..
[알고리즘] 동적계획법(Dynamic Programming)
·
컴퓨터 과학/알고리즘
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 푸는 알고리즘입니다.각 하위 문제는 한 번만 계산하고 그 결과를 저장하여, 동일한 하위 문제가 다시 나타날 때 재계산하지 않고 저장된 결과를 사용하는 것이 핵심입니다. 이로 인해 중복된 계산을 피할 수 있다는 장점을 가지고 있다!동적 계획법의 기본 아이디어 분할 정복: 문제를 여러 하위 문제로 나눈다.중복된 하위 문제: 여러 하위 문제가 여러 번 등장하는 경우가 많다.최적 부분 구조: 문제의 최적해는 하위 문제의 최적해로 구성된다.메모이제이션: 이미 계산한 하위 문제의 결과를 저장해 둔다. 동적 계획법의 구현 방식동적 계획법은 크게 두 가지 방식으로 구현할 수 있습니다.탑 다운(Top-Down)바텀 업(Bo..
[알고리즘] 다익스트라 알고리즘(Dijkstra)
·
컴퓨터 과학/알고리즘
다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다. 다익스트라 알고리즘이 프림 알고리즘과 다른 두 가지 차이점은 다음과 같다. 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만 프림 알고리즘은 모든 정점을 방문해야 종료한다.그래프를 예시로 다익스트라 알고리즘의 동작에 대해 설명해 보겠습니다. 가중치가 부여된 그래프가 있습니다. 1를 시작 정점으로 잡고 퍼져나가는 것을 알아보겠습니다. 구현 (1) : 순차 탐색을 이용한 방법으로 노드의 개수가 N이라고 할 때 각 노드마다 최..
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)
·
컴퓨터 과학/알고리즘
너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.깊이 우선 탐색 깊이 우선 탐색은 시작 정점을 경계에 추가하는 것으로 시작한다. 너비 우선 탐색의 그림 예를 변형해서 가져왔다. 하나의 지점에서 시작하여 가능한 멀리 있는 정점에 도달하고 재귀하는 방식을 가진다.구현 깊이 우선 탐색은 두 가지의 코드를 사용할 수 있다. 1. Stack를 이용한 깊이 우선 탐색 2. 재귀 함수를 이용한 깊이 우선 탐색 이 두 가지가 있다. (1) #include #include #include using namespace std; bool visited[9]; vector ..
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)
·
컴퓨터 과학/알고리즘
그래프 순회 문제란 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 문제라고 한다.그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용할 수 있기 때문에 그래프 탐색 문제(graph search problem)라고 부르기도 한다. 오늘 알아볼 것은 여러 그래프 탐색 알고리즘 중 하나인 너비 우선 탐색에 대한 내용이다.너비 우선 탐색 너비 우선 탐색(BFS)은 시작 정점을 경계에 추가하는 것으로 시작한다.(1)의 검정 동그라미가 시작정점이라고 했을 때 퍼져나가는 모습을 표현했다. 그림 예 (1) (2) (3) (4) (5) 즉 이렇게 시작 지점에서 경계에 인접한 정점을 반복적으로 탐색하는 방법을 가진다.이렇게 되면 전체 그래프를 순회할 수 있게 된다.구현 #include #i..
김치바보
'컴퓨터 과학/알고리즘' 카테고리의 글 목록
상단으로

티스토리툴바