알고리즘 문제풀이 리뷰2

역시나 푼지 좀 오래됐지만 괜찮은 문제들 리뷰하기

 

https://www.acmicpc.net/problem/26601

가장 작은 수 P5

분류 : 수학, 에라토스테네스의 체

 

다른사람한테 소개받은 문제의 입력덕분에 접근이 쉬워지는 문제

약수의 개수에 대한 조건을 잘 생각해보며 풀어보자

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj26000-26999/boj26601.cpp

 

https://www.acmicpc.net/problem/16287

Parcel P5

분류 : dp, mitm

 

mitm 알고리즘에 대해 찾아보게 된 계기가 된 문제.

mitm의 흐름을 기억하며

만들어진 무게가 sum이 되는지 와 중복되서 선택되지 않았는지를 판단하며 존재 여부만 확인한다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj16000-16999/boj16287.cpp

 

https://www.acmicpc.net/problem/16432

떡장수와 호랑이 G4

분류 : dp, dfs

 

dfs를 이용하여 접근하되 캐싱을 하지 않으면 모든 경우의 수에 대해서 진행되어 시간초과가 난다.

캐싱을 하고 백트래킹을 가능하게 구현하면 되는문제

rgb거리와 비슷한 느낌의 문제이다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj16000-16999/boj16432.cpp

 

https://www.acmicpc.net/problem/1700

멀티탭 스케줄링 G1

분류 : 그리디

 

이 문제가 인상깊었던 이유는 운영체제 시간에 배운 개념을 사용하는 문제였기 때문인것같다.

프로세스 스케줄링 기법중에서 최적의 스케줄링이 될려면 다음에 가장 늦게 올 스케줄을 먼저 제거하면 된다.

이는 이상적인 내용이기 때문에 실제로는 이루어질 수 없다고 기억한다.

이를 구현하면 정답이 된다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj1000-1999/boj1700.cpp