소민's Blog

10816. 숫자 카드2첫 풀이 - fail일반 이분탐색 구조로 풀었으나이 코드는 중복되지 않는 값들로만 이루어졌을때만 가능그 이유: 중복 값 여러개 있을때 [10 10 10 10] 두번째 10 위치가 mid로 먼저 인식됐을때 앞에 값을 건너뛰어버리기 때문n=int(input())nums=list(map(int,input().split()))m=int(input())lst=list(map(int,input().split()))nums.sort()result=[]for val in lst: cnt=0 l,r=0,n-1 while l 두번째 풀이중복된 값이 존재하는 만큼bisect으로 val, val+1 값 위치 찾아서 val의 갯수 세기from bisect import bisect_le..

연속된 부분 수열의 합 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이누적 합 (Prefix Sum)prefix_sum[i] = prefix_sum[i-1] + sequence[i-1]구간 합 계산: prefix_sum[r] - prefix_sum[l]prefix_sum[l]부터 prefix_sum[r]까지의 합은 수열의 l+1부터 r까지의 합.이진 탐색 (bisect_left)r = bisect_left(prefix_sum, k)prefix_sum에서 k 이상인 첫 번째 인덱스를 찾음.투 포인터 방식 탐색투 포인터 (l, r): l은 구간의 시작, r은 구간의 끝을 나타냄.prefix_sum[r] - ..

14426.접두사 찾기 풀이S를 사전순으로 정렬접두사 탐색을 위해 정렬 필수각 검사 문자열 c에 대해 이진 탐색으로 c가 들어갈 위치 찾기 (bisect_left)idx = bisect_left(S, c)찾은 위치의 문자열가 c를 접두사로 가지는지 확인S[idx][:len(c)] == c → 접두사 여부 판별startswith로도 확인 가능slst[idx].startswith(c)접두사면 카운트 증가from bisect import bisect_leftn, m = map(int, input().split())slst = sorted(input() for _ in range(n))clst = [input() for _ in range(m)]cnt = 0for c in clst: idx = bisect..

bisect: 정렬되어 있는 리스트에서 정렬을 흩트리지 않아도 되는 부분의 '인덱스'를 엄청 빠른 속도로 찾아주는 모듈 bisect_left(literable, value) : 왼쪽 인덱스를 구하기bisect_right(literable, value) : 오른쪽 인덱스를 구하기 (bisect =  bisect_right) from bisect import bisect_left, bisect_rightnums = [0,1,2,3,4,5,6,7,8,9]n = 5print(bisect_left(nums, n))print(bisect_right(nums, n))'''결과값56'''출처: https://programming119.tistory.com/196 [개발자 아저씨들 힘을모아:티스토리]

11054. 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 최장증가부분수열을 구하는 LIS 함수를 만들어두고 최장감소부분수열은 값에 -를 붙여서 LIS함수에 넘기면 같은 길이값을 반환함 i까지의 최장증가부분수열의 길이, i이후의 최장감소증가부분수열의 길이를 구해서 -1 (하나 값 중복되므로) import bisect def lis(arr): if not arr:return 0 dp = [arr[0]] for i in range(len(arr)): if dp[-1]

12015. 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 N (1 ≤ N ≤ 1,000,000)이기 때문에 11055. 가장 큰 증가하는 부분 수열 N (1 ≤ N ≤ 1,000) 처럼 2중 for문 돌면서 DP 로 풀면 시간 초과남 굳이 N개의 수들에 대해서 현재 위치 이전의 모든 수를 반복하며 훑어봐야할까? dp [i]를 구하기 위해 dp[0]~dp[i-1]의 최댓값을 알고 있다면 반복하지 않아도 된다! -> pyth..