우주수첩의 우주먼지

해시키에 대응되는 값을 저장하는 자료구조시간 복잡도 : Insert, Erase, FInd, Update 모두 O(1) 해시함수 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 충돌 해결 방안충돌은 해시에서 가장 큰 애로사항으로 해결 시 성능에 큰 영향을 미치기에 해결하면 나이스1. Chaining각 인덱스마다 연결리스트를 하나씩 두는 것.삽입 : 발생 시 연결리스트에 값을 추가.탐색 : 인덱스를 찾아 해당 연결리스트 내에서 특정 값에 대한 탐색을 재 실행시간복잡도 : 이상적 : O(1) /  최악 O(N) => 각 키의 해시값이 균등해야 성능 굳굳 2. Open Addressing각 인덱스에 (키,값)쌍을 저장삽입 : 충돌 예상 시 다음 인덱스에 값을 저장탐색 : 인덱스에 해당하는 키값이 ..

백트래킹이란?- 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모노드로 돌아가 다른 자식 노드를 찾는 방법.❗️즉, 모든 경우의 수를 찾아 보지만 그 중에서도 가능성 있는 경우의 수만 찾아보는 것을 의미❗️  백트래킹 vs dfs vs 브루트포스 1. 브루트 포스- 모든 경우의 수를 찾아본다.- 장점 : 만족하는 값을 100% 찾아냄- 단점 : 조합 가능 경우의 수에 따라 필요 자원 크기가 커 질 수 있음. 2. 백트래킹 - 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단.- 장점 : 탐색에 불필요한 자원을 줄일 수 있다. (브루트 포스의 단점 보완) 3. dfs - 백트래킹에 사용되는 대표적인 탐색 알고리즘❗️ 백트래킹의 방법 중 하나가 dfs임 ❗️

배열이 주어졌을때 maximum subarray 를 찾고자 한다. 본인의 경우 배열 내에서 가장 큰 값이 지속되는 구간을 찾아아 시작 인덱스와 종료 인덱스를 추출해야 했다. 시간 복잡도 O(N) 개념 각각의 최대 부분 합은 이전 최대 부분 합이 반영된 결과이다. 이전 인덱스가 가질 수 있는 최대 부분 합에 현재 인덱스 값을 더하면 현재 인덱스가 가질 수 있는 최대 부분 합을 구할 수 있음을 의미한다. 방법 각각의 인덱스 값은 이전 인덱스가 갖고 있는 최대 부분 합을 연장할지 아니면 자신의 값으로 초기화 할지 선택한다. 연장 이전 인덱스의 최대 부분합 + 현재 인덱스의 최대 부분 합 > 현재 인덱스 값 Math.max(A[i],A[i] + A[i-1]) 적용 코드 public AvailableSchedul..

중고등학생때 해보고 냅다 까먹어 버린 최대공약수와 최소공배수를 다시 리마인드 하러 왔.땨. # gcd(a,b) : greatest commom divisor 두 integer a,b에 대하여 a,b의 공통된 factor들 중 최대값을 뜻한다. ex) gcd(30,12) =6 #lcm(a,b) : lowest common multiple 두 integer a,b를 모두 factor로 가지는 수들 중 가장 작은 수 ex) lcm(30,12) = 60 # 관계 성립 # Theorem non-zero integer a,b에 대해 아래 statement들이 성립한다. gcd(a,b)=gcd(b,a) if a>0, and a|b, -> gcd(a,b)=a if a≡c(mob b) -> gcd(a,b)=gcd(c,b..

