느낌표 공장

비트마스크란 ? 비트마스크(Bit Mask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. 보통 어떤 비트가 1이면 "켜져 있다" 라고 말하며, 0이면 "꺼져 있다" 라고 말한다. 비트마스크의 장점 수행 시간이 빠르다. 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 이는 연산 횟수가 늘어날수록 차이가 매우 커지게 된다. 코드가 짧다. 메모리 사용량이 더 적다 ★ 예를 들면, bit가 10개인 경우에는 각 bit당 두 가지 경우를 가지기 때문에 2¹⁰ 가지 경우를 10bit 이진수 하..

Dijkstra 알고리즘이란 ? 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 음의 간선이 존재하지 않는, 간선의 값이 0 이상의 양수일 때 정상적으로 동작한다. 우선 순위 큐(heapq)를 사용한다. 동작 원리 단계 인접 리스트를 만든다. 최단 거리 테이블을 무한대의 값으로 초기화한다. 현재 노드에서 갈 수 있는 노드 다 가져온다. 현재 노드에서 다음 노드로 가는 간선 비용을 계산하여 가중치 테이블을 업데이트 한다. 3번과 4번을 반복한다. 문제 SWEA - 5251. 최소이동거리

Union-Find 란? Disjoint Set을 표현할 때 사용하는 알고리즘 그렇다면 Disjoint Set(서로소 집합, 상호 배타 집합) 이란 ? 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다. 집합에 속한 하나의 특정 멤버(root node)를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호 배타 집합을 표현하는 방법 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연결 리스트보다 효율적이다. 연결 리스트 같은 집합의 원소들은 하나의 연결 리스트로 관리 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다. 상호 배타 집합 연산 m..

Dynamic Progamming? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 원리 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그 문제를 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 언제 사용할까 ? 최적화 문제 경우의 수 구하기 과정 문제를 부분 문제로 분할한다. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다. ✔︎ Memoizat..

DFS(Depth-First Search) : 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택 자료구조 혹은 재귀 함수를 이용한다. ✔︎ 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 수행한다. ✔︎ 깊이 제한 : 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위함이다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다...

에라토스테네스의 체(Eratosthenes' sieve ) 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법이다. 에라토스테네스의 체 알고리즘 1. 1부터 n까지의 자연수를 전부 나열한다. 2. 소수도, 합성수도 아닌 1을 지운다. 3. 남아 있는 자연수 중 가장 작은 수인 2 의 배수들을 모두 지운다. 4. 남아 있는 자연수 중 가장 작은 수인 3의 배수들을 모두 지운다. 5. 남아 있는 자연수 중 가장 작은 수는 소수다. 이 수의 배수들을 모두 지운다. 6. 남은 자연수 중 가장 작은 수가 n의 제곱근을 넘을 때까지 과정 5를 반복하면, 남아 있는 수가 모두 소수다. 코드로 표현하기(Python) number = [False, False] + [True] * n answer = ..