초콜릿 파워

오랜만에 돌아온 알고리즘 공부 시간! 세그먼트 트리의 필요성 A1, A2, … AN 의 수열이 있을 떄, L, R을 입력 받아서 AL 부터 AR 까지의 수열의 합을 구하라. → 이런 쿼리가 있다면, 누적합을 이용해서 sum[R] - sum[L-1]을 통해서 쉽게 구할 수 있을 것이다. → 하지만, 이렇게 누적합을 구하는 과정에서 중간에 수열의 값이 변한다면, 각각의 누적합에 대해 연산을 실시해야하므로 O(N) 의 시간복잡도가 걸린다. → 이러한 연산을 효율적으로 실행할 수 있게 해주는 기법이 세그먼트 트리 기법이다. 세그먼트 트리란 각 노드는 특정 구간을 대표한다. 노드들은 이진트리 구조를 이룬다. (부모 노드가 대표하는 구간은 자식 노드가 대표하는 구간의 합집합이다. ) 총 길이는 2^k 꼴일 때, 비..

LIS를 lower_bound로 해결하는 가장 효율적인 알고리즘이 있음에도 불구하고, 이 알고리즘을 쓰게 된 이유를 알지 못하는 사람들이 많다. 그저 효율적이라는 이유만으로 이 알고리즘을 사용한다면, 그 배경을 알지 못해 응용도 할 수 없을 뿐더러 사용할 때마다 가슴이 답답함을 느끼게 될 것이다.. (나는 이런 걸 왜 생각하지 못할까.. .) 그래서 이 알고리즘이 등장하게 된 배경에 대해서 설명해보려고 한다. (답답해서 공부했다.) 먼저 동적 프로그래밍으로 알고리즘을 설계하는 방법에 대한 것이다. * 동적 프로그래밍 : 앞으로 푸는 문제에 대해 이전의 데이터를 활용할 수 있다면 cache에 저장하여 사용한다. 푸는 방법: https://ebang.tistory.com/89 동적 프로그래밍을 짜기 위해 수..

c++ 자료형의 프로모션 사칙연산이나 대소 비교 등의 이항 연산자들은 두개의 피연산자를 받는다. 만약 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 이들을 같은 자료형으로 변환해서 계산하고 이를 프로모션이라고 한다. c++에서 적용되는 규칙은 다음과 같다. 한쪽은 정수형이고 한쪽은 실수형일 경우: 정수형이 실수형으로 변환된다. 양쪽 다 정수형이거나 양쪽다 실수형인 경우: 넓은 범위를 갖는 자료형으로 변환된다. 양쪽 다 int형보다 작은 정수형인 경우: 양쪽 다 int형으로 반환된다. 부호 없는 정수형과 부호 있는 정수형이 섞여 있을 경우 : 부호 없는 정수형으로 변환된다. 연산 될 때 원하지 않는 값이 나오지 않는다면, 조심하도록 하자!

최단경로를 다익스트라로 풀고 있을 때, 그 경로도 구해야 하는 경우가 있다. (백준 #5719 거의 최단경로 문제, k번째 최단경로 등) 이럴 때는 어떻게 경로를 저장할 수 있는지 알아보았다. 다익스트라의 진행과정은 다음과 같다. 1. distance[S] 3, 0->4 로 갈 때 모두 갱신이 되고, 모든 경로가 최단경로로써 저장이 될 것이다. - 나중에 최단경로가 아님을 알고 지울 방법이 있는가? -> 알수가 없다. - 나중에 최단경로였음을 알고 되돌아 갈 수 있는 방법은? -> 직전노드를 저장해준다면? -> 갱신될 때마다 방문된 각 노드마다 직전노드를 저장한다면, 마지막에 종료되었을 때의 노드를 기준으로 직전노드로 되돌아가면(일명 벡트래킹) 그것이 최단경로일 것이다! 이러한 사고흐름을 통해, 최단경로..

1. 크루스칼 알고리즘 최소 신장 트리를 구하는 알고리즘 중 하나이다. 1. 유니온 파인드 연산을 필요로 한다. 유니온 파인드 보러가기 >> 2.트리 그래프 : 순환을 갖지 않는 연결 그래프. 임의의 두 정점에 대해서 경로가 정확히 1개 존재함. 하나 이상의 정점을 가지며 임의의 간선 e를 제거한 그래프는 연결 그래프가 아니다. (연결 그래프: 모든 정점들을 간선을 통해방문할 수 있는 그래프 : 임의의 v, u 정점에 대해 path(v,u)가 존재하는 그래프) - 느낌: 그래프를 최소한의 간선으로 모두 연결해서 이동가능 할 수 있게 만든 것이되 사이클이 없는 것. - 특징: 전체 노드의 개수가 N개일때, 트리를 만들고 나면 전체 간선의 수는 N-1개가 된다. (1개의 경로로만 이루어져 있기 때문에) 3...

1. 플로이드 워셜 - 임의의 한 지점에서 다른 임의의 지점까지의 최단 거리를 구하는 알고리즘 (모든 지점에 대해 구할 수 있음: dist[V][V]) - 중간 지점을 통해서 최단거리를 갱신하는 알고리즘 - O(N^3)의 시간 복잡도: 3중 for문 - 사용가능한 시점: 시간 초과 제한에 걸리지 않을 때( 정점의 수가 약 500개 이하정도) - 다이나믹 프로그래밍 사용 : dist[i][j] = i에서 j 로 가는 거리라고 할 때, i -j의 최단경로가 i-k-j라면 i-k와 k-j도 최단경로이다. 점화식: dist[i][j](최단) = dist[i][k] + dist[k][j] - code for k

1. 유니온 파인드(Union Find) - 서로소인 집합들의 정보를 확인(find)하고 조작(union)할 수 있는 자료구조. - Union 연산 : 서로소인 집합을 '유니온' 연산을 통해서 같은 집합으로 만들 수 있다. - Find 연산 - 두 원소가 같은 집합에 속해있는지 확인할 수 있다. - 메쏘드 1. init - parent[N] 배열을 모두 자기 자신으로 초기화. 2. find - 루트를 반환하는 함수 - 재귀적으로 짤 수 있음 : 부모가 자신 일 때 종료. - 경로 압축: 변수에 결과를 반환받은 뒤, parent 를 갱신 후 다시 return 3. union - 두 원소를 받아서 한 집합으로 만드는 함수 - C++의 경우 union이라는 이름은 이미 있어서 다른 함수 이름으로 설정. - a..