우주수첩의 우주먼지

백트래킹이란?- 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모노드로 돌아가 다른 자식 노드를 찾는 방법.❗️즉, 모든 경우의 수를 찾아 보지만 그 중에서도 가능성 있는 경우의 수만 찾아보는 것을 의미❗️  백트래킹 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라고..

Dynamic Programing recursion + Memoization 단순 테이블 채우기가 아니라 memoization을 이용해서 recursion을 smart하게 하는 기법. # 문제해결 절차 문제를 정확하게 정의하기. 정의된 문제에 대한 subproblem을 생각한 뒤 이를 이용해 reccurence relation을 세운다. A(i)를 해결하기 위해서 이전단위의 subproblem의 solution으로 현재 해결하고자하는 식을 논리적으로 구한다. memoization을 이용하여 recurrence relation 계산 중간 결과물들을 저장할 data structure을 고른다. 대개 n차원 array 사용. Subproblem들간의 dependency를 확인한다. (보통 top-down | ..