[알고리즘] 매개변수 탐색 알고리즘: 최적의 설정을 찾는 방법
·
컴퓨터 과학/알고리즘
기계 학습 모델을 개발할 때, 성능을 극대화하기 위해서는 모델의 하이퍼파라미터를 적절히 설정하는 것이 중요합니다. 하이퍼파라미터란 모델의 학습 과정에 직접적으로 영향을 미치는 변수로, 학습률, 신경망의 레이어 수, 뉴런 수, 정규화 계수 등이 포함됩니다. 하지만 최적의 하이퍼파라미터를 찾는 과정은 쉽지 않습니다. 이 글에서는 대표적인 매개변수 탐색 알고리즘과 그 특징에 대해 알아보겠습니다. 1. 그리드 탐색(Grid Search)그리드 탐색은 모든 가능한 매개변수 조합을 체계적으로 탐색하는 방법입니다. 사용자가 지정한 각 매개변수의 값들에 대해 모든 조합을 시도하며, 가장 성능이 좋은 조합을 찾습니다.간단한 예제from sklearn.model_selection import GridSearchCVfrom..
[알고리즘] Union-Find 유니온-파인드(Disjoint Set Union)
·
컴퓨터 과학/알고리즘
Union-Find(또는 Disjoint Set Union, DSU)는 그래프 알고리즘에서 서로소 집합(Disjoint Sets)을 관리하기 위해 사용되는 자료구조입니다. 이 알고리즘은 대표적으로 최소 스패닝 트리(MST) 알고리즘인 Kruskal's Algorithm에서 사용되며, 효율적으로 그래프의 연결성을 판단하거나 집합을 관리할 수 있습니다. 1. Union-Find란 무엇인가?Union-Find는 다음 두 가지 연산을 빠르게 수행할 수 있도록 설계된 자료구조입니다.Find(x): 원소 x가 속한 집합의 대표자(루트 노드)를 찾습니다.Union(x, y): 원소 x와 y가 속한 두 집합을 하나로 합칩니다.이 두 연산을 통해 집합을 동적으로 관리하며, 집합의 연결성을 확인할 수 있습니다. 예를 들어..
[알고리즘] 분할정복(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이라고 할 때 각 노드마다 최..
김치바보
'컴퓨터 과학/알고리즘' 카테고리의 글 목록
상단으로

티스토리툴바