이분탐색

[python] 코테 대비 알고리즘 모듈 정리

정렬 arr = [(1,2),(2,3), (1,1)] arr.sort() # 일반적으로 처음인자부터 차례로 정렬 nlogn arr.sort(key=lambda x:x[1],x[0]) # 두번째 인자 우선순위로 정렬 arr.sort(key=lambda x:x[0], reverse=True) # 첫번째 인자 기준으로 반대로 정렬 곱집합, 조합, 순열 from itertools import product product([1,2,3],['a','b','c','d']) # 하나씩 선택하는 모든 케이스(곱집합)가 만들어진다. from itertools import combinations combinations(iterable, r=None) # 조합 구하기 from itertools import permutatio..

[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )

왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다. 우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 경우를 구하면 된다. 제한사항을 보면 distance가 1~1,000,000,000이다. 아무래도 선형탐색은 못할 만큼 값이 크다. 따라서 여기서 이분탐색의 냄새를 살짝 맡아본다. 처음에 나는 각 돌마다 거리를 구하고 작은 값부터 제거하면 되지 않나?하고 생각했다. 그러나 문제는 돌이 제거되면 각 돌의 거리를 다시 최신화 해주어야 한다. 그럼 돌을 제거 할 때마다 sort를 하게 되고 n만큼 sort를 해야되는 상황이 발생한다. 그럼 생각을 바꿔보자 만약 최솟값을 기준으로 현재 바위가 만족하는지 확인한다고 가정한다. ..

[python3] 프로그래머스 입국심사 풀이 ( 이분 탐색 )

이거 어려웠다. 처음에 점화식을 세워야하나 많이 당황했다. 솔직히 이분탐색 문제가 아니었다고 한다면 제한된 시간내에 풀지 못했을거 같다. 일단 문제를 보자 문제를 읽어보면 입국심사가 필요한 인원과, 입국심사에 걸리는 시간이 존재한다. 이때 입국심사를 모두 마치기 위한 최소시간을 구하면 된다. 처음에는 이분탐색을 어디에 적용해야할지 몰라서 당황했다. 이후에 문제를 차분히 살펴보니 return값을 살펴보는게 어떨까라는 생각이 들었다. 정리된 생각은 아래와 같다. 1. 입국심사에 적은 시간이 걸리는 심사관이 많은 입국자를 받아야 총 시간이 줄어든다. 2. 최소시간을 times로 나누었을때 값을 더하면 n이 된다. 처음에는 1번에 꽂혀서 무조건 작은 시간을 많이 주고 하나씩 줄여가며 연산을 하면 되겠지라는 생각..

백준 12015 풀이 (가장 긴 증가하는 부분 수열 2, LIS, 이분탐색)

이 문제는 어떻게 접근해야하나 LIS를 찾다가 거의 정답을 알게되서 거의 꽁으로 푼 문제다. 그러나 이해하는데에 상당히 어려웠기 때문에 내 수준에서 이해한 풀이를 적어보겠다. 이전에 LIS문제가 있었는데 그건 다이나믹 프로그래밍으로 풀었던 문제였다. guccin.tistory.com/38 백준 11053 풀이 (가장 긴 증가하는 부분 수열, LIS) 요것은 머랄까 LIS인데, 나도 처음 들어봤다. 애당초 알고리즘 수업도 들어본 기억이 없기 때문에 무엇을 듣던지 생소하다. 그래서 맘편히 구글링을 해보았다. LIS는 최장 증가 수열을 의미한다. L guccin.tistory.com 당시의 풀이 방법은 처음부터 i번째 시점에서 가장 많이 몇번째인지 정하는 방식으로 풀이를 진행한다. 이렇게 설명하려니 상당히 어..

백준 1300 풀이 (k번째 수, 이분 탐색)

이제 슬슬 알고리즘 풀때 음악을 들으면 안되겠다는 생각이 점점 들기 시작했다..... 그래서 오늘은 음악을 듣지 않고 천천히 집중해서 풀어보았다. 문제에서 주어지는 입력값이 굉장히 크다. 그래서 배열을 직접 만들어서 선언하며 풀게되면 메모리나 시간적인 측면에서 굉장히 손해를 볼수 있다. 따라서 어떻게 풀어야 할지 고민해보고 어떤 방식을 쓰면 좋을지 고민해 보았다. 우선 이분 탐색 문제이기 때문에 어떤 오름차순을 선택해서 풀어야할지 고민해보았다. 그 중에서 쓸만하다고 생각했던것은 행렬에 존재할 수 있는 수의 오름차순이었다. 예를 들어 3x3행렬이라면 1~9까지 나올수 있는 수이고, 4x4행렬이라면 1~16까지가 나올수 있는 수이다. 그럼 3x3행렬일경우 n = 3, k = 7 행렬은 [[1,2,3],[2,..

백준 1654 풀이 (랜선 자르기, parametric search, 파라매트릭 서치)

파라매트릭 서치는 이분탐색을 활용하여 최대 혹은 최소를 구하는 방법이다. 예를 들어 1~10까지중 5를 확인해보고 최소를 구해야된다면 5부터 10까지 버린다. 그럼 1~4안에서 비교를 하며된다. 이러한 방식으로 절반값을 확인하며 최대 혹은 최소를 구하는 방법이다. 딱히 설명할게 없어서 바로 이론을 학습하고 바로 코딩에 들어갔다. import sys k,n = map(int, sys.stdin.readline().split()) small = 2**32-1 lan = [] for _ in range(k): t = int(sys.stdin.readline()) lan.append(t) if t < small: small = t l = 1 r = max(lan) mid = small while l != r: ..

백준 10816 풀이 (숫자 카드 2, 이분 탐색, 해쉬 사용, Counter)

이번 문제는 Counter를 사용해서 해결했다. 기본적인 이분 탐색과 풀이에 차이가 전혀 없다. 단지 Counter를 이용해서 Dict형태로 만들어 주고 중복값을 제거하여 이분 탐색을 진행하게 만들었다. 1. Counter를 이용해서 중복을 제거한 Adict를 얻는다. 2. Adict에서 key값만 뽑아서 중복이 제거된 Alist를 얻는다. 3. Alist를 오름차순으로 정렬한다. 4. 이분탐색을 이용하여 해당되는 값을 구한다. 5. 해당 되는 값을 구할 수 있다면 Adict에서 몇개나 존재하는지 출력한다. 위의 순서로 코딩을 진행하면 쉽게 풀 수 있다. from collections import Counter n = int(input()) AC = Counter(list(map(int, input()...