어디까지 갈 수 있을까?

큰 문제를 작은 문제로 나눠, 현재 계산된 수들을 바탕으로 앞으로의 값을 계산하는 프로그래밍이다 중복되는 연산을 피하기 위해 DP테이블에 계산해 놓은 값을 저장해놓는 (메모이제이션 = 캐싱) 기법 을 이용한다 시간복잡도는 O(logn)이다 탑다운 방식 재귀 함수 이용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 d=[0]*100 def fibo(x): if xd[i//5]+1: d[i] = d[i//5]+1 elif i%3==0 and d[i]>d[i//3]+1: d[i] = d[i//3] + 1 elif i%2==0 and d[i]>d[i//2]+1: d[i] = d[i//2] + 1 print(d[n]) cs 개미전사 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

27. 정렬된 배열에서 특정 수의 개수 구하기 12345678import sysfrom bisect import bisect_left, bisect_rightinput=sys.stdin.readline n, x=map(int, input().split())arr=list(map(int, input().split())) print(bisect_right(arr, x)-bisect_left(arr, x))cs 28. 고정점 찾기 12345678910111213141516171819202122import sysinput=sys.stdin.readline n=int(input().rstrip())arr=list(map(int, input().split())) start=0end=len(arr)-1check=0w..

1 2 3 4 5 from bisect import bisect_left, bisect_right nums = [4,5,5,6] n = 5 print(bisect_left(nums, n)) #1 print(bisect_right(nums, n)) #3 cs bisect_left는 정렬된 배열에서 n값이 들어갈 수 있는 가장 왼쪽 인덱스를 반환한다 bisect_right는 정렬된 배열에서 n값이 들어갈 수 있는 가장 오른쪽 인덱스를 반환한다 * 범위 안 수의 갯수를 구하고 싶을 때 1 2 3 from bisect import bisect_left, bisect_right nums = [4,5,5,6,6,7,8] print(bisect_right(nums, 7)-bisect_left(nums, 5)) #5 ..

문제링크 www.acmicpc.net/problem/2110 이분탐색 진리의 라이브러리 bisect를 사용하자 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys from bisect import bisect_left, bisect_right input=sys.stdin.readline for _ in range(int(input())): n, m=map(int, input().split()) a=list(map(int, input().split())) b=list(map(int, input().split())) a.sort() count=0 for i in b: count+=len(a)-bisect_right(a, i) print(count) cs

1. 순차탐색 데이터를 앞에서부터 차례로 확인하는 방법 시간복잡도가 log(N) 1 2 3 4 5 6 7 8 9 10 11 12 import sys input=sys.stdin.readline print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요') a, find=input().split() print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.') arr=list(input().split()) for i in range(len(arr)): if arr[i]==find: print(i+1) break Colored by Color Scripter cs 2. 이진탐색 데이터를 반으로 쪼개며 탐색하는 방법 이미 정렬 돼 있는 데이터 안에서만..

문제링크 www.acmicpc.net/problem/2606 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import sys from collections import deque input=sys.stdin.readline def bfs(): q=deque() q.append(1) visited[1]=True global result while q: v=q.popleft() for i in graph[v]: if not visited[i]: q.append(i) visited[i]=True result+=1 n=int(input()) graph=[[] for _ in ..

23. 국영수 www.acmicpc.net/problem/10825 1 2 3 4 5 6 7 8 9 10 11 12 import sys input=sys.stdin.readline arr=[] for _ in range(int(input())): a, b, c, d=input().split() arr.append([a, int(b), int(c), int(d)]) arr.sort(key=lambda x:(-x[1], x[2], -x[3], x[0])) for i in arr: print(i[0]) Colored by Color Scripter cs 24. 안테나 www.acmicpc.net/problem/18310 1 2 3 4 5 6 7 import sys input=sys.stdin.readline ..

알고리즘의 효율성을 표기해주는 표기법으로 데이터가 n개 주어졌을 때 연산의 횟수를 나타낸다 빅오 표기법은 알고리즘 최악의 경우 복잡도를 나타낸다 간단하게 이진탐색을 예로 들어보자. 주어진 데이터가 8개일 때 이진탐색은 8->4->2->1 이렇게 3번의 탐색을 진행해 최종적인 답을 찾아내게 된다 만약 주어진 데이터가 n개이고 x번의 탐색을 통해 1이 될 때 x는 어떻게 구할 수 있을까? 로 나타낼 수 있고 여기서 양변에 x를 구하기 위해 log(2)를 취하면 여기서 x를 구하기 위해 양변에 log2를 하면 탐색횟수 x를 구할 수 있다 O( 1) < O( log n)