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열부터 마지막 열까지 다음을 반복합니다. 첫 행의 경우 현재 위치를 왼쪽, 왼쪽 아래에서부터 접근해올 수 있습니다. 왼쪽 위는 금광이 존재하지 않습니다. 마지막 행의 경우 현재 위치를 왼쪽, 왼쪽 위에서부터 접근해올 수 있습니다. 왼쪽 아래는 금광이 존재하지 않습니다. 중간 행의 경우 현재 위치를 왼쪽, 왼쪽 위, 왼쪽 아래 모두에서 접근해올 수 있습니다. 접근해올 수 있는 모든 값들 중 최댓값을 현재 금광에서 얻을 수 있는 값과 더해줍니다. 마지막으로 마지막 열의 모든 값들 중 최댓값을..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 43, p 397 크루스칼 알고리즘을 이용해 최소 비용의 신장 트리를 탐색했습니다. 최종 반환해야 할 답이 절약할 수 있는 최대 금액이므로, 전체 도로에 가로등을 설치하는데 드는 비용을 total_cost로 저장하고, 최소 신장 트리를 만들었을 때 가로등을 설치하는데 드는 비용을 min_cost로 저장하여 둘의 차를 반환했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 집의 수 N = inputs[0] parent = [0] * N for i in range(N): parent[i] = i # 도로의 수 M = inputs[1] # (도로의 길이, 도로..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 42, p 395 비행기를 '최대' 몇 대 도킹할 수 있는지 출력해야 하므로 이진 탐색을 이용해 풀이했습니다. 먼저 도킹할 수 있는 비행기의 최소 대수를 1대, 최대 대수를 게이트의 개수인 G대로 설정합니다. 이후 중간값을 계산하고, 이 중간값만큼의 비행기를 도킹할 수 있는지 확인합니다. 비행기를 순서대로 도킹한다고 했으므로, 중간값 개수만큼의 도킹 정보를 가져오고, 이를 dock라는 함수에 전달합니다. dock 함수는 도킹 정보 리스트를 받아 모든 비행기를 도킹할 수 있으면 True, 아니면 False를 반환하는 함수입니다. 이는 힙을 이용해 구현했는데, 파이썬의 heapq는 Min Heap이므로, Max Heap으로 사용하기 위해 각 el..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 41, p 393 서로소 집합을 이용해 여행 계획 안에 있는 여행지들이 모두 같은 집합에 속하면 예행 계획이 가능한 것으로, 그렇지 않으면 불가능한 것으로 풀이했습니다. 연결된 도시들의 정보가 리스트가 아닌 행렬로 주어지므로 행렬의 값 중 0이 아니라 1인 부분의 좌표를 통해 연결된 도시들의 정보를 담은 리스트 links를 생성했습니다. 이를 이용해 서로소 집합 알고리즘을 수행하고, 계획에 있는 도시들이 속한 집합을 확인해 이들이 모두 같으면 YES, 아니면 NO를 출력했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 여행지의 수 N = inputs[0..