one Book a Day

비트마스크(bit mask) 비크마스크란 무엇인가? 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술. 집합에서 하나의 원소는 하나의 bit로 표현(꺼져있다, 켜져있다.) ex switch_states = [True, False, False, True, True, False, False, False, True, True] switch_states = 0b1001100011 # 611, python에서는 앞에 '0b'를 붙여 이진수 표현 가능 정수형으로 표현하면 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐 더 간결한 코드 작성이 가능 더 빠른 연산이 가능 더 작은 메모리의 사용. 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함. (중요) 위와같은 장점이 ..

이진트리?? 최대 두개의 자식 노드를 가지는 트리형태의 자료구조. 단순 저장보다는 탐색혹은 정렬을 위함. 힙도 이진트리의 일종. 이진 탐색트리? 이진트리의 특수한 경우. 모든 노드에 대해 그 왼쪽 자식들의 값이 현재 노드보다 작거나 같으며 오른쪽 자식들의 값이 현재 노드의 값보다 크다는 조건을 만족하면 이진 탐색 트리가 된다(작은값은 왼쪽 큰값은 오른쪽에 저장.) 가장 처음 입력된 값이 root 클래스 정의, 초기화 노드 클래스 정의 class Node(object): def __init__(self, data): self.data = data self.left = self.right = None 이진 탐색 트리 클래스 정의 class BinarySearchTree(object): def __init__..

최단 경로 알고리즘. 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알고리즘 (Dijkstra Algorithm) 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm) 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 전체 쌍 최단 경로 문제, 다수출발, 단일도착 하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 A*알고리즘이 적합하다. 다익스트라 특정 노드에서 다른 모든 노드로 가는 최단경로를 갱신. 음의 간..

에라토스테네스의 체 란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 소수 구하기 n=100 def isPrime(a): if(a 소수의 배수들을 배제하는 방법으로 남는 소수를 가져갈 수 있지 않을까? 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당..

뜬금 정렬 정리. 최근 문제풀이에 열중하다보니 다시한번 기본서를 보고싶은 느낌이 들어 정리. 버블 정렬 O(n^2) def bubbleSort(lst): LEN = len(lst) for last_idx in range(LEN-2, 0, -1): # 각 턴의 마지막 인덱스 isSwap = False # 최적화 for l_idx in range(0, last_idx+1): if lst[l_idx] > lst[l_idx+1]: lst[l_idx], lst[l_idx+1] = lst[l_idx+1], lst[l_idx] isSwap = True if not isSwap: # swap이 일어나지 않았으면 정렬 완료상태 return lst return lst 나랑 내뒤에랑 비교해서 큰게 뒤로감. 여러번 순회해서 ..

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 양의 가중치만이 있는 그래프만을 취급 특정 위치에서 도착위치의 최단경로를 찾는 알고리즘(모든경로의 최단경로를 구하지는 않는다. 그리디하게 정점을 선택해 방문. 선택한 정점의 인접정점 중 방문되지 않은 것들에 대해 최단경로를 구해가며 도착지점에 도달. 배열에 각각 노드에 접근 시 가중치 합을 저장하며 지나간다. 0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다. 현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다 1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다. 이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 ..

최소 신장 트리(MST, 크루스칼, 프림 알고리즘) 최소 신장 트리(Minnimum Spanning Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. 신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고, (n-1)개의 간선으로 연결 되어이으면 필연적으로 트리형태가 되고 이게 신장 트리이다. 즉 그래프에서 일부 간선을 선택해서 만든 트리. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 ..

말 그대로 큰 문제를 재귀적으로 쪼개어 나간 다음 하위문제들의 결과를 조합 해 원래 문제의 결과를 도출하는 방식. 분할 -> 정복 -> 조합 3단계로 이루어지며 대표적으로 병합 정렬 알고리즘을 볼 수 있다. def F(X): # 정복 if F(X)가 간단해졌을 때: return F(X)계산값(int or list or str) else: # 분할 X를 left와 right로 분할. F(left)와 F(right)를 호출 # 조합 return F(left)와 F(right)로 F(x)를 구하는 관계식(재귀) 추후 최적 부분구조(Optimal Substructure)에도 연관 됨. 예제로 연산 문자열이 들어갔을 때 괄호를 치는 경우의 수에 따른 계산값 리스트를 구하는 함수. 각 연산자를 만남에 따라 좌우를 ..

유니온 파인드 = 디스조인트 셋(disjoint set) = 머지 파인드 셋(merge find set) 디스 조인트 셋은 서로소 집합(교집합이 공집합인 집합) 많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. A와 B 사건 중 둘이 동시에 일어날 수 없고 둘 중 하나만 일어나야 한다. = 두 사건 중 하나의 사건이 일어날 확률이 두 사건이 각각 일어날 단순 확률의 합 과 같다. (P(A)가 일어날때 P(B)가 0이기 때문) P(A or B) = P(A) + P(B) //상호배타적이 아닌 독립적 관계는 A,B의 교집합이 없는 것은 동일하나 A,B동시에 일어나도 상관없음. 구현에는 Union, Find가 존재. 부분 집합들은 트리로 표현 할 수 있고, 파인드를 통..