본문 바로가기

코딩4

가장 큰 수 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers return [6, 10, .. 2021. 4. 28.
큰 수 만들기 Programmers 프로그래머스 C++ 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 number k return "1924" 2 "94" .. 2021. 4. 26.
Greedy Algorithm 탐욕법 정리 Dynamic Programming처럼 현 단계에서 이전 단계를 이끌어내는 기법에 비하여 Greedy Algorithm은 현 단계에서 가장 최적인 다음 단계를 만들어내는 기법이다. Greedy Algorithm의 가장 기본적인 원리는 최댓값 max[n] 혹은 최솟값 min[n] 에서 배열의 다음 값인 arr[n+1]의 값을 더하거나 빼서 max[n+1] 혹은 min[n+1]을 만들어내는 방식이다. 예를 들어서 a라는 지점에서 d라는 지점까지 가는 방법이 a->b->d a->c->d 2가지인 경우라고 생각을 해보자. a->b까지 걸리는 시간이 1시간, b->d까지 걸리는 시간이 1시간이고 a->c까지 걸리는 시간이 1시간 40분, c->d 까지 걸리는 시간이 40분 일 경우 우리는 당연하게도 a->b->d.. 2021. 4. 22.
Dynamic programming 동적 계획법 정리 동적 계획법의 개념은 문제에서 주어진 최종적인 결괏값을 만드는 것을 여러 개로 쪼개어 그 아랫단계로 만들어 내는 것이다. 즉 i번째의 결과를 도출해내기 위하여 i-1번째를 보고 i-1번째를 만들기 위하여 i-2번째를 참조하는 식이다. 다만 이런 예시는 단순히 반복문만으로 하드코딩을 하더라도 풀어낼 수 있다. 하지만 만약 i번째의 결과를 만들기 위하여 3가지 경우의 수가 존재한다면? DP[i] = DP[i-1] + DP[i-2] DP[i] = DP[i-2] + DP[i-3] DP[i] = DP[i-1] + DP[i-3] 와 같은 점화식이 나오고 그중에서 최댓값 혹은 최솟값을 구해야 한다면 반복문으로는 풀 수 없는 한계점에 이르게 된다. 단순히 3가지의 경우만 있더라도 10번째 최솟값을 구하기 위해선 3^1.. 2021. 4. 21.

티스토리툴바