국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 플로이드 워셜 알고리즘 구현 문제 2. 접근 방식 - 플로이드 워셜 알고리즘을 사용 - 단, 입력을 받을 때도, 동일한 위치에 cost값이 변형 될 수 있기에 조건을 넣어줘야 한다. (처음에 이 부분을 안 넣어서 오류가 났었음) 3. 코드 import sys n = int(input()) m = int(input()) INF = 1e9 graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, n+1): if i == j: gra..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 30분 + a 1. 문제 설명 - 2개의 string이 주어질 때 1번째 string을 2번째 string으로 바꾸기 위해서 '삽입, 삭제, 교체'등의 연산을 수행할 수 있다. 이때, 최소한의 연산을 수행했을 때의 값은? 2. 접근 방식 - 2차원 배열의 DP를 활용해서 문제를 풀면된다. - 두 문자가 같은 경우 : dp[i][j] = dp[i-1][j-1] - 두 문자가 다른 경우: dp[i][j] = 1+ min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] (삽입, 삭제, 교체 순) 3. 코드 ## 최소편집거리 계산을 위..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 24분 1. 문제 설명 - 인수가 2, 3, 5로만 구성된 수를 '못생긴 수'라고 한다. 1도 못생긴 수로 포함시킬 때, n이 입력으로 주어지면 n번째 못생긴 수를 출력한다. 2. 접근 방식 - 입력으로 들어오는 n의 수가 1000이하라고 해서, 1000이하면 2, 3, 5 원소들의 순열이 1000개 이상이 될 수 있게만 하면 되겠다고 생각을 했다. - 그리고 소수를 구하는 기법인 '에라토스테네스의 체'기법을 활용하면 되겠다고 생각을 했다. - 문제를 풀기는 했는데, 답을 제출해볼 수 있는 방법이 없어서 해답을 봤는데 해답에서는 또 다른 방법으로..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 30분 + a 1. 문제 설명 - 퇴사를 앞두고 그 전까지 상담을 많이 해서 한탕 벌고자 하는데, 최대로 벌 수 있는 경우는 무엇인가? 2. 접근 방식 - 마지막 날에 상담은 절대 할 수 없다. 그렇다면 마지막 날부터 계산하면 되지 않을까? - DP[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대이익 > dp[i] = max(p[i] + dp[t[i]+i], max_value) 3. 코드 n = int(input()) t_ls = [] # 상담에 걸리는 시간 p_ls = [] # 상담 완료시 받을 수 있는 금액 for _ in range(..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 40분 + a 1. 문제 설명 - 병사들의 전투력이 적힌 리스트가 입력으로 들어올 때 내림차순으로 병사들이 정렬되도록 하고자 한다. 가장 전투력을 높게 해서 병사들을 뽑고자 할 때, 병사들을 몇 명을 빼면 되는지 묻는 문제 2. 접근 방식 - 해당 문제는 특성상 정렬을 하면 안되고, 주어진 리스트를 그대로 활용해야 했다. - 초기에는 점화식을 만들기 위해서 노력했으나 결국 그게 답이 아니라는 것은 해답을 보고서야 알았다. - DP 중 유명한 알고리즘인 '가장 긴 증가하는 부분수열 문제'였다. 지금 문제는 감소하는 순서로 찾는 것이었기에 이를 역순..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 정수값으로 이루어진 행렬이 삼각형 모양으로 주어질 때, 위에서 아래로 내려가며 각 위치의 값을 더해갈 때 최대가 되는 값은 무엇인지 묻는 문제 2. 접근 방식 - 점화식을 세워서 문제를 풀었다. (dp[i][j] = triangle[i][j] + max(dp[i-1][j], dp[i][j])) - i의 조건을 체크해줘야 된다. i가 없으면 0이어야 한다. 3. 코드 n = int(input()) triangle = [] for _ in range(n): triangle.append(list(map(int, input()..