[스택 / 큐] 프로그래머스 - 기능개발
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42586 문제 설명 : 기능 개선 작업을 수행 중이다. 문제에서는 각 기능의 개발 속도와 개발 작업의 진도가 적힌 배열이 주어진다. 작업 진도 배열에서 뒤에 있는 원소는 앞에 있는 원소보다 우선 배포할 수 없다. 만약 0번째에 있는 작업이 100% 완성되었을 때, 1번째에 있는 작업은 이미 완성된 후라면 첫 번째 배포 날에 1번 작업까지 배포할 수 있다. 각 배포마다 몇 개의 기능을 배포할 수 있는지를 return 하는 함수를 만들어 보자. 입출력 예시 progresses speeds return [93, 30, 55] [1, 30, 5] [2, 1] [95, 90, 99, 99, 80, 99] [..
2021. 10. 24.
2021.6.13 TIL : [알고리즘] 백트래킹 (BackTracking)
마지막 알고리즘 수업에서는 백트래킹과 NP-완전을 배웠다. 둘 다 조금은 이해하기 어렵다고 느껴져서 오늘은 이 내용을 정리해보고자 한다. 문제에서 어떤 해를 구할 때, 해의 형태가 n개의 원소로 이루어진 튜플인 경우가 있다. (이 때, 이 튜플 내의 각 원소를 x1, x2, x3, ... xn이라고 한다.) 해의 원소들(xi)은 유한 집합(Si)에서 선택된다. 백트래킹은 기준함수인 P를 최대화/최소화/만족하는 해를 구하는 문제를 해결하는데 적용하는 방법으로 효율적인 알고리즘이 존재하지 않을 경우에 사용한다. 모든 문제의 사례에 대해서 효율적이진 않지만 많은 문제 사례에서 효율적이다. mi를 Si의 크기, 즉 원소의 개수라고 하면, xi가 선택할 수 있는 해는 각각 m1, m2, m3, ..., mi, ...
2021. 6. 13.
