알고리즘22 [알고리즘] 매개변수 탐색(Parametric Search) 🟡 매개변수 탐색(Parametric Search) - 어떤 조건을 만족하는 함수나 값 중에서 특정한 값을 찾거나 최적화 하는 알고리즘 - 주로 수치 계산 문제나 최적화 문제에서 사용된다. 🟡 매개변수 탐색이 사용되는 상황 ① 조건을 만족하는 값 찾기 - 어떤 함수나 조건식이 주어졌을 때, 이 조건을 만족하는 특정 값을 찾기 위해 사용한다. - 예를들어, 어떤 함수 f(x)의 값이 특정 값 k와 같아지는 x를 찾는 문제 ② 최적화 문제 - 주어진 함수나 목적 함수를 최대화 또는 최소화하는 변수 값을 찾는 문제에도 적용될 수 있다. - 함수 값의 변화를 추적하며 최적 값에 접근한다. 🟡 매개변수 탐색 수행 단계 ① 매개변수 범위 정의 - 매개변수 탐색에 사용될 매개변수의 범위를 정의한다. ② 이분 탐색 -.. 2023. 8. 25. [알고리즘] 분할정복을 사용한 거듭제곱 계산 알고리즘 🟡 분할 정복을 사용한 거듭제곱 연산법 - x^n을 다음과 같이 쪼갤 수 있다. 1) n이 짝수인 경우 x^n = x^(n/2) * x^(n/2) 2) n이 홀수인 경우 x^n = x^(n-1/2) * x^(n-1/2) * x 🟡 시간 복잡도 - 일반적인 방법으로 x^n을 계산하려면 시간복잡도는 O(n)이다. - 그러나 분할정복을 사용하여 계산하면 시간복잡도는 O(log n)이다. 2023. 8. 23. [알고리즘] 분할 정복 알고리즘(Divide and Conquer) 🟡 분할 정복 알고리즘(Divide and Conquer) - 큰 문제를 작은 부분 문제로 분할하여 해결하는 알고리즘이다. - 주어진 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제를 재귀적으로 해결한 후, 그 해답을 결합하여 원래 문제의 해답을 얻는 방법이다. 🟡 분할 정복 알고리즘의 단계 ① 분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할한다. ② 정복(Conquer): 작은 부분 문제들을 재귀적으로 해결한다. ③ 결합(Combine): 작은 부분 문제들의 해답을 결합하여 원래 문제의 해답을 얻는다. 🟡 분할정복 알고리즘 예시 ① 병합 정렬(Merge Sort) ② 퀵 정렬(Quick Sort) ③ 이진 검색(Binary Search) ④ 카라츠바 곱셈 알고리즘(Karatsuba) 2023. 8. 18. [알고리즘] 그래프 표현방법 3가지 🟡 그래프 표현방법 3가지 ① 에지 리스트(Edge List) ② 인접 행렬(Adjacency Matrix) ③ 인접 리스트(Adjacency List) 🟡 에지 리스트 - 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 이 경우 배열의 열은 2개면 된다. - 혹은 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.이 경우 배열의 열은 3개를 사용한다. - 에지 중심으로 표현한 것이라, 이를 사용하여 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다. - 에지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다. 🟡 인접 행렬 - 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. - 노드 중심으로 그래프를 표현한다. -.. 2023. 8. 14. [알고리즘] 동적 계획법(Dynamic Programming) 🟡 동적 계획법(Dynamic Programming) - 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 🟡 동적 계획법의 핵심 이론 ① 큰 문제를 작은 문제로 나눌 수 있어야 한다. ② 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다. ③ 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모이제이션(memoization) 기법이라고 한다. ④ 동적 계획법은 톱-다운(top-down)방식과 바텀-업(bottom-up) 방식으로 구현할 수 있다. · 톱-다운 방식: 위에서부터 문제를 파악해 내려오는 방식. 주로 재귀함수로 코드를 구현 ·.. 2023. 7. 20. [알고리즘] 정렬 - 카운팅 정렬(counting sort, 계수 정렬) 🟡 카운팅 정렬(counting sort, 계수 정렬) - 다른 정렬 알고리즘들과는 다르게 입력 배열의 값을 비교하지 않고, 각 값의 등장 횟수를 세어 정렬하는 방식 - 따라서 입력 배열의 값의 범위가 제한되어야 한다. - 카운팅 정렬은 입력 배열의 크기가 N, 입력 값의 범위를 K라고 할 때, O(N+K)의 시간 복잡도를 가진다. - 입력 값의 범위가 큰 경우에는 메모리 사용량이 많아진다. 🟡 카운팅 정렬 진행 과정 카운팅 정렬의 기본 아이디어는 각 입력 요소의 등장횟수를 기록하기 위해 카운트 배열을 사용하는 것 ① 입력 배열을 순회하며 각 요소의 등장 횟수를 카운트 배열에 기록한다. 카운트 배열의 인덱스는 입력 요소의 값이고, 각 인덱스의 값은 해당 요소의 등장 횟수다. ② 카운트 배열을 누적 합 배.. 2023. 6. 30. 이전 1 2 3 4 다음
