개발 일지

위 그래프에서, V1에 위치한 노드 "1"이 V5에 위치한 노드 "12"까지 도달하는데까지 최소비용으로 갈 수 있는 경로를 찾으려고 한다. 물론 다익스트라 알고리즘을 통해 해결 가능하지만, DP 적 접근을 조명하여 문제를 해결해보고자 한다. 모든 내용은 맨 하단 남겨놓은 강의를 바탕으로 한다. "다이나믹 프로그래밍" 기법이 사용되기에 합당한 상황이란, 반복적으로 최적의 선택을 골라 답을 도출해야 하는 때 이다. 위 문제 역시 각 스테이지를 이동하며 최종적으로 가장 비용이 적게들게 하는 경로를 선택해야 하므로, DP에 대한 접근이 타당하다고 할 수 있다. 하지만 이전에 푼 백준 14501번 퇴사 문제와 마찬가지로, 최적의 경로를 찾아야 하는 상황이지만 그 최적의 경로라는 것이 최종적으로 봤을 때가 기준이라..

본 문제는 반복적으로 문자 삽입, 삭제, 교체 중 최적의 선택을 시행한다는 점에서 DP로 접근한다는 아이디어는 타당하다. 소개할 방법에서는 기본적으로 문자열 A를 순회하며 문자열 B와 비교해 현재 인덱스에 해당하는 문자에 와야할 문자를 삽입할지, 삭제할지, 교체할지 결정한다. 아래 표는 A에 sunday, B에 saturday가 입력된 경우 편집 거리 DP 테이블 이다. 여기서 편집 거리란 특정 행상태의 A가 특정 열상태의 B까지 도달하기 위한 최소 비용이다. 맨 처음 테이블을 초기화 할 때는, 문자열 A가 아무것도 입력되지 않았을 때 B의 saturday까지 입력되려면 총 8의 편집 거리가 소요되므로 dp[0][8] = 8 이 되고, 마찬가지로 문자열 B가 비어있을 때 A의 sunday가 되려면 총 6..

이해하는데 꽤 애먹은 문제였다. 풀이 자체는 굉장히 간단하다. 못생긴 수에 2,3,5 중 하나를 곱해준 결과는 항상 못생긴 수라는 것이다. 바꿔 말하면, 1부터 시작해서 2,3,5를 각각 곱해가며 못생긴 수를 만들고, 오름차순으로 나열해야 하니 후보 숫자들 중 최소값을 못생긴 수 배열 끝에 담아주는 것이다. next가 의미하는 것은, 모든 못생긴 수에 대해 2,3,5를 각각 곱해본다는 의미이다. 코드 n = int(input()) ugly = [0]*n ugly[0] = 1 i2 = i3 = i5 = 0 next2,next3,next5 = 2,3,5 for l in range(1,n): ugly[l] = min(next2,next3,next5) if ugly[l] == next2: i2 += 1 next..

문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 ..

문제 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 1 테이블과 같이 소요시간과 보상이 주어졌을 때, 각 업무를 조합하여 경우들 중 최대값을 찾아내야 하는 문제이다. 가장 먼저, 조합의 경우를 찾는 방법을 바로 알아채기가 힘드니 주어진 예시를 가시화하여 상황을 정리해본다. 아래는 예시를 가시화하여 나타낸 그림이다. 위와 같은 업무 테이블을 이용해 7일차 까지 조합의 경우의 수 중 가장 큰 값을 찾아내야한다. 1일차 업무를 하고 받는 보상과 4일차 이후 부터의 조합 중 보상의 최대값을 더한 경우, 1일차 업무를 포기하고 2일차 혹은 3일차 업무를 하는 경우로 나뉜다. 이와 같은식으로 f(i)를 i일..

보호되어 있는 글입니다.

문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[..

문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 ..

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 좀... 흥미로운 문제다. 문제의 핵심은 각 수들의 ..