알고리즘4 [BOJ] 2094 수학은 너무 쉬워 전혀 쉽지 않은 문제였다. 각 값을 소인수분해 한 결과를 vector에 저장하고, 해당 소인수분해 결과를 종합해서 입력된 값들이 가질 수 있는 최대공약수를 구하고, 각각의 값들이 해당 최대공약수를 만족하기 위해 필요한 값의 갯수를 찾아서 합치면 된다. 어찌보면 그냥 수학 문제인데, 생각보다 많이 어려웠다. #include #include #include #include #include using namespace std; int numbers[101], N, sieve[1001]; vector datas[101]; map sum; pair dummy; void print_vector(){ for(int i = 0 ; i < N; i++){ vector target = datas[i]; printf("%d.. 2020. 4. 24. [BOJ] 11562 백양로 브레이크 이 문제는, 주어진 두 지점에 대해서 '최소 몇번 역방향 다리를 새로 놓아야 접근할 수 있는지' 에 대해 묻는 문제이다. 뒤집어서 생각하는 것이 관건이다. 길이 없는 경우 거리를 무한대, 양방향 길이 있는 경우 거리를 0, 단방향만 있는 경우는 길이 없는 방향에 대해 1 값을 부여한다. 그 후, Floyd-Warshall 알고리즘을 적용하면, 모든 Path에 대해 최단거리로 이동하기 위해 설치해야 할 다리의 갯수가 나온다. #include #include using namespace std; const int INF = 1 2020. 4. 14. [2] Floyd-Warshall 알고리즘 플로이드 워셜 알고리즘은 그래프에서 "All-pair-shortest-path" - 정점들의 모든 쌍의 최단 경로의 길이를 구하는 알고리즘이다. 그래프 알고리즘 중 가장 단순한 알고리즘이라고 생각된다. Brute-Force랑 거의 같다고 볼 수 있기 때문이다. 알고리즘도 단순하다. pseudo-code를 보자. 다음과 같이 Floyd-Warshall은 for문 3개로 돌아간다. 의미를 해석하자면 i에서 j로 가는 길의 거리를 생각했을 때, i에서 j로 바로 가는게 빠른지 -> (d_ij) 아니면 k를 경유하여 가는게 빠른지를 비교해서 (d_ik + d_kj) 더 작은 길의 값이 지정이 되는 것이다. (min) 저장되는 그래프 D의 dij는 곧 i에서 j로 가는 최단 거리가 지정이 될 것이다. 2020. 4. 12. [1] 3-SUM algorithm 3-Sum algorithm은, 세 숫자의 합이 특정 조건을 만족하는 모든 경우의 수를 탐색하는 알고리즘이다. 2-Sum 알고리즘도 있다. 애는 Linear Time에 해결할 수 있고, 이는 Hash-table을 이용하여 문제를 해결한다. 2-Sum algorithm을 nlogn의 시간복잡도로 해결하는 방법으로 sliding-window 방식이 있는데, 3-Sum algorithm은 이 방식을 한번 더 감싼 것에 불과하다. 예시 문제를 보면서 이해해보자. 주어진 문제에선 용액의 특성값을 나타내는 N개의 정수가 순서대로 제공된다. 그 때, 세 특성값의 합이 0에 가장 가까운 조합을 찾는것이 목적이다. 그냥 단순히 Brute-force로 문제를 해결하게 되면, for문을 3개 돌려서 모든 조합에 대해서 정답.. 2020. 4. 11. 이전 1 다음
