백준 알고리즘 강의 후기(코드플러스): 중급2

백준/BOJ/코드플러스/알고리즘 강의 후기

수강신청해서 보세요~! 정말 돈 하나도 안아깝습니다. :)

12/31 복습: 처음부터~

1/2 복습: 연습1~

● 1000 - 다이나믹 프로그래밍 2 - 25/15/32분

백준 11048 이동하기 www.acmicpc.net/problem/11048

여러가지방법으로 다이나믹을 푸는것을 설명하는 강의

특징1. 큰문제에서 작아지고 있다. => DP

특징2. 한번 오른쪽이나 아래로 가면 되돌아갈 수 없다.

방법1. 점화식

max(어디서 올때 가장큰가) + 현재값

다이나믹에서는 0으로 초기화해놓고 인덱스1부터 쓰는것이 좋을때가 많다.

방법2. 점화식

어디로 갈수있는가?

max(있을수있는값, 현재에서 건너간 새값)

방법3. 문제의 조건과 이동방법의 특징을 이용.

대각선 이동은 처리하지 않아도된다. 직각 코너를 이용하지 않는것은 가장 작은 사탕이기 때문이다.

방법4. 탑다운 방식(이전거는 다 바텀업 방식)을 재귀로 이용해보자. 탑다운방식과 바텀업방식의 차이 및 만드는 방법

함수호출로 변경하고, 메모이제이션을 초과한다 -> 그냥 하면 시간초과

그래서 미리 -1로 초기화 한 후에 진행

방법5. 점화식의 변형 (1,1) -> (i, j)로 했었는데, 시작을 (i,j)로 도착을 (N, M)로 변경

go(1,1)호출로 시작함.

백준 11060 점프 점프 www.acmicpc.net/problem/11060

다이나믹 설계법 : 알수없는 정보는 정말 중요하고 좋은것이다. 그게 DP설계의 핵심이므로.

방법1. 어디에서 왔나?

갈수 있는칸, 없는칸 모든칸 다 조사함.

방법2. 어디로 갈수있나?

이 방법이 더 좋다.

백준 15486 퇴사 2 www.acmicpc.net/problem/15486

점프점프와 유사함

두가지 다음날인 i+t[i]와 i+1에 대해서 각각

i 를 통하지 않고 온 경우와, i를 통해서 온경우의 max를 구해줌

백준 10942 팰린드롬? www.acmicpc.net/problem/10942

재귀방식과 반복문방식 두가지가 있다.

쿼리문제라서 다르게 접근해야된다.

일반적인 순서로 하는게 아니고 대각선 순서라서,(예: 가장 큰 값이 오른쪽 위, 가장 작은값이 가장 큰 i == j 대각선) 재귀로 해야한다.

1, 2, 3 더하기 4 www.acmicpc.net/problem/15989

순서대로 세는것

백준 11066 파일 합치기 www.acmicpc.net/problem/11066

다이나믹으로 풀수있는 이유: 연속되기 때문이다.

k를 앞에서 부터 뒤로 옮기면서

go(i,k) + go(k+1,j) + sum 을 구해줌

백준 12865 평범한 배낭 www.acmicpc.net/problem/12865

각각의 물건에 가방에 들어가거나 들어가지않거나, 즉 N^2너무 크다.

하지만 무게 제한이 있기 때문에 풀수있는 문제로 바뀐다.

이차원배열을 일차원으로 바꾸려면 배열에 기존에 쓴 값이 덮히지 않게 뒤에서 부터 작업해줘야함..

백준 1495 기타리스트 www.acmicpc.net/problem/1495

평범한 배낭과 유사한 문제.

M개보다 작다는 조건을 이용해 NM다이나믹을 시도해볼수 있음

백준 12869 뮤탈리스크 - 골드4 www.acmicpc.net/problem/12869

재귀의 장점은 배열은 음수인덱스를 넣을수 없지만 재귀는 그게 처리 가능하다.

백준 10422 괄호 - 골드 5 www.acmicpc.net/problem/10422

너무 신박해서 충격받음... O(N^2)

한번 닫는 괄호가 더 많아지게 되면 뒤에 뭐가 와도 무조건 실패 한다는것.

방법1.

방법2.

XXXX) => D[N-1][L+1]

