algorithm(98)
-
백준 카드 정렬하기 코드 및 해설 (파이썬)
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net cards라는 heap에 각 카드 묶음의 카드 수를 저장합니다. cards의 길이가 1이 될 때까지 다음을 반복합니다. 최솟값 2개를 뽑아(pop) 둘의 합을 result라는 리스트에 추가하고, 둘의 합을 cards 힙에도 다시 추가합니다. 이후 다시 최솟값 2개를 뽑아 이를 반복합니다. 마지막엔 result 리스트의 모든 원소의 합을 반환합니다. sort 함수를 이용하면 시간초과가..
2021.08.12 -
프로그래머스 실패율 코드 및 해설 (파이썬)
https://programmers.co.kr/learn/courses/30/lessons/42889?language=python3 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 입력으로 받은 stages를 오름차순으로 정렬합니다. 이후 Counter를 이용해 각 스테이지별 빈도를 딕셔너리로 저장하고, 이 딕셔너리의 키를 하나씩 받으며 실패율을 계산합니다. 실패율은 (현재 키의 빈도수) / (지금까지 남아있는 사용자 수)입니다. 처음의 사용자 수는 stages의 길이로 초기화하고, 이후 사용자 수에서 현재 ..
2021.08.04 -
백준 안테나 코드 및 해설 (파이썬)
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() # 정중앙의 집..
2021.08.03 -
백준 국영수 코드 및 해설 (파이썬)
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..
2021.08.02 -
정렬
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..
2021.08.02 -
백준 병사 배치하기 코드 및 해설 (파이썬)
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에..
2021.07.29