알고리즘(파이썬) (16) 썸네일형 리스트형 역수열을 원래의 수열로 되돌리기(그리디) 역수열 5 3 4 0 2 1 1 0 이 주어진다. 첫(1) 번째 요소 5는 원래의 수열에서 1 앞에 1보다 큰 숫자가 5개 있다는 뜻이고 (1보다큼)(1보다큼)(1보다큼)(1보다큼)(1보다큼)1(?)(?)두(2) 번째 요소 3은 원래의 수열에서 2 앞에 2보다 큰 숫자가 3개 있다는 뜻이먀(2보다큼)(2보다큼)(2보다큼)2(?)1(?)(?)세(3) 번째 요소 4는 원래의 수열에서 3 앞에 3보다 큰 숫자가 4개 있다는 뜻이다(3보다큼)(3보다큼)(3보다큼)2(3보다큼)13(?) n = int(input()) # 배열 크기 입력a = list(map(int, input().split())) # 왼쪽에 있는 자신보다 큰 수의 개수 리스트seq = [0] * n # 최종적으로 정렬될 배열 (초기에는 모두.. list와 deque list와 deque에서 pop(0)의 차이점 1. pop(0) (list 사용)첫 번째 요소를 제거하면 나머지 요소들의 인덱스를 하나씩 앞으로 이동해야 해서 성능이 저하된다.O(n)의 시간 복잡도를 가짐 (리스트가 길수록 더 느려짐)2. popleft() (deque 사용)첫 번째 요소를 제거해도 나머지 요소들의 인덱스가 유지된다. (재정렬 불필요)O(1)의 시간 복잡도를 가짐 하나의 보트에 두 사람이 탈 수 있다고 가정할 때 필요한 최소한의 보트 개수를 구해보자.먼저 승객의 몸무게를 리스트에 저장하고 오름차순으로 정렬한다. 그리고 리스트를 deque로 변환하여 앞뒤에서 빠르게 요소를 제거할 수 있도록 변경한다. 가장 무거운 사람과 가장 가벼운 사람이 함께 타기에 너무 무거운 경우(limit을 넘을 경.. 그리디 알고리즘(2) 체력 테스트 후 우수한 학생을 선발하고자 한다. 키, 몸무게 중 적어도 하나는 다른 사람보다 커야 한다는 선발 기준이 있을 때 (데이터 중복은 없다고 가정) 몇 명의 학생을 선발할 수 있을까? (키, 몸무게) 튜플 형식으로 리스트에 넣은 후키를 기준으로 내림차순 정렬한다. 그렇다면 정렬 후 앞에 나오는 사람은 항상 키가 크고, 나중에 등장하는 사람은 항상 앞사람보다 키가 작다.따라서 몸무게가 지금까지 선발된 사람 중 가장 크다면 선발 가능하다. 그리고 최대 몸무게(largest)를 갱신하고 선발된 학생 수(cnt)를 증가시킨다. 키몸무게최대 몸무게선발 여부A183650->65OB1816065XC1807065->70OD1756770XE1727270->72Obody=[]for i in range(n): .. 그리디 알고리즘 하나의 회의실이 있고 n개의 회의가 열릴 계획이 있을 때,최대 몇 개의 회의를 배정할 수 있는지 구해보자. n=int(input())list=[] # 각 회의의 시작 시간과 끝 시간for i in range(n): s, e=map(int, input().split()) list.append((s, e)) # 튜플 형태list.sort(key=lambda x : (x[1], x[0])) # list의 자료를 하나(x) 받아서 x[1]이 우선순위, x[0]이 차순위로 정렬et=0 # 현재 회의가 끝나는 시간cnt=0for s, e in meeting: if s>=et: et=e cnt+=1print(cnt) 각 회의의 (시작 시간, 끝나는 시간)을 리스트에 저.. 결정 알고리즘 n개의 마구간이 있고 c마리의 말이 있을 때 c마리의 말들을 가능한 멀리 떨어지도록 배치한다. 이때 가장 가까운 두 말 사이의 최대 거리를 구해보자. 마구간이 수직선상에 있고 현재 사용 가능한 마구간이 1번, 2번, 4번, 8번, 9번 마구간이라면lt=1rt=9로 잡고 결정 알고리즘을 적용해보자. mid=5 이면 가장 가까운 두 말의 거리가 5라는 뜻으로 3마리의 말을 배치하고자 하면첫 번째 말이 1번 마구간,두 번째 말이 2번, 4번 마구간에 들어가지 못하고 8번 마구간에 배치될 것이다.세 번째 말은 9번 마구간에 들어가지 못하기 때문에가장 가까운 두 말의 거리가 5라고 했을 때 마구간에 말을 2마리 밖에 넣지 못한다. -> 답이 될 수 없음 -> rt를 줄인다. ............처음엔 말을 먼저.. 이분검색 lt=0rt=n-1while ltm: rt=mid-1 else: lt=mid+1 a라는 정렬된 숫자 리스트가 주어졌을 때lt는 왼쪽 인덱스로 0, rt는 오른쪽 인덱스로 (리스트의 크기-1)로 시작한다. 또한 mid는 lt와 rt를 더한 값을 2로 나누었을 때 몫을 말한다. while문을 lt가 rt보다 작거나 같다면 계속 진행하는데 (lt 반면 lt가 rt보다 커지면 더 이상 탐색할 구간이 없다는 의미이기 때문에 반복문을 종료해야 한다. 이 조건을 설정하지 않으면 탐색 범위가 끝난 뒤에도 불필요하게 반복문이 실행될 수 있다. 아래에서 예시를 들어보았다.'''a=[1, 3, 5, 7, 9, 10, 13, 14, 15]에서 m=5을 찾고자 할 때'''# 1)lt=0rt=8m.. 스도쿠 검증 이중 for문과 중 for문을 이용하여 스도쿠의 정답 여부를 판별하였다.for i in range(9): ch1=[0]*10 ch2=[0]*10 for j in range(9): ch1[a[i][j]]=1 ch2[a[j][i]]=1 if sum(ch1)!=9 or sum(ch2)!=9: return Falsefor i in range(3): for j in range(3): ch3=[0]*10 for k in range(3): for s in range(3): ch3[a[i*3+k][j*3+s]]=1 if sum(ch3)!=9: retur.. 연속된 부분 수열의 합 (투 포인터 기법 사용) 주어진 배열에서 연속된 부분 수열의 합이 m이 되는 경우의 수를 구해야 할 때.... 브루트 포스(완전 탐색) 방식을 이용한다면 O(n³)의 시간 복잡도로 시간이 초과될 가능성이 있다.# 브루트 포스 - 시간 초과for x in range(n): for y in range(x, n): sum = 0 for i in range(x, y+1): sum += a[i] if sum == m: # 합이 m이면 경우의 수 증가 cnt += 1 반면 투 포인터 방식을 이용한다면 O(n)의 시간 복잡도로 효율적이고 빠르게 답을 구할 수 있다.lt = 0 # 왼쪽 포인터 (부분 수열의 시작점)rt = 1 # 오른쪽 포인터 (부.. 이전 1 2 다음