코학다식

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

최근 배우게 된 알고리즘 중 가장 실생활과 밀접한 관련이 있다고 느껴지는 알고리즘이다. (이미 내가 사용하고 있을 수도 있지만) 이름을 알고 있는 알고리즘이 아직 그다지 많지 않은데, 열심히 공부해서 얼른 수를 늘리고 싶다. 문제를 해결할 때 필요한 알고리즘을 적재적소에 떠올리고 싶은데 지식이 부족하다. 그래도 과거의 나보단 낫다는 것에 항상 의의를 두려고 노력 중. 이분 매칭(Bipartite Matching) 이분 매칭은 네크워크 플로우(Network flow)에서 등장하는 개념 중 하나이다. 그렇지만 네트워크 플로우를 처음 들어 본다고 하더라도 쉽게 이해할 수 있다. 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 각각이 일대일 대응으로 매칭되는 것을 의미한다..

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

문제 링크 :: https://www.acmicpc.net/problem/1806 Solution 문제 이름처럼 부분 합을 이용해서 푸는 문제. 그래서 일단 sum 배열에 부분 합을 구해 줬다. 그리고 나서는 어떻게 시간 초과가 나지 않으면서 합이 S 이상인 구간 합 중 가장 길이가 짧은 것을 구하느냐가 관건이었다. 다른 사람들은 어떻게 풀었는지 모르겠지만 나는 S 이상의 부분 합이 나타나는 부분 합을 발견하면 그 인덱스를 기준으로 가장 짧은 구간 합(j가 i-1인 경우)부터 계산하면서 그 값이 S 이상이 되면 정답 후보 배열(sol)에 길이를 저장해 주도록 했다. 가장 짧은 구간 합부터 구하니까 S 이상인 값을 발견하면 바로 반복문을 탈출한다. 만약 가장 짧은 구간 합이 S 이상이면 굳이 나머지 구간 ..

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