[자바스크립트] 그리디 (Greedy) 알고리즘

그리디(Greedy) 알고리즘 지금 순간에 가장 최적의 해를 선택하는 알고리즘 다음과 같이 위에서 아래로 이동하면서 거쳐가는 노드의 합이 가장 큰길을 찾고자 한다면 그리디 알고리즘은 아래와 같이 찾아냅니다. 노드 5에서 봤을 때는 다음으로 가장 높은 수가 100이므로 100을 선택하고, 100에서는 30을 선택합니다. 하지만 실제로 가장 높은 노드의 합은 5에서 10을 거쳐 500으로 가는 길입니다. 이렇듯 그리디 알고리즘은 항상 최적의 해를 보장해주지는 못합니다. 그리디 알고리즘은 이럴 때 좋습니다 근사 알고리즘 위에서 봤다시피 항상 최적의 해를 보장해주지는 못하지만, 어느 정도 최적에 근사한 답을 알려줍니다. 그래서 "적당히 괜찮은 해답"을 얻기 위해서는 최적의 알고리즘입니다. 또한 뒤의 경우를 더 ..

→2021.08.05

[프로그래머스 LV1] x만큼 간격이 있는 n개의 숫자 문제 풀이 (Javascript)

문제 설명 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요. 제한 조건 x는 -10000000 이상, 10000000 이하인 정수입니다. n은 1000 이하인 자연수입니다. 입출력 예 x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] 정답 풀이 function solution(x, n) { let answer = []; for (let i = 1; i

→2021.07.06

[프로그래머스 LV1] 소수 만들기 문제 풀이 (Javascript)

문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 입출력 예 nums result [1,2,3,4] 1 [1,2,7,6,4] 4 입출력 예 설명 입출력 예 #1 [1,2,4]를 이용해서 7을 만들 수 있습니다. 입출력 예 #2 [1,2,4]를 이용해서 7을 만들 수 있습니다. [1,4,6]을 이용..

→2021.07.05

[프로그래머스 LV1] 완주하지 못한 선수 문제 풀이 (Javascript)

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return ["leo", "kik..

→2021.07.05