Algorithm/Dynamic Programming

Algorithm/Dynamic Programming
[Google 인터뷰] 못생긴 수
문제 못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12... 이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라. 입출력 입력 출력 10 12 4 4 초기접근 1001크기의 리스트를 만들고 각 인덱스에 1이 표시되어있으면 못생긴 수로 판단한다. dp = [0]*1001 dp[1], dp[2], dp[3], dp[5]를 1로 표시한다. 0인 값들을 2,3,5로 나눠보고 나누어떨어지면 1로 표시한다. 1로 표시된 것들의 개수를 세어나가면서 n이 되면 종료하고 해당 인덱스를 출력한다..
→2021.03.10
Algorithm/Dynamic Programming
[Goldman Sachs 인터뷰] 편집 거리
초기 접근 글자 하나하나 마다 문자를 수정하는 경우의 수를 구하고 가장 작을때의 경우를 배열에 저장해둔다. 의 문제점 : 가장 작을때가 아니라 같을 때 다음 글자에서 어떤 경우였는지를 알아야한다. 그럼 2차원배열에 저장해야하는데 이 3가지 경우의 수를 어떻게 표현할까.. 해결 아이디어 주어진 단어 두개를 2차원 배열에 표시하면 위치에 따라 3가지 경우의 수로 나눌 수 있다. 예를들어 sunday, saturday 두 단어가 주어졌다고 가정해보자. 2차월 배열로 나타내면 아래와 같다. 들어가는 정보는 original 단어에서 new 단어로 바뀔때 최소편집거리를 써준다. 예를들어) dp[0][0] ~ dp[0][8] 까지는 0(아무것도 없는 상태에서) s, sa, sat, satu, satur, ... 로 ..
→2021.02.21
Algorithm/Dynamic Programming
[백준 18353] 병사 배치하기
문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 ..
→2021.02.17
Algorithm/Dynamic Programming
[백준 14501] 퇴사
문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15..
→2021.02.13
Algorithm/Dynamic Programming
[FlipKart 인터뷰] 금광
초기접근 점화식 세우는 과정은 어렵지 않았다. 각 단계는 전 단계에서 올 수 있는 경우중에 가장큰 수 + 해당 금광수 이다. 이것을 점화식으로 나타내면 d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j] 이다. 여기서 가장 위쪽과 아래쪽은 전단계에서 오는 경우의 수가 1개가 적다. 이것을 따로 구현하는 것 보다 data와 d 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다. 해결 아이디어 1. 점화식 : d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j] 2. 쉽게 구현하기 : 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다. 정답코드 tc = int(input()) for t i..
→2021.02.10
Algorithm/Dynamic Programming
다이나믹 프로그래밍 문제접근
DP조건에 맞는지 확인하는 방법 1. 큰 문제를 작은문제로 나눌 수 있다. 2. 동일한 작은 문제를 반복적으로 해결한다. 처음에 딱 문제를 볼때 접근해야하는 과정 1. 그리디, 구현, 완전탐색인지 확인한다 2. 방법이 떠오르지 않으면 DP 조건을 확인해본다. 3. 재귀로 비효율적인 완전탐색을 구현해보고 4. 작은 문제로 큰 문제 해결이 가능하면 DP로 코드개선을 한다. 일반적인 코테의 DP문제는 기본유형으로 낸다. = 점화식만 세우면 구현은 쉽다.
→2021.02.09

• 이전
• 1
• 다음