코학다식

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

문제 링크 Solution 처음에는 양수 배열과 음수 배열로 나누어서 이분 탐색을 실행하는 걸 고민해 봤는데, 번거로운 것 같고 다른 방법이 있을 것 같아 다른 방법을 찾다 절댓값으로 정렬해서 이웃한 두 수를 더하는 방법을 사용했다. 이 방법을 사용하면 모두 양수인 경우, 모두 음수인 경우도 쉽게 해결할 수 있다. 대충 봤을 때 값이 꽤 커 보이기에 모든 변수를 long long으로 선언해 줬다. +) C++의 sort 함수는 정말 자주 유용하게 쓰이는 것 같다. code #include #include #include #include using namespace std; vector ans; bool cmp (const long long a, const long long b) { if (abs(a) =..

문제 링크 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/11660 Solution 구간 합을 이용하긴 하는데 이차원 배열임을 유의해야 한다. 문제의 예시에서 볼 수 있듯이 그냥 처음부터 끝까지 수를 다 더하는 게 아니라 사각형 모양을 이루는 구간의 합을 구해야 한다. 이건 구간 합을 구할 때뿐만이 아니라, 부분 합을 구할 때도 마찬가지다. 특정 위치의 부분 합을 구하고 싶다면 처음(1, 1)부터 해당 위치까지 사각형을 만들어 그 구역에 있는 숫자들을 합해야 한다. 합하는 방법은 일차원 배열보다는 조금 복잡하지만 어렵지는 않다. 첫 행은 평범하게 부분 합 구하듯이 쭉쭉 더해 주면 된다. 다음 행부터는 첫 번째 열에 위치하는 경우와 아닌 경우가 달라진다. 첫 번째 열에 위치하면 만들 수 있..

문제 링크 :: 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 ..