이전 포스팅 https://dusty-wznt.tistory.com/85 에서 Prime에 대해 다뤘고 그와 동시에 에라토스 테네스의 채의 원리를 너무나도 완 벽 하 게 이해를 해버렸.땨. # 에라토스 테네스의 체 주어진 integer x가 prime인지에 대한 여부를 쉽게 판별할 수 있도록 processing 해주는 알고리즘. prime 여부는 크기가 n인 array에 저장되며 (이해를 돕기 위해 sieve라고 하겠다. sieve == 체) i>2에 대하여 sieve[i] ==0이면 i는 prime이고 sieve[i]==1이면 i는 !prime이다. 이처럼 배열은 해당 index가 prime인지에 대한 여부를 저장한다. 여기서 에라토스 테네스의 채를 구현할 때 key idea가 될 조건은 앞서 포스팅 ..

거 참 제목 하나 영어로 썼다고 간지나는 거 보소. 이전에 에라토스 테네스의 체를 포스팅 한 적이 있다. https://dusty-wznt.tistory.com/19?category=1061713 이때는 그냥 코드 구현만 하고 자세한 설명이 없었는데 수업을 듣다가 원리를 깨달아 버렸다. 만약 N이 prime이 아니라면 두 positive integer a,b >1에 대하여 n=a*b로 나타낼 수 있다. 이 경우 a or b는 반드시 √n 을 넘지 않는다. bool prime(int n){ if(n

#include #include using namespace std; #define NUMBER 12 int tree[4 * NUMBER]; // 4를 곱하면 모든 범위를 커버할 수 있다. 개수에대하여 2의 제곱 형태의 길이를 가지기 때문...이라는데 머지? int A[] = { 1,9,3,8,4,5,5,9,10,3,4,5 }; // 구간 합을 구하고자 하는 리스트를 저장한다. void build(int node, int start, int end) { if (start == end) { tree[node] = A[start]; } else { int mid = (start + end) / 2; // 재귀로 두 부분으로 나눈 뒤에 그 합을 자기 자신의 합으로 한다. // 처음 시작은 build(!,0,n..

# Min Cut Problem == vertex patitioning Source s, sink t를 가진 directed graph G =(V,E)에서 s-t cut (s∈S, t∈T)를 만족하는 vertex들의 partition(S,T)으로 정의한다. 한 partition은 무조건 source만, 다른 한 쪽의 partition은 무조건 sink만 포함. 한 partition에 sink 와 source를 모두 포함할 수는 없다. s-t cut의 capacity C(s,t)는 u∈S, v∈T를 만족하는 모든 edge의 capacity의 총 합으로 정의한다. 시작 vertex는 source에서, 종료 vertex는 sink에서 존재해야 한다. # Max-flow & Min cut theorem Dire..

# Ford-Fulkerson Algorithm Max-Flow 문제를 해결할 수 있는 대표적인 알고리즘이다. 주어진 그래프 G와 현재 Flow f로 정의되는 잔여 그래프(residual graph) Gf를 이용해서 해결된다. # Residual graph 초기화 G의 vertex와 edge를 모두 G0로 copy한다. G0의 edge 중 one-way-path edge를 edge(v,u)를 G0에 추가한다. 이때 edge(v,u)의 capacity는 0으로 정의한다. one-way-path : edge(u,v)는 있으나 edge(v,u)는 없는 경우 2번의 작업상태에 있는 그래프를 G'이라고 칭할 예정이다. #Augumenting path : 증가 경로 G'의 source 에서 sink 까지 가는 pa..

# 네트워크 플로우 (Network Flow) - 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지를 측정하는 알고리즘 # 필요 용어 정리 capacity (용량): edge가 수용할 수 있는 값 flow (유랑) : 실질적으로 보내는 값 source : indegreee가 0인 vertex sink : outdegree가 0일 vertex (수첩의 개입) 이라고 정의하기에는 너무 두루뭉실 뜬구름이 뭉게뭉게여서 다시 설명을 하자면 육상 트랙의 라인 수 == capacity 트랙에서 한 번에 뛰어야 하는 선수의 수 == flow 라고 생각하면 앵간 편하지 않을까 싶기도 한댱 ㅇㅅㅇ... 뭔가 일반화된 그래프의 시각으로 봤을 때 start 점이 source / finish 지점이 sink라고..