아삭

Union-Find (합집합 찾기 알고리즘) = Union 연산 + 루트를 찾는 Find 연산두 노드가 같은 집합에 속하는지 판별하는 그래프 알고리즘Disjoin Set: 서로소 집합(상호 배타적 집합) ★ Find(x)원소 x가 속한 집합의 대표(루트)를 찾는 함수.경로 압축(Path Compression) 기법을 써서 효율성을 높을 수 있음.※ 자신의 부모 노드만 저장하게 되면 재귀 호출을 통한 탐색에 시간이 많이 들기 때문에,인접한 부모 노드가 아니라 루트 노드의 번호를 저장해야함! ★ Union(x, y)원소 x와 y가 속한 두 집합을 하나로 합치는 함수.대표 노드를 기준으로 한 집합으로 병합.# 초기1   2   3   4   5 ↑   ↑   ↑   ↑   ↑ 자기 자신이 루트# union(1..

최소힙import heapqmin_heap = [6, 1, 8, 5, 4, 3, 7]# 힙 변환 # 시간복잡도 O(N)heapq.heapify(min_heap) #[1, 4, 3, 5, 6, 8, 7]# root(최소값) 반환, 비어 있는 경우 IndexError# 시간복잡도 O(logN)heapq.heappop(min_heap) #[3, 4, 7, 5, 6, 8]# 힙에 원소 추가heapq.heappush(min_heap, 2) #[2, 4, 3, 5, 6, 8, 7] 힙 (heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된완전이진트리(complete binary tree)부모노드와 자식노드 간에만 대소관계가 성립되지만,형제 사이는 상관없다.부모노드의 순서가 ..

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.(출처: 위키백과)  백준 1003번을 풀었는데 시간 초과가 되서 해결법을 찾아보다가"메모이제이션"을 해야 성공할 수 있다고 해서 찾아보았다.https://www.acmicpc.net/problem/1003

파라메트릭 서치는 이진탐색과 유사하지만이진탐색은 정렬된 값 중에서 원하는 값을 찾는 알고리즘이라면파라메트릭 서치는 주어진 범위 내에서 원하는 값을 찾아내는 알고리즘이다. 파라메트릭 서치는 최적화 문제를 풀 때 유용하게 쓰일 수 있다. 범위 내에서 조건을 만족하는 최대값, 혹은 최소값을 찾으려고 할 때,이진 탐색을 활용해서 범위를 좁혀가면 최적화 문제를 결정 문제로 바꾸어서 문제를 풀어나갈 수 있다.

이진탐색은 반드시 정렬된 배열에서만 사용 가능한 점에 주의하자.이진탐색은 순차 검색이며 시간복잡도는 O(log N)이다. 다음은 파이썬으로 구현한 코드이다.# arr : 정렬된 리스트# target: 찾고자 하는 값# start : 배열의 처음# end : 배열의 마지막# binary_serach 함수의 반환값 : target의 인덱스def binary_search(arr, target, start, end): if start > end: return None mid = (start + end ) // 2 if arr[mid] == target: return mid elif arr[mid] > target: end = mid ..

브루트포스 알고리즘은 완전탐색알고리즘의 하나이다.해가 존재할 수 있는 모든 경우의 수를 탐색하는 방법으로 '무식한' 알고리즘이라고도 할 수 있다. 브루트 포스의 구현 방법으로는 다음과 같은 것이 있다.순차 탐색 - 선형 구조를 전체적으로 탐색깊이 우선 탐색(DFS)  - 비선형 구조를 전체적으로 탐색너비 우선 탐색(BFS)  - 비선형 구조를 전체적으로 탐색백트랙킹(backtracking) - 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법  브루트 포스의 장점 - 예외가 없이 100%의 정확성 - 알고리즘의 설계와 구현이 간단 브루트 포스의 단점  - 메모리를 비효율적으로 사용  - 실행시간이 길다(시간복잡도가 높음)  >>> 백준의 1436번의 '영화감독 숌' 문제도 브루트..

유클리드 호제법 (연제법, Euclidean algorithm)A = Bq + RG(A, B) = G(B, R)A와 B의 최대공약수와 B와 R의 최대공약수가 같다.두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (단, a > b)a와 b의 최대공약수는 b와 r의 최대공약수와 같다.>> 이를 이용해서 a를 b로 나눈 나머지 r를 구하고, 다시 b를 r로 나눈 나머지를 구하는 과정을  나머지 r이 0이 될 때까지 반복하면 마지막의 b가 a와 b의 최대공약수가 된다.  def gcd(a, b): while b: a, b = b, a % b return a print(gcd(a, b))

https://travelbeeee.tistory.com/451 [알고리즘] 비트마스킹(bitmasking) 이란안녕하세요, 여행벌입니다. 오늘은 2진수 표기법의 특징을 활용한 비트마스킹 알고리즘에 대해서 포스팅해보겠습니다. [ 비트마스킹 ] 컴퓨터는 내부적으로 모든 자료를 이진수로 표현합니다. travelbeeee.tistory.com🩵1 🩵집합연산도 가능