본문 바로가기

Algorithm

 (9)
long long과 int 차이점 정수 자료형 int는 32/64비트 환경에 상관없이 4바이트의 정보를 기록할 수 있는 자료형이다. signed int(부호가 있는 정수)를 기준으로 기록할 수 있는 양의 정수 범위는 0 ~ 2,147,483,647(16진수로 7FFFFFFF) int로 계산할 수 있는 범위를 넘어서는 문제가 있을 수 있다. (산술 넘침 혹은 Overflow) 4바이트의 저장 공간만으로는 좀 더 큰 정수를 계산할 수 없게 되었고, 점점 커져가는 메모리 공간, 계산량에 어느 정도 대비할 필요가 있게 되었다. long long은 8바이트의 공간을 가지는 자료형이기에 signed long long을 기준으로 하면 최대 계산할 수 있는 양의 정수 범위는 0 ~ 9,223,372,036,854,775,807(16진수로 7FFFFFF..
[Algorithm] brute force, 시간복잡도 문제풀이 고려사항 1. 제한된 메모리와 시간 2. 알고리즘 시간복잡도 문제에서 제시된 입력의 크기와 프로그램의 수행시간과의 관계를 나타내는 함수 Big-O(빅-오) : 상한 점근 (가장 느리게 실행될 때)을 이용해서 시간복잡도 표현 간단하게 생각하면 최고차항의 차수 또는 지수의 밑이 중요하다 1초 = 10^9 Bruteforcing 모든 경우의 수를 확인해보는 방법 빠른 입출력 - main 아래에 구문 적기 cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); - 이 경우 scanf, printf 혼용 X cin, cout만 사용하기 - endl(버퍼를 비운다)대신 개행문자 '\n' 사용하기 1) 블랙잭 BOJ 2798 주어진 배열에서 M을..
[Lecture] SCC SCC : Strongly Connected Component Connecte Component는 undirected graph에서 존재한다 SCC는 directed graph에서 임의의 두 정점에 대해 양방향으로 가는 경로가 모두 있을 때, 존재한다 즉, 모든 노드가 양방향으로 reachable한 노드의 최대한 키운(Maximal Subset) 집합이다 //SCC는 사이클이 한 개 이상 겹쳐진 형태를 띤다. 하나의 정점도 SCC가 될 수 있다 [참고] Directed graph : 문제를 해결한 알고리즘이 나왔을 때, 같은 방향으로 undirected graph에도 적용시켜 해결할 수 있다 Undirected graph : undirected graph에서 해결한다고 해서 directed graph가 ..
[Lecture] BCC Biconnected Component (maximal set) Biconnected Graph : 임의의 한 노드를 제거해도 나머지 모든 노드들이 연결되어 있는 그래프이다. 따라서 biconnected graph에는 cv가 존재하지 않는다 (무방향 그래프에서 정의되는 개념이다) Biconnected Component : cv에 의해 끊어진 그래프들의 각 부분을 의미한다 BCC 내의 임의의 두 노드는 완전히 다른 (edge와 node가 겹치지 않는다) 2개 이상의 경로가 존재한다 cv가 있으면, 그래프 전체가 BCC가 아니다(정의와 모순됨) 기본적으로 cycle을 BCC라고 한다 cv가 있었는데, 사라지면 연결이 끊기는 것이므로 BCC상태가 아니다 * cv는 여러 BCC에 걸쳐있다 * cv가 아닌 노드는..
[Lecture] Cut Vertex Cut Vertex 전제 : 전체가 연결된 graph가 있다고 했을 때 (일부분을 봐도 되지만, 여기선 그냥 전체를 전제로 한다) Cut vertex를 버리면, graph가 disconnected graph가 된다 x와 y가 존재한다고 하자 x에서 y로 가는 모든 path가 s(Cut vertex)를 통해서 간다 그래프에서 Cut Vertex를 어떻게 찾을 수 있을까? - 노드를 하나씩 빼보면서 disconnected graph가 되는지 확인한다 각 노드(N)에 대해 DFS를 한다(M+N) = O(N(M+N)) = O(MN) Cut Vertex => cv로 대체한다 Idea1 child가 하나일 땐, parent는 cv가 아니다 왜냐하면, 하나의 노드가 사라진다고 해도, connected graph를 유..
[Lecture] Graph Traversal 특정 노드(x) 하나가 없어지면, 그래프가 끊어질 때, 특정 노드(x)를 구하는 방법은 무엇일까? 방향이 없으면 힘들어진다 다익스트라는 소스에서 가까운 것부터 방향을 만들어가면서 해결한다 보통 방향을 정한 다음에 늘려가면서 구한다 local과 global 정보가 섞여 들어오면서 문제를 풀게된다 다익스트라에선 빨간색이 최종답이었다 위 그림에서 30 입장으로 인접한 노드들을 바라봤을 때, 35,38,40이라는 정보를(local)알 수 있다 global 정보는 파란 것 중에서 가장 작은 것을 뽑는 것이다 global정보가 간단할수록 쉽게 풀린다 다익스트라는 traversal로 볼 수 있다 Traversal어떤 순서에 따라 그래프의 노드를 방문한다 일반적으로, 해당 노드에서 연산을 하면 방문했다고 표현하고, 지..
[Lecture] Greedy Algorithms, Minimum Spanning Tree Greedy Algorithm 답을 찾기 위해 선택을 반복하는 알고리즘들 중 비교적 간단한 방법으로 선택하고, 선택한 후 바꾸지 않는 알고리즘이다 selection sort도 가장 작은 숫자를 맨 앞으로 보내고 뒤돌아보지 않기 때문에 greedy이다 shortest path는 보통 greedy algorithm으로 문제를 해결한다 (edge weight = 비용) 노드가 n개이면, edge는 n-1개이다 shortest path는 결국 edge n-1개를 구하는 문제이다 Greedy Algorithm은 항상 해결 가능한 알고리즘인가? Minimum Spanning Tree 모든 노드를 포함하는(span:덮다) 트리를 찾는데 비용이 최소화되도록(minimum) 하는 것이다 Prim Algorithm 1. ..
[Lecture] Sum, Binary Search, Selection Sort A Simple Code & A Simpler Code 첫번째 그림: 일반적으로 누적합을 구할 수 있는 코드 두번째 그림 : 재귀로 누적합을 구할 수 있는 코드 두번째 그림의 코드가 맞는지 증명해보자 수학적 귀납법 : sum(x)는 1+2+...+x를 항상 리턴한다 base: P(1) 즉, 코드에 1을 넣었을 때 return값은 1이다 따라서 sum(1)이 리턴하는 값은 1임을 알 수 있다 step: 코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴한다 sum(x-1)의 리턴값은 1+2+...(x-1)와 같다고 할 때, sum(x)는 1+2+....+x를 리턴한다는 것을 확인할 수 있다 Binary Search & Recursive Binary Search 시간 복잡도 : O(n) (첫번째 코드..

티스토리툴바