728x90 728x90 알고리즘/문제 해결 전략2 탐욕 알고리즘 Greedy Algorithm [문제해결전략] ( 프로그래머스 요격 시스템) 탐욕 알고리즘(Greedy Algorithm)이란? 현재 상태에서 최선의 선택을 하며 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘 문제를 해결하는 단계 1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다. 2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다. 3. 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택절차로 돌아가 위 과정을 반복한다. 탐욕 알고리즘은 요격시스템을 풀면서 알게되었다. 처음에는 도통 어떻게 푸는지 몰랐는데 어떻게 푸는지 알게되면 그때부터 쉽게 풀리는 듯 하다. 프로그래머스 - 요격 시스템 https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. .. 2023. 12. 2. 다이나믹프로그래밍 DP (=동적계획법) [문제 해결 전략] 다이나믹 프로그래밍 DP ( = 동적 계획법) 하나의 큰 문제를 여러개의 작은 문제로 나눠서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 문제 해결 법을 말한다.기억하며 풀기라고 할 수 있다. 다이나믹 프로그래밍은 분할정복과 비슷한데 여기서 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 후 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다음에 또 나오면 저장해둔 정답을 사용하며 속도를 향상시킨다. 방법론 1. 메모이제이션 배열로 -1 -1 -1 입력한 상태에서 부분적으로 답이 나오면 채워 넣는다. 이미 채워져있을 경우 그 값을 사용한다. function fibbo(n) if memo[n] != -1 // 이미 n번째 값을 구해본 적이 있다면 return memo[n.. 2023. 9. 2. 이전 1 다음 728x90 728x90
