나를 잃지 말자

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

비고:

-Brute force

-next permutation만 있으면 해결됨

-난이도중

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

비고:

-Brute force

-다 세지 않고선 규칙을 발견하기 힘들며, 영역 나누기도 힘들어 보이며, 주어진 조건이 가용 시간/메모리 내에 해결 가능

-이런 문제에서 모든 경우를 세기 위해서 next permutation함수를 잘 짜야 한다.

-입력받은 list을 next permutation으로 바꾸며, return은 True/False로 작성

-next permutation을 처음작성하는 거라면 난이도가 있다.

  -기본 규칙은, 배열의 index 0부터(=좌측부터) 우측으로 훑으며 "마지막" 증가(increase)인 index(i)를 찾는다.

  ex) 124653에서 46가 마지막 증가(<)고 4의 index인 2

  -마지막 증가에서의 값보다 크며 가장 우측에 존재하는 값의 index(j)를 찾는다.

  ex) 124653에서 65중에서 5가 더 오른쪽, 5의 index인 4

  -i,j에서의 값 교환

  ex) 124653 -> 125643

  -j보다 우측의 값들을 정렬시킨다.

-난이도중

내소스코드:

boj.kr/33b0cb84fe5d4b48b02c860081023606

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