파이썬 알고리즘/이분탐색 & 그리디 알고리즘

10. 역수열 (그리디)

역수열(그리디) 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞 에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 역수열은 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출 력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 자연수 N(3 1..

9. 증가 하는 수열 만들기

문제 1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열 을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니 다. 예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다. 맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽 끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다. 문제풀이 import sys sys.stdin=open("input.txt", "r") n = int(input()) p = list(map(int, input().split())..

8.침몰하는 타이타닉(그리디)

침몰하는 타이타닉(그리디) 유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있 으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요. 문제풀이1-List import sys sys.stdin=open("input.txt", "r") n, limit= map(int, input().split()) # p = list(map(int, input().split())) #일단 오름차순으로 몸무게를 정렬한다. p.sort() cnt=0 whil..

7. 창고정리

창고정리 문제는 생략 문제풀이 import sys sys.stdin=open("input.txt", "r") n = int(input()) a = list(map(int, input().split())) #리스트에 여러 값을 대입하고 싶은 경우 m = int(input()) a.sort() #Hint 오름차순으로 정렬했으므로 첫번째 요소가 최솟값이고, 맨 마지막 요소가 최대값이다. for _ in range(m): a[n-1]=a[n-1]-1 #최댓값 1감소 a[0]=a[0]+1 #최소값 1증가 a.sort() #첫번째 요소가 최솟값이 되고, 맨 마지막 요소가 최대값이 되도록 연산이 끝날때마다 지속적으로 오름차순 정렬을 한다. answer=a[n-1] - a[0] print(answer) Hint 1. ..