코학다식

문제 링크 그래프에서 최단 경로를 찾는 알고리즘 중 하나인 벨만-포드 알고리즘으로 풀 수 있는 문제였다. 주의해야 할 점은 오버플로우가 발생할 수 있기 때문에 거리 배열의 타입을 long long으로 선언해 주어야 한다는 점이다. Bellman-Ford's Algorithm 어떤 경로든 최대 ||V|| - 1개의 간선으로 이루어질 수 있으므로 모든 간선을 ||V|| - 1번 확인하면서 모든 정점의 최단 거리를 갱신하는 알고리즘이다. 한 개의 정점에서 시작해 모든 정점으로 가는 최단 경로를 찾는다. 간선이 E개, 정점이 V개일 때 각 간선을 ||V|| - 1번 확인하므로 시간복잡도는 O(||V|| ||E||)가 된다. 음수인 간선이 있어도 사용할 수 있다. 아래의 예시에서 시작하는 정점은 S이다. ..

문제 링크 Solution 정렬 함수인 sort()만 사용하면 쉽게 풀 수 있는 문제로 보이지만, 주의해야 할 것이 하나 있다. 나이가 같은 경우 먼저 가입한, 즉 먼저 입력받은 요소가 앞에 와야 한다는 것이다. 이를 위해 비교 함수(comp)를 바꿔 줄 수도 있지만, sort()와 같이 정렬 함수 중 하나인 stable_sort()를 사용하면 간편하게 풀 수 있다. stable_sort()는 sort()와 같이 정렬을 수행한다는 것은 같지만 값이 같은 경우에는 원래의 순서를 그대로 유지한다. sort()의 경우 입력받은 데이터의 크기가 작으면 값이 같은 경우에 따로 처리를 해 주지 않아도 순서가 유지되는 것처럼 보이나, 데이터가 커지면 랜덤하게 바뀔 수 있다. code #include #include ..

문제 링크 Solution 반복문을 이용해서 부분 배열의 합을 구하려고 하면 시작점과 끝점을 바꿔 가면서 값을 구해야 하기 때문에 반복문을 최소 두 번은 중첩해서 사용하게 된다. 그러면 시간 초과가 나기 때문에, 반복문을 중첩하는 방법으로는 AC를 받을 수 없다. 그런데 DP를 이용하면 선형 시간 안에 이 문제를 해결할 수 있다. 부분 배열의 합을 저장하는 배열을 하나 더 만든다고 생각해 보자. 이 배열의 이름을 dp라고 하면, dp[i]는 해당 인덱스까지의 부분 배열의 합을 의미한다. 주어진 배열이 -1 -2 -5 6 1이라고 가정하자. 편의상 인덱스가 1부터 시작한다고 생각하고 dp의 값을 구하면 dp[1]은 -1이 될 것이다. dp[2]는 dp[1]에 -2를 더한 값이 되는데, 이는 dp[1]보다 ..

문제 링크 Solution 나무를 자를 특정 높이를 구해야 한다. 즉, 특정 숫자를 구해야 하는 것이다. 이 숫자는 어떤 조건을 만족해야 한다. 조건이 무엇인지는 차치하고, 이 두 가지만 먼저 고려해 보자. 전형적인 탐색 알고리즘 문제와 비슷하다. 그래서 이분 탐색을 사용했다. 다만 이미 입력받거나 해서 정해진 특정 숫자를 찾는게 아니라, 나무들의 배열에서 이 숫자보다 큰 높이를 가진 나무들을 잘랐을 때 잘린 부분의 합이 M이 넘는다는 조건을 만족하는 숫자를 찾아야 하는 게 다른 점이다. 또 하나 주의해야 할 점은 그렇게 해서 조건을 만족하는 최댓값을 찾아야 한다는 것이다. 코드에서 ans가 등장한 이유이다. 가령, 입력으로 나무 개수가 2개, 필요한 나무의 길이가 3, 각각의 나무의 길이가 2인 경우에..

문제 링크 :: https://www.acmicpc.net/problem/11375 Solution 이분 매칭으로 쉽게 풀 수 있는 문제이다. M개의 일을 해야 하는 상황에서 N명의 직원들 각각이 할 수 있는 일이 정해져 있고, 직원들은 하나의 일만 담당할 수 있다. 이분 매칭 알고리즘 설명 글에서 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 하나의 간선으로만 연결되는 것을 의미한다고 했다. 일과 직원은 서로 같은 그룹끼리는 연결되지 않으면서 다른 그룹끼리만 연결 가능한, 전형적인 이분 그래프라고 할 수 있다. 이 문제는 이분 매칭을 최대한 많이 가능하게 만드는 것을 요구하고 있다. 그렇다면 어떻게 해야 이분 매칭을 최대한 많이 할 수 있을까? 이것 역시 이분 ..

문제 링크 :: https://www.acmicpc.net/problem/11659 Solution 아주 아주 기본적이고 쉬운 구간 합 문제. 부분 합을 구해 놓고 시키는 대로 구간 합을 구하면 된다. 괜히 배열의 크기를 딱 문제에 제시된 수열의 최대 크기만큼만 선언하지 말고, 한 칸만 더 선언해 준 다음에 인덱스와 주어지는 구간을 일치시키는 게 훨씬 직관적이고 편하다. 수열을 이루는 숫자는 작아도 더하면 좀 커지므로 데이터 타입을 더 큰 단위로 선언해 주는 게 좋다. 물론 이 문제에서는 100000개의 숫자가 모두 1000이고 처음부터 끝까지의 합을 구해도 int형 범위 내일 것 같긴 한데, 넘어가는 문제도 많으니까. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

문제 링크 :: https://www.acmicpc.net/problem/14648 Solution Prefix sum 알고리즘으로 쉽게 해결할 수 있는 문제입니다. 관련 설명은 아래 링크에서 보실 수 있습니다. 그런데 한 가지 주의해야 할 점이 있습니다. [a, b] 구간의 합을 구하기 위해서 b까지의 부분 합과 a-1까지의 부분합을 알아야 하는데, 편의상 배열의 크기를 (n이 최대 1000이므로) 1001로 선언해 두고 첫 번째 요소의 인덱스가 1이 되도록 코드를 작성하는 경우에는 그대로 b와 a-1까지의 부분 합을 사용해서 구간 합을 구하면 되지만, 첫 번째 요소의 인덱스가 0인 경우에는 b-1과 a-2까지의 부분 합을 구해야 합니다. 이런 사소한 부분에서 실수가 나면 은근 알아차리기 어렵더라구요...

안녕하세요. 오랜만의 알고리즘 포스팅입니다. 제가 방학이라고 공부 안 하고 놀아서 그렇습니다. (반성...) 이번 포스팅에서는 Prefix sum(구간 합)에 대해 알아보도록 하겠습니다. 아주 간단하지만 유용한 알고리즘입니다. Prefix sum? 영어로는 이게 뭐지 싶지만 한글로 보면 의미를 대충 짐작하실 수 있을 겁니다. 구간 합이란 말 그대로 수들의 나열에서 특정 구간의 합을 의미합니다. 이와 비슷한 개념으로 부분 합이 있습니다. 부분 합은 구간 합과 달리 처음부터 특정 인덱스까지의 합을 의미합니다. 구간 합에서의 구간은 당연히 어느 구간이든 가능합니다. 처음부터 끝까지일 수도 있고, 세 번째에서 일곱 번째일 수도 있고, 마지막 숫자만일 수도 있겠습니다. 예를 들어 볼까요? 1 2 3 4 5 6 7..