https://programmers.co.kr/learn/courses/30/lessons/42889?language=python3 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 입력으로 받은 stages를 오름차순으로 정렬합니다. 이후 Counter를 이용해 각 스테이지별 빈도를 딕셔너리로 저장하고, 이 딕셔너리의 키를 하나씩 받으며 실패율을 계산합니다. 실패율은 (현재 키의 빈도수) / (지금까지 남아있는 사용자 수)입니다. 처음의 사용자 수는 stages의 길이로 초기화하고, 이후 사용자 수에서 현재 ..

https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 집들의 위치를 houses라는 리스트에 저장하고 이를 오름차순으로 정렬합니다. 집들의 개수를 N으로 저장하고, 정중앙의 집인 N을 2로 나눈 몫번째 집에 안테나를 설치합니다. import sys # 집의 개수 N = int(sys.stdin.readline()) # 집의 위치 houses = list(map(int, sys.stdin.readline().split())) # 정렬 houses.sort() # 정중앙의 집..

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net sort의 key를 활용해 문제의 조건에 맞게 정렬했습니다. 디폴트로 오름차순으로 정렬되므로, 내림차순으로 정렬되어야 할 경우엔 -를 붙여 내림차순으로 정렬되도록 했습니다. import sys # 학생 수 N = int(sys.stdin.readline()) students = [] for i in range(N): # 이름, 국어, 영어, 수학 name, korean, en..

1. 선택정렬 • 정렬되지 않은 리스트의 최솟값을 정렬된 리스트의 마지막에 추가한다 # 선택 정렬 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i # 최솟값의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # swap print(array) 2. 삽입 정렬 • 하나의 값씩 정렬된 리스트 내의 적절한 위치에 삽입한다 # 삽입 정렬 array = [7,5,9,0,3,1,6,2,4,8] for i in range(1, len(arr..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net '가장 긴 증가하는 부분 수열(LIS)'을 이용해 풀이했습니다. 이 문제는 오름차순이 아니라 내림차순을 요구하므로, 점화식의 부등호 방향만 바꾸어줬습니다. dp는 모두 1로 초기화하고, soldiers는 입력으로 받은 병사들의 전투력을 저장합니다. 점화식: 모든 0 soldiers[i] 이후 dp의 최댓값을 구하면 가장 긴 내림차순 부분 수열의 길이가 되고, 이를 전체 병사의 수인 N에..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 각 날짜까지의 누적 이익을 담은 dp 리스트를 만들고, 다이나믹 프로그래밍으로 풀이했습니다. 처음엔 모두 0으로 초기화합니다. 입력을 받으면서 start는 현재 일이 시작되는 날, end는 현재 일이 끝나는 날, profit은 현재 일로 얻을 수 있는 이익으로 정의합니다. (현재 일이 시작되기 전까지의 이익 + 현재 일을 끝낸 후의 이익)과 (일이 끝나는 날의 기존 dp 값) 중 큰 값을 dp[end]로 갱신합니다. 이때 end+1일 이후의 누적 이익이 end일까지의 누적 이익보다 적을 수 없으므로 , dp[end+1:]의 모든 값을..