Algorithm

Python으로 코딩을 하다보면 간결한 표현, 또는 인자로 만들기 위해서 Nested list를 종종 사용한다. list를 3개를 만들어서 관리할 바에야, 한개의 리스트에서 tuple로 3개의 인자를 포함하게 해서 인덱스로 접근하면 간편한 일이기 때문이다. 그런데, n

BJ_4792Disjoint set 문제를 공부하는 중이다. 제법 simple한 방법이라고 생각하는 응용 범위가 넓고 정형화 되어 있지 않아 제법 어려운 문제들이 많이 등장한다. disjoint_set으로 문제를 계속 풀어가다가 발견한 이문제, 뭔가 disjoint_

잊어 버릴만 하면 나오는 문제 때문에, 계속 찾아보게 되어서 정리해 본다. 아, 그리고 이 사이트는 참고가 많이 된다. https://tempdev.tistory.com/20 Binary Indexed Tree 기본 형태

구조의 범위로 보았을 때, Tree는 Graph에 포함되는 개념그래프: 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료구조, 연결된 노드 간의 관계를 표현할 수 있는 자료 구조특징:그래프는 순환 혹은 비순환 구조를 이룸그래프는 방향이 있는 그래프와 방향이

모듈러 연산의 경우 + - * 에 대해서 비교적 자유롭게 사용해 봤다. 아래와 같은 성질을 만족하기 때문이다. 1) (A+B)%C = (A%C + B%C)%C 2) (A-B)%C = (A%C - B%C)%C 3) (AxB)%C = (A%C x B%C)%C 분배 법칙

스털링 수는 위키 피디아 에서 아래와 같이 정의 되어 있다. 조합론에서 스털링 수(Stirling, Stirling number)는 조합론에서 자주 등장하는 두종의 정수열이다.제 1종 스털링 수와 2종 스털링 수가 존재하는데, 부호 없는 제 1종 스털링 수는 n개의 원

유클리드 호재법을 이용한 최대공약수와 최소공배수는 아래와 같이 구할 수 있다. 알아두면 피가 되고 살이 될지니 받아 들일 지어다. 최대공약수 최소공배수

$$A^{b}$$ 의 간단한 해결법은 A를 b번 곱하는 것이다. 하지만, O(n)의 시간으로 풀기 어려울 크기가 b로 주어진다면?아래의 두가지 방법으로의 접근이 가능하다. 둘 다 O(nlogn)접근이 가능하게 해주는 방법들이다. 1) 분할 정복 이용2) 이진수 응용

피사노 주기: 피보나치 수를 K로 나눴다고 했을 때, 그 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라 함.피사노 주기를 P라고 했을 때, N % M == (N % P) % M 또한 $$M = 10^{k}$$ 일 때 k>2라면 주기는 항상 $$15\*10^{k

이항 계수: n개 중에 k개를 순서 없이 고르는 방법 : $${n}C{m}$$ 또는 $$n\\choose m$$ = $$n!\\over k!(n-k)!$$ 으로 쓴다.Pascal's Triangle: Cn = Cn-1 + Cn-1, 여기서 Cn는 $n\\choose k

특정한 정점에서 다른 모든 정점으로 가는 최단 거리를 구할 때 사용하는 알고리즘 중의 하나최단 거리는 여러개의 최단 거리로 이루어져 있다. (다이내믹 프로그래밍)특징: 1) 간선의 가중치(weight)가 음수이면 적용 불가능 함2) 시작점의 위치가 정해져 있을 경우에

DAG(Directed Acyclic Graph): 사이클이 없는 방향 있는 그래프위상 정렬(Topological Sort): 그래프의 간선 u → v에서 v를 선행하기에 앞서 u를 먼저 수행해야 한다는 의미에서 봤을 때 정점의 순서를 찾아주는 알고리즘 : 보통 위상정

스패닝 트리 : 그래프에서 일부 간선을 선택해서 만든 트리 : 스패닝 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안됨 ( 트리의 정의가 사이클 없이 모든 정점이 연결되어 있는 그래프) : 스패닝 트리는 그래프에 있는 n개의

최단 경로: 시작점이 1개 일 때, 다른 모든 곳으로 가는 최단 경로 구하기: A → B 로 가는 최단 경로는 최대 N-1개의 간선으로 이루어짐 (중요한 성질): 최대 N-2개의 정점을 포함하되, 같은 정점이 존재할 수 없다. (같은 정점이 존재하면 최단 경로가 될 수

Floyd Warshall 알고리즘: 모든 쌍의 최단경로를 구하는 알고리즘: 다익스트라와 bellman-Ford의 경우는 시작점이 1개일 때 구하는 알고리즘: 다익스트라와 벨만포드를 v번 반복하면 같은 결과를 얻을 수 있다.: 장점은 코드가 간단하는 점: 코드는 dp로

메모리 영역은 다음과 같이 구분 되어 있고, < 하위 주소 ------> 상위 주소 >< 정적 할당 영역 >

아래 코드를 보고 문제점이 무엇인지 알 수 있는가? C 코드의 정수형 int의 범위는 다음과 같다. 4 Bytes를 기준으로 하여, 아래의 범위에 해당한다. 대략 -20억에서 20억까지.int 범위 (4 Bytes) : –2,147,483,648 ~ 2,147,483,

수 많은 종류의 정렬 알고리즘이 존재한다. 하지만 비교적 많이 사용되는 기법은 병합정렬(Merge Sort)과 퀵정렬(Quick Sort) 정도다. 정렬 알고리즘 시간 복잡도 비교 병합정렬은 Best, Average, Worst case 모두 O(nlogn)을 보장

Array 배열을 rotating 하는 문제는 심심치 않게 기본 동작으로 처리하는 문제가 나오는 경우가 많다. Python을 이용하면 zip operation을 통해서 array rotating 원리를 파악하지 않고도 비교적 쉽게 구현이 가능하다. 나중에 구현할 때 참