XXXX( => D[N-1][L-1]

● 1001 - 다이나믹 프로그래밍 2 (연습) - 29분/32분

동전 1

이건 안풀어주네, 1,2,3 더하기 4와 비슷, 여기서는 덧셈을구한다

동전 2

이것도 안풀어줌. 위에거랑 비슷한데 여기서는 최소를 구한다.

크리보드

키보드 눌러주는 규칙으로 식을 잘 만들자

점프

점프점프와 비슷. 두가지방법이 있다.

1. 새 칸에 올수있는 방법을 조사(비효율적임) N^3 => 왼쪽고 위에있는 모든칸이 I,J로 갈수있는것도 아닌데 모두다 조사하기 때문이다.

2. 갈수있는곳을 조사(오른쪽, 아랫쪽) N^2

행렬 곱셈 순서

DP2의 파일합치기와 같은 문제. N^3

1학년 - 골드1

기타리스트 문제와 비슷, 숫자 사이에 플러스 마이넣스를 넣을수있으니까 경우의 수는 2^N

마지막은 등호를 넣어야 하니까 -1하고 시작함.

O(20N)

2^N 또는 NM 중에서 작은것 선택하여 풀기

ABC - 골드1 www.acmicpc.net/problem/12969

c = i - a - b

배열과 리턴을 이용해서 구현을 약간 다르게 함.

출근 기록 - 골드3 www.acmicpc.net/problem/14238

오차원 다이나믹

ABC와 유사하게

BOJ 거리 - 실버1 www.acmicpc.net/problem/12026

풀어보기

강의 연습2

백준 12996 Acka - 골드3 www.acmicpc.net/problem/12996

사차원다이나믹. 음수를 편하게 처리하기 위해 재귀로 구현

백준 2281 데스노트 - 골드4 www.acmicpc.net/problem/2281

이름을 이줄에 쓸건지 다음줄에 쓸건지 중에 정해야된다.

D[index][count]

- 다음줄에 쓸 경우: space:(M-count+1),

A[index] go(index+1, A[index+1]) + space^2

- 현재줄에 쓸 경우: go(index+1, count+1 + A[index])

백준 3012 올바른 괄호 문자열 - 플래티넘3 www.acmicpc.net/problem/3012

DP2의 괄호의개수 문제랑 비슷

D[i][j] : i~j 문자열의 올바른 괄호갯수

i는 항상 여는 괄호가 되어야 한다. i ~ k , k+1~j : k를 짝이맞는 닫는괄호 혹은?로 정의

다이나믹보다 5자리넘는거 나머지연산 처리하는 부분이 더 어렵다

백준 2616 소형기관차 - 골드4 www.acmicpc.net/problem/2616

N개를 그룹으로 나눈 문제고 그건 k 개가 되어야 한다.

백준 1413 박스 안의 열쇠 - 플래티넘4 www.acmicpc.net/problem/1413

이 수는 제 1종 스털링수 와 같다 stirling numbers of the first kind

팔굽혀펴기 - 골드1 www.acmicpc.net/problem/10564

기타리스트볼륨, 배낭 등등과 비슷함 1학년 등

D[i][j] = 총 팔굽혀펴기를 i번 했고, 이 때 점수 j가 가능한가?

건배 - 플래티넘5 (The bavarian beer party) www.acmicpc.net/problem/1970

괄호문제와 유사함, 올바른 괄호 문자열도 비슷. 특히 괄호 안의 내용과 밖의 내용은 서로 관련없는 점이 유사하다.

원형인것은 크게 의미가 없다.

i~k~j 쓰는것을 잘하도록 연습하자.

초콜릿 자르기 - 브론즈3 www.acmicpc.net/problem/2163

핵심은. 자르고 나면 서로 연관이 없는 독립적인 문제가 된다는것.

● 1002 - 다이나믹 프로그래밍 2 (도전) - 15분

백준 12872 플레이리스트 - 골드2 www.acmicpc.net/problem/12872

문제

수빈이는 BOJ 알고리즘 캠프에서 음악을 들으면서 문제를 풀고 있다. 지금 수빈이의 스마트폰에는 N개의 노래가 저장되어 있다. 오늘 수빈이는 P개의 노래를 들으려고 한다. 수빈이는 다음과 같은 조건을 만족하는 플레이리스트를 만들려고 한다. 플레이리스트에는 같은 노래를 여러 번 추가해도 된다.

모든 노래를 플레이리스트에 추가해야 한다.
같은 노래를 추가하려면, 플레이리스트에서 두 노래 사이에 적어도 M개의 곡이 있어야 한다.

수빈이는 플레이리스트를 만들 수 있는 경우의 수가 궁금해졌다. N, M, P가 주어졌을 때, 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, P가 주어진다. (1 ≤ N ≤ 100, 0 ≤ M ≤ N, N ≤ P ≤ 100)

출력

첫째 줄에 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 출력한다. 경우의 수가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다.

M은 항상 다른곡으로 이루어져있다.

따라서 노래를 두개의 그룹으로 나눌 수 있다.

- 그룹 X: 이미 추가한 노래

- 그룹 Y: 아직 추가하지 않은 노래

d[p][x][y] = p번째 곡을 선택할것이고, x 와 y의 크기

1. 그룹 y에 있는 노래를 추가: D[p+1][x+1][y-1]

2. 그룹 x에 있는 노래를 추가: D[p+1][x][y]

N-Rook II - 플래티넘3 www.acmicpc.net/problem/1767

문제

체스 세계랭킹 1위의 숌은 더 이상 체스를 대결할 상대가 없자, 새로운 체스방법을 생각했다.

일단 Rook은 체스판의 같은 열, 혹은 같은 행에 다른 말이 있을 경우, 그 말을 공격할 수 있는 말이다.

숌은 N * M 크기의 체스판에 K개의 룩을 놓는데, 서로 공격받지 않는 경우의 수를 구하는 문제를 생각했다. 이 문제는 너무 쉽게 풀려서 숌은 좀 더 어려운 문제를 찾다가 각 룩이 최대 1개의 룩에만 공격받는 경우의 수가 궁금해졌다. 어떤 룩은 공격받지 않을 수도 있다.

N*M크기의 체스판이 주어졌을 때, K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 세로 크기 N, 둘째 줄에 가로 크기 M, 셋째 줄에 놓으려고 하는 룩의 수 K가 주어진다. N과 M과 K는 100보다 작거나 같은 자연수이다.

출력

N * M 크기의 체스판에 K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 1,000,001로 나눈 나머지를 출력한다.

D[N][M][K]

경우의수

0. 룩을 놓지 않음 :

1. 룩이 공격받지 않음 : D[N-1][M-1][K-1]XM

2. 같은 행에 룩이 있고 열에는 없음 : D[N-1][M-2][K-2]XM(M-1)

3. 같은 열에 룩이 있고 행에는 없음 : N-1 M-1 K-2 X M X N-1

네가지를 모두 더해주는 코드를 구현하면 된다.