코학다식

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

자료 구조와 알고리즘(1) 이 포스팅은 Python Cookbook의 내용을 요약하여 작성되었습니다. 지적, 질문은 언제나 환영합니다. 1.1 시퀀스를 개별 변수로 나누기 모든 시퀀스(혹은 이터레이팅 가능한 것)는 할당문을 통해서 개별 변수로 나눌 수 있다. 단, 변수의 개수가 시퀀스에 일치해야 한다. 그렇지 않으면 에러가 발생한다. 시퀀스를 개별 변수로 나누는 것을 언패킹(unpacking)이라고 하는데, 이는 순환 가능한 모든 객체(튜플, 리스트, 문자열, 파일, iterator, generator 등)에 적용할 수 있다. 다만 특정 값을 제외하는 방법은 따로 없다. 만약 어떤 값은 버리고 싶다면, 그 값에 해당하는 변수 이름을 버리는 것으로 이해할 수 있도록 붙여 주는 수밖에 없다. 책에서는 _(언..

문제 링크 :: 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까지의 부분 합을 구해야 합니다. 이런 사소한 부분에서 실수가 나면 은근 알아차리기 어렵더라구요...