www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 아이디어: 파이썬으로 풀면 아주 간단하게 풀 수 있다. 일단 중복을 제거하기 위해 set을 사용하고, 후에는 sorted()함수에 lambda를 사용하여 다중 조건을 걸어 정렬을 한다. 코드: #문자열, 정렬 import sys n = int(sys.stdin.readline()) arr = [] for _ in range(n): arr.append(sys.stdin.readline().rstrip(..
알고리즘💻/이분탐색&정렬&분할정복
www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 아이디어: 정렬 B의 가장 큰 수에 A의 가장 작은 수를 곱하면 된다. A는 오름차순으로, B는 내림차순으로 정렬한 후 각각 곱한다. 5 1 1 1 6 0 2 7 8 3 1 이 예제에서 A를 오름차순으로 정렬하면 0 1 1 1 6, B를 내림차순으로 정렬하면 8 7 3 2 1 이므로 구하는 합은 0+7+3+2+6=18 이다. 코드: 파이썬에서 내림차순으로 정렬하는 방법, lambda를 쓰는 방법 잘 익혀..
www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 아이디어: 이분 탐색으로 푼다는 게 무조건 mid 값을 찾는다는 게 아닌가보다..((아닐수도)) 1. 정렬 2. high = n-1, low = 0으로 포인터를 설정하고, while문을 수행하면서 특성값을 구하고 절댓값을 취하여 최솟값을 업데이트한다. 특성값이 음수면 low++(0에 가까워지려면 커져야 되니까), 양수면 high--(0에 가까워지려면 작아져야 되니까) impor..
www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 아이디어: 블루레이 크기를 이분 탐색. high = 10^9, low = 1 레슨의 길이를 더하다가 mid보다 같거나 커지면 블루레이 개수 +1 레슨의 길이가 M보다 크면 low = mid + 1, 같거나 작으면 블루레이 크기를 더 줄여야 하니까 high = mid - 1하고 ans 업데이트 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map..
www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 아이디어: 막대 과자의 길이를 이분 탐색하여 조카 n명에게 줄 수 있는 과자 길이의 최댓값을 구한다. import sys m, n = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) high = 1000000000 low =..
www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 아이디어: 시간을 이분탐색하여 시간의 최솟값을 찾는다. import sys n, m = map(int, sys.stdin.readline().split()) time = [] for _ in range(n): time.append(int(sys.stdin.readline())) high = 10**18 low = 1 ans = high while (high>=low): mid = (high+low..
www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 아이디어: 이분 탐색의 기본 문제. 이분탐색의 로직을 잘 익히자. import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) arr.sort() m = int(sys.stdin.readline()) num = list(map(int, sys.stdin.read..
