https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 설명만 보면 무언가 흔히 봤던 문제 같지만 배열이 4개로 나누어져 있다. 거기다 입력값은 최대 4000개까지 가능해서 왠만한 방식으로는 그냥 바아아로 시간초과가 나버린다. 여러 방식들을 시도해 보았으나 가장 마음에 드는 방법은 역시 딕셔너리를 쓰는 거였다. 문제를 풀어볼수록 파이썬에 딕셔너리가 있어서 정말 감사하다~ 는 생각이 들었다. 특정 이분 탐색 문제는 조금만 코드를 ..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이제까지 풀던 이분탐색 문제의 조오금 고급 버전..! 전체적인 구성은 이전의 문제들과 동일하지만 is_possible에서의 조건을 조금 더 구체적으로 분리해 주어야 한다. 사이트에 반례가 많이 없어서 예외처리를 해주는데 시간이 조금 걸렸다. 내 코드가 조금 더러운것 같기도.? 1. lo, hi, mid를 정할때, mid는 배열의 (최대-최소) /..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 마찬가지로 이분 탐색 문제. 이러한 유형들은 뭘 많이 자른다. 한가지 주의할 점은 랜선의 길이가 0이 되는 일은 없기 때문에 lo를 0이 아닌 1로 시작해야 한다. 안그러면 런타임 에러(ZeroDivisionError)가 뜨는데 코테에서 이에 해당하는 testcase를 주지 않으면 아무 생각 없이 지나갈 수도 있을것 같다. 주어진 테케 잘 돌아간다고 넘기지 말고 문제 ..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 계속되는 이분 탐색 시리즈. 이와 비슷한 류의 문제는 같은 방식으로 작성하는 연습을 하고 있다. 나무를 잘라보자 N, M = map(int, input().split()) trees = list(map(int,input().split())) lo = 0 hi = max(trees) mid = (lo+ hi) //2 def is_possible(mid): tm..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분 탐색을 공부하는 중 대표 문제로 지정되어 있어서 들어가 봤더니 이전에 다른 방식으로 해결한 문제였다. 이번엔 이분 탐색을 사용하여 풀어 보았다. 파이썬 이분 탐색 라이브러리: from bisect import bisect_left, bisect_right 이를 이용해서 리스트에 자신이 찾길 원하는 숫자가 존재하는지 확인할 수 있다..! bisect_right(a..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색 중 파라매트릭 서치를 구현해보는 문제이다. 어렵게 생각하지 말고 기본적인 이분탐색 구현에 초점을 맞추면 쉽게 해결할 수 있다. 라이브러리를 불러와서 이분탐색 함수를 쓸 필요도 없다. 입력받은 예산들 중 가장 큰 값의 절반으로 중간점을 잡고 중간점과 각 예산 중 작은 값들을 더한 값이 예산 총액을 넘어가는지 확인하면서 이를 반복한다. N = int(input()) req = list..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 조건도 까다롭지 않고 배열의 입력값 범위도 최대 8이어서 시간복잡도 걱정 없이 부르트포스로 풀면 되겠다고 생각하였다. 문제 풀이에서도 딱히 걸리는건 없었고 최대한 시간와 메모리를 쓰면서 코드를 작성했다. 간단히 짚고 넘어갈 부분은 리스트의 얕은 복사와 깊은 복사 부분 정도인것 같다. 처음에 받은 배열을 계속 깊은 복사하면서 BFS를 시도한다. 주어진 지도에서 3개의 좌표에 벽을 세워야 하는데 이는 배열의..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 겉으로 보면 간단해 보이지만 굉장히 시간초과가 많이 발생하는 문제였다. 처음부터 문제의 조건과 각 풀이방법별 예상 시간 복잡도를 계산해본 후 코드작성에 들어가야 헤매지 않을 수 있는 문제인것 같다. 먼저 문제의 설명과 예시를 보면 가장 먼저 생각나는게 BFS일테고, 각 좌표별로 BFS를 돌려 카운트를 세면 당연히 시간초과가 난다. N by M 행렬이고 N과 M은 각각 10^3..