본문 바로가기

728x90

Dynamic Programming4

[Swift] 2022 KAKAO TECH INTERNSHIP 코딩 테스트 공부 Problem 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Solution 해당 문제는 다이나믹 프로그래밍으로 풀어야 하는 문제이다. 1. 알고력과 코딩력의 최대치를 구해준다. 문제를 모두 풀 수 있다는 것은 알고력과 코딩력의 최대치를 얻는 다는 것이므로 미리 구해준다. var maxAlp: Int = alp var maxCop: Int = cop problems.forEach { maxAlp = max(maxAlp,$0[0]) maxCop = max(maxCop,$0[1]) } 2. dp 배열을 알고력 + 1 , 코딩력 + 1개의 이중 배열을 만들어 .. 2022. 8. 26.

[Swift] 프로그래머스 올바른 괄호의 갯수 Problem 코딩테스트 연습 - 올바른 괄호의 갯수 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모 programmers.co.kr Solution 해당 문제는 다이나믹 프로그래밍을 이용해야 하는 문제입니다. 다이나믹 프로그래밍으로 괄호가 1쌍인 것부터 주어진 n쌍까지 차근 차근 풀어나가야 하는데요. 직접 구해보기 괄호가 1쌍일 땐 경우의 수가 -> ()만 존재합니다. 괄호가 2쌍일 경우 -> ()(),(()) 이렇게 두 개가 존재합니다. 괄호가 3쌍일 경우 -> ((())), (()()), (())(), ()(()),()()() 이렇게 5.. 2022. 3. 6.

[Algorithm] 동적 계획법(Dynamic Programming)이란? 안녕하세요 Foma 💻 입니다! 그 동안 알고리즘 문제를 풀면서 동적 계획법 관련된 문제가 나오면 어려움을 겪곤 했는데요.. 오늘은 동적 계획법에 대해서 제대로 정리를 해보려고 합니다. 바로 시작할게요! 동적 계획법(Dynamic Programming)이란? 다이나믹 프로그래밍은 1950년대 미국의 수학자인 리처드 벨맨이 최적화 문제(Optimization Problem)를 해결하기 위해서 고안되었다. 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말하며 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키 백과 - 즉, 분할 정복 알고리즘과 같이 큰 문제를 작게 쪼개서 문제를 해결해 나가는 알고리즘입니다. 다.. 2021. 12. 9.

[Swift] 프로그래머스 스티커 모으기(2) Problem 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr Solution 해당 문제는 DP(Dynamic Programming)으로 풀어야 하는 문제입니다. 1. 스티커의 갯수가 3개 이하라면 가장 큰 수를 반환한다. 스티커의 갯수가 3개 이하라면 하나밖에 뗄 수 없으므로 가장 큰 수를 반환합니다. if sticker.count < 4 { return sticker.max()!} 2. 첫 번째 스티커를 뜯어냈을 경우와 두 번째 스티커를 뜯어냈을 경우의 dp를 만들어줍니다. var dp1:.. 2021. 10. 19.

이전 1 다음

728x90

티스토리툴바