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:]의 모든 값을..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 모든 정수를 거쳐가며 다음을 처리합니다. 첫 행은 아무 계산도 하지 않습니다 2번째 행부터 중간에 위치한 정수들은 직전 행의 오른쪽, 왼쪽 대각선의 수 중 큰 것을 더합니다. 첫 번째에 위치한 정수들은 직전 행의 첫 번째 수를 더합니다. 마지막에 위치한 정수들은 직전 행의 마지막 수를 더합니다. 계산이 끝난 후 마지막 행의 최댓값을 반환합니다. 시간 복잡도: O(N) import sys # 입력 처리하기 nums = [] # 삼각형의 크기 N = int(sys.stdi..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 31, p 375 이전에 풀이한 등굣길 문제와 유사하게 다이나믹 프로그래밍(DP)을 사용해 풀이했습니다. 입력으로 받은 금광에서 1열의 값은 그대로 두고, 2열부터 마지막 열까지 다음을 반복합니다. 첫 행의 경우 현재 위치를 왼쪽, 왼쪽 아래에서부터 접근해올 수 있습니다. 왼쪽 위는 금광이 존재하지 않습니다. 마지막 행의 경우 현재 위치를 왼쪽, 왼쪽 위에서부터 접근해올 수 있습니다. 왼쪽 아래는 금광이 존재하지 않습니다. 중간 행의 경우 현재 위치를 왼쪽, 왼쪽 위, 왼쪽 아래 모두에서 접근해올 수 있습니다. 접근해올 수 있는 모든 값들 중 최댓값을 현재 금광에서 얻을 수 있는 값과 더해줍니다. 마지막으로 마지막 열의 모든 값들 중 최댓값을..