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

목차 개요 10807번: 개수 세기 (acmicpc.net) 풀이 1차원 배열에서 순회하는 문제. 일일히 반복문을 돌아서 찾아도 된다. Counter나 count를 사용하는 방법도 있다! 코드 Counter 사용 import sys from collections import Counter input = sys.stdin.readline N = int(input()) lst = list(map(int, input().split())) v = int(input()) counter_lst = Counter(lst) print(counter_lst[v]) count 사용 import sys input = sys.stdin.readline N = int(input()) lst = list(map(int, inpu..

25710번: 점수 계산 (acmicpc.net) 25710번: 점수 계산 길이가 N인 배열 a가 주어진다. 배열 a의 i번째 원소를 ai라고 정의하자. 다음 과정을 통해 배열에서 점수를 획득할 수 있다. 배열의 두 원소 ai, aj를 선택한다. (1 ≤ i < j ≤ N) 선택된 두 원소의 www.acmicpc.net 사실 문제는 굉장히 간단하다. 나올 수 있는 두 수의 조합을 모두 구한 후 그 값을 곱한 뒤에 나온 값의 자릿수를 더한 값이 최대가 되는 것을 찾으면 된다. 만약 {1, 3, 9, 11, 20}이 있다면(정렬되지 않게 들어올 수 있다) 여기에서는 9와 11을 곱한 값 99의 자릿수를 다 더하면 18이 되는데 이게 최대값이 될 것이다. 그러나 문제는 시간 제한은 1초이고 들어올 수 있는 입..

1966번: 프린터 큐 (acmicpc.net) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 프린터에 들어간 종이들에 가중치가 있고, 가중치가 높은 순으로 종이를 출력해야 한다니, 이거 완전 우선순위 큐 아니냐?! 하신 분들은 나처럼 이 문제를 북마크하면 되시겠다. 이 문제에 주의깊게 봐야할 지점은 바로 중요도가 같은 종이들의 출력 순서이다. 기본적으로는 배열의 왼쪽부터 출력을 걸도록 되어 있어 그 부분에 대한 처리가 필요하다. 예제에서 세번째 케이스가 좋은 예시가 된다. 한 종이만 중요도가 9이고, 나머지는..

1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 가장 짧은 사이클을 찾아내는 그래프 문제. 문제 분류를 봤을 때는 플로이드 워셜을 사용해야 할 것이라고 생각했는데, 그것보다 더 빠르게 답을 찾을 수 있는 방법이 존재한다. 플로이드 워셜의 방법을 사용한다면, 각 노드의 자기 자신으로 가는 루트를 최대값으로 설정한다. 이후 삼중 반복문을 다 돌고 나서 각 노드를 확인하며 자기 자신으로 가는 루트 중 최소값을 찾으면 되는 것이다. 하지만 ..

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를 가지고 해당 인덱스에 위치한 값을 찾는 것은 어렵지만, 값을..