나를 잃지 말자

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

비고:

-Binary search

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

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

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

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

-난이도하

내소스코드:

boj.kr/9016f079aa1344f59b645ee752dc460c

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

비고:

-Dynamic programming

-예제2에서 문제 포인트를 알아차려야했는데 놓쳤다.

2 1 -4 3 4 -4 6 5 -5 1 에서 6 5->11이 답이라고 착각하였다. 답은 3 4 -4 6 5로 14다.

-여기서부터 문제를 파악하고 해결해 나가자.

-각 index마다 left max값과 right max값 그리고 index에서의 값을 다 더하고 취합하고 취합한 것에서 max를 구하면 된다.

-각 점마다 left max를 dictionary로 박자. 이 때, index가 작은 순부터 left max를 구하는 것에서 dynamic programming

-0에서는 left max가 0, 1에서는 left max가 0에서의 leftmax + 0에서의 값, 이 때 이 더한 값이 음수면 1에서의 leftmax는 0, 양수면 그 값을 1에서의 left max로 택한다.

-이러면 n번의 계산으로 모든 점에서의 left max를 구한다.

-마찬가지로 n번의 계산으로 모든 점에서의 right max를 구한다.

-문제파악에서 차질이 생겼다. 다음에는 반드시 예제의 정답을 믿자. 예제가 틀렸다고 생각하다니...ㅉㅉ

-게다가 사람들이 많이 푼 문제에 오류가 있다고 생각하면 되겠냐

-난이도중

내소스코드:

boj.kr/12104c7b668241f7b7ef8ee4d6ab8541

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

비고:

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

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

-난이도하

내소스코드:

boj.kr/39dad1f4b4aa4923a86f5f3f9d298ff4

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

비고:

-dfs로 돌면서 label(dictionary)를 잡고 돌고

-이웃node가 label이 없으면 이전 nodes' label과 반대로 달고

-새로운 node마다 labeled 이웃 전체(이전 node를 지우고하는게 아니라)에 대해 label이 같은지 테스트가 관건

-난이도 중

내소스코드:

boj.kr/79b09fa7f4294aa19104a5d58d317c05

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

비고:

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

-list.sort(key=lambda x: (x[1],x[0])) 형태로 주면, multiple fields에 대해 우선순위 줘가며 sorting이 가능

-다음 케이스를 놓쳐서 오래 걸림

5

4 4

4 4

3 4 

2 4 

1 4

정답은 3

-즉 포인트는 같은 종료 시간 내에 시작 시간을 정렬해야 한다는 점과 그 때 단순히 이어진 시작 시간 2개 교체해나가는 바람에 100%에서도 틀렸습니다를 얻게됨

-생각보다 오래걸림 ㅠㅠ

-난이도가 중

내소스코드:

boj.kr/d38992bbf196403e87c8619016a051c2

문제: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/2133

비고:

-Dynamic programming 활용

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

점화식을 D[n] = 3*D[n-2] + 2*D[n-4]로 생각했다가 고생했다.

여기서 3은

--

||

||케이스와

--

--

--케이스

||

||

--케이스 해서 총 3가지

2는

----

|--|

|--|와

|--|

|--|

----

이 때 n=6일 때 고려하지 못한 케이스가

------

|----|

|----|와

|----|

|----|

------이다.

따라서, 경우를 나눌 때, 우측 상단에 --로 시작해서

--

--

--로 끝나는 경우와

--

 |

 |

그리고

 |

--

--인 경우, 근데 마지막 2가지는 상하대칭성을 띄니까 1개의 함수로 세자

따라서, 구하고자하는 ans(n)과 보조함수 aux(n)을 정의

ans(n) = ans(n-2) + aux(n-1)

aux(n) = ans(n-1) + aux(n-1)

ans(0) = 1, ans(1) = 0

aux(0) = 0, aux(1) = 1로 두고 풀면 된다.

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

내소스코드:

boj.kr/7be8dbc0db4445888d24df8c7db663e8

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

비고:

-Dynamic programming 활용

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

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

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

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

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

내소스코드:

boj.kr/d99f1a90f14341a090c4ba58bd460c33