개발의 꿈을 개발하는 꿈을 개발하려는 꿈

1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 자체는 쉬운데, 발상을 하는 게 내 기준에서 어려웠던 문제. 으레 DP문제들이 다 그런 것 같다. 점화식과 DP 문제임을 밝혀내는 게 가장 어려운 과제다. 내가 가장 취약하다고 느끼는 부분인데, 이번에도 온전히 내 힘으로 풀어내는 것은 실패했다. 아무튼 문제를 보자. 우리는 어떻게 연속된 수를 선택해야 값이 최대가 되는지 한번에 알 수는 없다. 다만 어떻게 고르더라도 그러한 연속된 수의 양 끝단이 어떤 식으로든 존재할 것을..

1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 그래프를 사용하는 문제이다. 이분 그래프라는 것이 정확하게 개념으로 자리잡고 있는 것인지에 대해서는 잘 모르겠지만, 정점을 두 집합을 쪼개면서 각 집합 내에서는 인접하지 않게하는 방법은 사실 간단하다. 각 노드들을 순회하면서 자신의 인접한 노드가 자신과 같은 집합 내에 있는지 확인하는 것이다. 그렇다면 집합 표시를 어떻게 할 것인가가 또 의문으로 남게 되는데(내가 이것을 떠올리지 못해 틀리게 됐다), 사실 그것도..

1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 매우 간단한 문제이다. 그냥 A의 B제곱을 C로 나눠서 반환하면 되기 때문이다. 그러나 입력 제한을 보면 B 역시 int(2147483647) 최대값까지 들어갈 수 있기에 단순하게 B제곱을 했다가는 어마무시한 시간 초과가 나버리게 된다. 이를 조금 완화하는 방법이 있는데, 조금의 수학 지식이 필요하다. 나머지 분배 법칙 (A * B) % C = (A%C) *(B%C) % C 대충 이런 법칙이 있다. 간단하게 말하자면 두 수를 곱한 것의 나머지를 구할 때는, 각각의 나머지를 먼저 구하고..

1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 어라라, 출발지와 도착지가 정해져 있고, 내리막으로 이동가능한 모든 경우의 수를 구하라고? 이거 완전 dfs아니냐?! 라고만 생각하는 당신. 틀렸다! 문제의 제한시간과 메모리는 dfs로만 접근하기에는 조금 적다. 실제로 간단하게 dfs를 만들어서 돌리면 예제는 통과할 수 있다, 그러나 실제로 제출을 하면.. 이런 꼴을 면치 못할 것이다. 혹시나 싶어 PyPy3으로 제출해도 메모리 초과까지 나는 상황. DFS + DP d..

예제를 보면 알겠지만, n개의 물건이 다 같은 무게를 가질 수도 있고 심지어 다 넣더라도 C보다 무게가 덜 나가는 경우가 존재한다. 그래서 경우의 수가 최대로는 각 물건이 포함되거나, 포함되지 않거나를 따져서 $2^n$개까지 나올 수 있다. n의 입력 제한이 30이기에 최대 경우의 수는 $2^{30}$인 꼴인데, 이 모든 가짓수를 일일히 세면 문제에서 원하는 정도의 시간 제한을 준수할 수 없다. Meet In The Middle 이 가짓수를 획기적으로 줄일 수 있는 방법이 바로 meet in the middle 알고리즘이다. 이 알고리즘은 탐색할 리스트를 둘로 쪼갠다. 만약 n이 30일 경우 반으로 쪼개면 15, 15인 배열로 쪼개지게 되는데, 각 배열에서 나올 수 있는 최대의 경우의 수는 $2^{15}..

입력 조건의 n은 최대 \(10^5\)인 관계로 일차원 배열 B는 최대 \(10^{10}\)의 크기를 가지게 된다. 그 정도 크기의 배열을 일일히 만들고, 정렬해서 해당 위치를 참조하는 것은 시간을 많이 소비하게 된다. inlst = [[(i+1) * (j+1) for i in range(n)] for j in range(n)] lst = [] for i in inlst: lst.extend(i) lst.sort() 이렇게 모양을 만들어내는 것은 가능하다. 다만.. 어마무시한 시간을 잡아먹게 된다. 이분탐색 그 대신 활용할 수 있는 방법이 바로 이분탐색이다. 여기에서 이분탐색으로 찾아내야 할 것은 바로 k 인덱스에 해당하는 값이 되시겠다. k를 가지고 해당 인덱스에 위치한 값을 찾는 것은 어렵지만, 값을..