나를 잃지 말자

문제:www.acmicpc.net/problem/1920

비고:

-Binary search

-문제를 딱보고, 찾아야하는 수를 region에 for문 돌리는 상황생각하면, region 전체를 훑는게 비효율적임을 느껴야한다.

-실무에서도 그냥 search가 자주 일어난다면, 기존 region을 정렬해둬야 함을 알아차려야한다.

-그리고 찾아야하는 것과 region 사이에 대소비교를 할 key field가 필요해야함을 알아야 한다.

-재귀함수를 작성함에 있어서, (성공, 불가능, 오답, 계속) 형태로 작성하자. 즉, 종료하는 케이스가 일찍이 나오게 해줘야 무한 루프에 빠지지 않을 가능성을 높여준다. 

-난이도하

내소스코드:

boj.kr/9016f079aa1344f59b645ee752dc460c

문제:www.acmicpc.net/problem/2630

비고:

-Divide and conquer(분할-정복-조합)

-checker, divider, solve를 정의하여 사용, 최종적인 result인 dictionary를 유지

-난이도하

내소스코드:

boj.kr/39dad1f4b4aa4923a86f5f3f9d298ff4

문제:https://www.acmicpc.net/problem/12845

비고:

-Greedy algorithm 문제가 뭐 없나 찾아보던 중 발견했는데, 너무 쉬운 문제

-Greedy를 떠나서, 잘 살펴보면 결국 max값이 (N-1)번 더해지고, 남은 것들을 더해주기만 하면 된다.

-따라서 Subproblem을 떠나서 Explicit solution을 구해버릴 수가 있음

-난이도가 낮음

내소스코드:

boj.kr/2d49ff4b4e924b0693a2574534588dd4

문제:https://www.acmicpc.net/problem/11047

비고:

-Greedy algorithm 활용(Optimal substructure, Greedy choice property)

-python3, divmod를 통해 몫과 나머지를 바로 구함

-난이도가 낮음

내소스코드:

boj.kr/d957b77f0a804e328ac66afd615ac0c6

문제:https://www.acmicpc.net/problem/14852

비고:

-Dynamic programming 활용

-점화식을 짤 때, 1개만 할지 보조를 둬야할 지 감이 옴

-이 문제는 다음과 같음

  -f(0)=1, f(1)=2, g(1) = 1

  -g(n) = g(n-1) + f(n-1)

  -f(n) = f(n-2) + g(n-1) + f(n-1) + g(n)

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

-결과를 나머지로 뱉어야되는 경우, 개별 계산에서 미리해서 숫자 절댓값 줄여서 계산하기 필요(이 짓을 안했더니 "시간초과" 받음)

내소스코드:

boj.kr/782710fea2044c59b94b89039aa4c440

문제:https://www.acmicpc.net/problem/11726

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = D[n-1] + (D[n-2] * 2), *2로 생각하면 안됨

(D[n-2]에서 2x1을 2개, 1x2을 2개 사용하는 방식 총 2가지니까 *2하려고한다면, 2개 중 전자는 D[n-1]에서 count해서 중복발생)

따라서 D[n] = D[n-1] + D[n-2]

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/a173cca197ca42eb88e87bd88c47a6ba