하

2748 피보나치 수 2

피보나치 수.
0과 1로 시작, 2번째 부터는 바로 앞 두 피보나치 수의 합.
n이 주어졌을 때, n번째 피보나치 수를 구하자.
n<=90 자연수.

주어진 수식이
f[n] = f[n-1] + f[n-2] 라서

그냥 n크기 만큼의 f라는 배열을 미리 만들고
f[0] = 0, f[1] = 1, 을 채운뒤

for i in range(2,n+1):
로 f[i] 부터 순차적으로 채워서

f[n]을 출력하면 된다!

1904 01타일

00타일과 1타일이 있다.
크기가 n인 2진 수열의 갯수를 몇개 만들 수 있는지
가짓 수를 세보자.
단, 타일들은 무한히 많다.
(자연수 n은 1,000,000 이하.)

n이 1일때는 1이고,
n이 2일때는 11, 00이라 2고,

그리고 n이 3부터...

111, 001, 100 등이 있는데...
흠...
n이 4면

1111, 0000, 0011, 1001, 1100..

n이 5면

11111, 00001, 00111, 10011, 11001,
00100, 10000, 11100, ...

....

1, 2, 3, 5, 8...

아 규칙 찾았었는데 까먹었네
자리가 하나 늘면
이전의 경우의 수(그대로 거기에 1을 붙이면 되니까 그대로 계승)
......
....
2로 나누어졌을때 나누어지면 +1...(00으로 바꿀 수 있어서.)
+2 인가?

그러면...

5는 안나누어지는데...잉
1111+1
0000+1
0011+1
1001+1
1100+1

없는건
11100
10000...
00100...

아
이거 어째선지 규칙이
그전거 + 전거 = 현재 였지

아무래도 그전거 + 00, 전거 + 1 해서 현재 인?걸지도.
음~ 맞는듯
그렇다면 쉽다.

f[n] = f[n-2]+f[n-1]
처럼 똑같은데 이제 시작 값이 다른 거니까.

11047 동전0

동전은 n종류고, 적절히 사용해 가치 합 k를 만들때,
필요한 동전 개수의 최솟값을 구하라.
n은 10 이하, k는 100,000,000이하.
동전의 가치가 오름차순으로 주어지며, 뒤의 동전은 앞 동전의 배수다.

그리디!
이때는 쉬웠는데....

오름차순의 가장 큰 동전부터
k에 순차적으로 넣어보면서,

만약 k보다 동전 크기가 크면 넘어가고,
k보다 동전 크기가 작으면
k에 동전 값을 빼고

여전히 그러고도 작으면 빼는데
이걸 for로 하면 한번만 빼고 넘어가게 되니까
아예 나눠서 나머지를 다음에 반환시킨다.
그리고 그 몫을 경우의 수에 포함 시킴!

끝!

1541 잃어버린 괄호

식이 주어진다. 식은 0~9, +, -로만 이루어져있다.
처음과 마지막은 숫자다.
5자리보다 많이 연속되는 순자는 없다.
식의 길이는 50보다 작거나 같다.
여기서 +와 -가 들어가는 식에서 괄호를 적절히 쳐서
이 식의 값을 최소로 만들어보자.

처음에
괄호를 한번만 치는줄 알고
+++가 최대한 많이 연속되는 -에서
괄호를 쳐야겠군!

했는데, 괄호의 수는 제한이 없더라.
그래서 그냥 -가 나올때마다 다음 -전까지
계속 괄호를 치면 됨....

여기에서도 실제 알고리즘보단 구현의 문제인데
spilt으로 -기준으로 자르고,
또 자른거에서 + 기준으로 잘라가지고
그...
50+55같이 잘렸을 테니까,
거기서의 합을 총 합에 ...마이너스로 더하면 되거든(앞에 마이너스있으니까)
그래서 그 50+55도 +기준으로 잘라서
그냥 리스트의 sum으로 해버린다음
전체 합에서 -로 sum값 빼준다..
(그치만 처음 요소는 앞에 -가 없는거니까 플러스로...)
(애초에 이 연산을 인덱스 0이 아니라 1부터 시작하면 됨..)

중

9084 동전

동전의 종류가 주어질때, 주어진 금액을 만드는 모든 방법을 세보자.
동전의 가지 수 N, 동전의 금액이 오름차순으로 제시, 동전으로 만들어야할 금액이 M일때 방법의 수는 2^31 -1 보다 작고, 같은 동전이 여러번 주어지는 경우는 없다.

동전으로 만드는 모든 방법의 수를 제시하는 건데...

아마 m을 0부터 k까지의 ... 부분문제로 나누어서
가지고 있는 동전으로... 하아

아마 가장 작은 동전으로 만든 경우의 수 + 그 다음의 동전으로 만든 경우의 수 + .... 가 총 경우의 수와 일치한다고 추론했던 것 같음.

(가장 큰 수부터 경우의 수를 만들어보고

(10일때 5를 빼고 5을 만드는 경우,
10일때 3을 빼고 7을 만드는 경우,
10일때 2를 빼고 8을 만드는 경우...)

남은 금액으로 경우의 수를 나열해보니까
경우의 수가 중복되는 걸 발견했음)

(남은 5는 2+3, 5고
남은 7은 2+5, 3+2+2고,
남은 8은 3+5, 3+3+2, 2+2+2+2인데,)

(사실 크게 보면
5 : 2+3+5, 5+5,
7 : 2+3+5, 3+3+2+2,
8 : 2+3+5, 3+3+2+2, 2+2+2+2+2

인걸 보면,
2+3+5는 전부 중복임.
사실, 작은 동전을 넣었을때는,
그보다 큰 동전이 포함하는 경우의 수가 전부 중복임!

그럼, 작은 동전의 경우의 수+ 그 다음 동전의 경우의 수 = 총 경우의 수!
인 거니까!

다음으로 넘어갔을때 새로운 경우의 수가
나오는 경우는....

남은 수를 현재의 동전으로 나누었을때 완전히 나누어지는 경우! 니까.

0부터 ...k에서부터 항상 성립하며 최종적으로 m만큼의 금액을
n개의 동전 중 i번째 동전까지 포함하여 나오는 경우의 수는
(그리고 i번째 동전의 금액이 w일때)

dp[k][i] = max(dp[k][i-1], dp[k-w][i-1] + 1)

...근데 어차피 w만큼만 빼면 무조건 나누어질테니까
....
맞나?

쩝쩝

그냥 처음에 맨처음을
동전 배수만큼 되는 곳의 dp테이블을 1로 채우고
그 이후의 값은...

식에서는 그냥 일단 그대로 가져온 다음
(이전 동전의 경우의 수를)
굳이 완전히 나누어지지 않아도 크거나 같으면
이전의 그 정도 값에서 나온 최적의 해를 더하네.

나랑 약간 달랐네...

이전의 경우의수 + 남은 값으로 현재 동전이 시도했던 경우의 수
로구만

오케이!

9251 LCS

최장 공통 부분 수열 문제.
두 수열이 주어졌을때, 모든 부분 수열이 되는 수열 중 가장 긴 것을 찾자.
가장 긴 LCS의 길이를 출력하라.

이론적으로는
이전에 가장 긴,
그러니까 맨 끝에 글자를 떼고 만든 부분 수열 중
가장 큰 길이를 가져오고,

만약 그 문자열 두개의 끝 글자가 일치한다면,
문자열 하나가 아예 붙지 않은 수열에서 +1(일치하는 부분 수열의 길이)
를 해서 반환한다.

그래서
한 문자열의 길이가 n,
다른 문자열의 길이가 m일때,

열에 놓는 문자열 길이 m에서 0부터 m까지 i번째 문자와,
행에 놓는 문자열 길의 n만큼에서 0부터 n까지 j번째 문자를,

만약 i번째 문자와 j번째 문자가 일치한다면,
i-1번째 문자와 j-1번째 문자가 일치하는 길이에서 +1을 하고,

일치하지 않는다면,
i번째 문자만 붙인 경우와, j번째 문자만 붙인 경우,
둘 중 큰 길이를 가져온다.

(끝을 둘다 붙인 경우가 지금 구하는 수고,

(ABC, BCR의 경우라고할때.)

어차피 일치하지 않는다면 그렇다고 수가 증가하지않으니까,

(AB, BC에서 C와 R을 각각 붙인다고 증가하지 않음)

이전의 부분집함을 모두 검토하는 것 같음.)

(ABC, BC와 AB, BCR의 경우 두 가지로 나뉘니까.)

dp[i][j] = max(dp[i-1][j], dp[i][j-1])
과
dp[i][j] = dp[i-1][j-1]

두 가지로 나눠서 점화식을 쓰면 된다.

12865 아주 평범한 배낭

여행에 필요하다고 생각하는 N개의 물건.
각 물건은 무게 W와 가치 V를 가진다.
최대 K만큼의 무게를 배낭에 넣어 들고 다닐 수 있다고 할때,
가질 수 있는 최대의 V를 출력하자.

이 문제를 그리디로 하면
(가장 큰 가치 먼저 담으면)
안 된다...

그래서,
물건의 가짓 수가 정해져있으니까,

1부터 n까지 i번째 물건을 담았을 때의
0부터 k무게까지 j 무게에서 담을 수 있는 최적해를
(다시 말하자면, 최대 j 무게에서 나올 수 있는 최대 가치를)
항상 최적해를 구해서,
그게 결국 최종 최적해가 나오도록 계산한다.

그렇게...

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

하는데...

아마 0 무게는 아무것도 담을 수 없으니 0이고,
물건에도 0번째, 아무 가치도 안 가지는 열을 넣을텐데,
그건 버퍼 오버...를 막기 위함이다.
(엉뚱한 인덱스가 생기는 경우.)
(범위 지정으로도 해결 가능.)

11049 행렬 곱셈 순서

크기 NxM인 행렬 A, MxK인 행렬 B를 곱할때
필요한 곱셈 연산의 수는 NxMxK라고 할때,
행렬 N개를 곱하는데 필요한 곱셈 연산의 수는
곱하는 순서에 따라 달라진다.
행렬 N개의 크기가 주어졌을 때, 필요한 곱셈 연산 횟수의 최솟값을 구하시오.

아무도 이걸 그 뭐냐
스스로 생각해내지 못 할거라고 인정함
나도 인정함

흠....
......

.......
.......

대강 기억 나는건
체인 길이,......

그냥 딱 생각했을 때 생각나는건
왼쪽 애랑 곱할지 오른쪽 애랑 곱할지...
니까.

아아
근데 그 행렬의 순서는 정해져있는거라
처음 했을 때는 앞엣걸 뗀 걸 부분 문제로 해야할지
뒤엣걸 뗀 걸 부분 문제로 해야할지 고민했는데

실제 문제에서는
뒤엣걸 뗀걸..(그러니까, ABCDE면 ABCD가 부분해가 되는거임)
하고,

아마 그렇게 해서
전체 수열의 길이가 n일때
i번째까지 부분해를 구했으면 남은 체인의 길이가 l-i겠지?

그래서...
체인의 길이가 l이라고 할때 2부터 n+1까지 확인하는데 그걸 i라고 하면
(왜냐하면, 행렬이 한개일때는 곱셈 연산 순서가 없으니까.)
곱셈 연산 횟수는 ....
i번째 행렬을 곱하는 거니까
dp[i][j] = dp[i-1][j] + cost[i][0] x cost[k][1] x cost[j][1]

아니 j가 n-l+1이었던 건 기억나는데
나는 아직도 j가 뭔지 잘......모르겠어.
뭔가의 범위 값이라는......건 아는데...

흠......
...체인 길이 l에
현재 곱하는 행렬 i에
(범위가 n-l-1, 왜냐하면 체인 길이가 늘어날 수록 뒷 행렬을 지정해야하니까.)
j = i+l+1이라 진짜 그냥 체인의 종료 인덱스고,

그 체인의 i부터 j까지 k번째를 뽑아서
dp[i][j]를 채우는데,
k전까지의 dp+ k이후부터 j까지의 dp + 그 두 행렬을 곱하는데 드는 비용..
으로 채운다.

그렇게 dp[0][-1]이면 최종 인덱스라 결과 비용이 나옴.

아아,
나는 체인 길이라는 게 헷갈렸는데

그냥 지금 보는 행렬의 길이....
에서 k번째 기준으로 전부 나눠서 값을 구함....
약간 이차원 배열의 대각선 길이가 체인이었구나 싶고.....

가장 짧은 체인부터 시작할테니
나오는 dp...i의 갯수가 많......나?
많지...

흠...
행렬 수열의 모든 부분을 순회하고,
순회할때마다 체인의 길이를 점점 늘려서 전부 체크하는군.

OK!

11053 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하라.
수열 A의 크기를 N이라고 하자.

아 이게 왜 DP지

하 다 까먹었다

근데 아마 뒤엣부터 이어서 붙이는데
(그러니까 부분문제로 나눌때
10, 20, 10, 30이면
10, 20, 10 일때의 최적해를 사용하는데

새로 붙이는 값이, 앞에 있는 값보다 큰 지 작은 지에 따라
(앞에있는 값, 각자에 전부.)
부분 수열의 길이를 +1함.
그러니까 대략 20을 시작 지점으로 했을때의
긴 부분 수열의 값이 테이블에 남는 거임.

그래서....

리스트에서 i번째 수를 볼건데(0부터 n+1까지)
그 전까지의 리스트(i이전)에서 수를 하나씩 j로 뽑아서(0부터 i까지)
i가 j보다 크면
dp[j] += 1 하고
i가 j보다 작으면 넘어가고....

그래서 list에서 max값 찾아서 반환하면 됨!

다 까먹었다고 한것치곤 제법 잘 풀었어

1931 회의실 배정

한 개의 회의실에서 N개의 회의실 사용표를 만든다고 할때,
각 회의 I에 시작 시간과 끝나는 시간이 주어진다.
회의가 겹치지 않게 사용할 수 있는 회의의 최대 개수를 구하자.
단, 시작시간과 끝나는 시간이 중복될수는 있다.
(동일하다면 시작하자마자 끝난다고 생각하면 됨.)

하 울고싶다
울지마세요

...
이거 그리디인데
나는....
일단 회의 시간 길이가 제일 짧은 걸 넣어야한다는 건 알았는데
그럼 전부 길이를 재서?
제일 짧은 길이 부터 순서대로 뽑는데?
시작시간과 끝나는 시간이?
근데 중복 자체는 되잖아?(한번이면?)
하고 구현하느라 끙끙 댔었는데....

이게 그리디로 한 게
그냥..........
......

제일 앞에 있는 회의부터 뽑아서?
그 시작 시간이 끝나는 시간보다 크면
(그러니까 끝난 이후에 시작하면)
끝나는 시간을 그 시작 회의의 끝나는 회의로 갱신하고
회의 수를 카운트 올리거든?

아마
그 전에 끝나는 시간이 빠른 순부터 정렬을 시켜놓기때문에
끝나는 시간이 제일 빠른 애부터 뽑혀서 하는거라
그런거같아...
...

내가 한 거랑 전혀 달랐네? 비슷하다고 생각했는데.
뭐 끝나는 시간이 빠른 애가 상대적으로 길이가 짧긴 하겠는데.

정렬하는걸 그냥 대충 넘겼어서
아니 그냥 갱신하기만 하면 된다고?? 홀리몰리 하고 넘어갔었는데
그래서 이렇게 갱신하는게 되는거군...

아무튼 중 난이도 그리디는
정렬을 해서?
그냥 순차적으로 갱신하는게 트렌디한 듯.
(신입사원도 그런 문제라.)

1946 신입 사원

시험은 서류와 면접으로 이루어진다.
다른 모든 지원자와 비교했을때 서류, 면접 중 적어도 하나가
다른 지원자보다 떨어지지 않는 자만 선발한다고 할때,
신입 사원의 최대 인원수를 구하라.
1위부터 N위까지 동석차 없이 결정된다.

이것도 정렬하면 되나봐!!
했었는데 흠 음 흠
단순히 그게 아니라 약간 달랐는데...

힌트를 들어서
한쪽 성적 순을 인덱스로 넣어서 리스트를 만들었었는데....

사실 그것과 상관없이
(그렇게 하면 시간? 메모리는 덜 들어도.)

하...
개같이 고생한 것만 생각나고
풀이가 생각 안 나네
헛살았네

처음에 했던 게 그럼
이미 서류 높은 순위 뽑았으니까
그 서류 높은 순위 애의 면접 순위보다는 높으면 되는거잖아?
하다가 경우의 수가 세세하게 빠져서
애먹다가...

아마 그냥
하

면접 순위를 가장 높은애로 계속 갱신시켜서
(그러니까,
서류 순위로 뽑되,
면접 순위 가장 높은 성적을 갱신시켜서,)
(한바퀴 다 돌렸던거같다.)

나는
왜 애먹었지? 원리 똑같지않아?

음 아아
나는 서류 순으로 진행하되
면접에서 가장 낮은 애보다 높으면 포함시키다보니
꼬인거였네..
하...바보.

상

1700 멀티탭 스케줄링

멀티탭 구멍 개수가 N, 전기 용품 총 사용 횟수가 K일때,
한정된 멀티탭 구멍 개수에서 전기 용품 사용 순서가 주어질때
최소로 플러그를 뽑을 때, 플러그를 뽑는 횟수를 출력하라.

....
이거
그......

맨처음에는 빈도가 제일 높은 전기용품을
나중에 뽑아야겠지? 이랬는데

그러면 매번 순서가 (앞에는 쓰면 순서가 사라질 거 아냐?)
얼마나 남았는지 리스트를 갱신해야하거든....

점점 수식이 길어지면서
이건 아닌거같다는 생각이 들고...

이이거
가장 인덱스가 뒤에 있는 경우에
(그러니까 사용 순서가 가장 나중인 것을)

그때마다 찾아서
그 인덱스에 해당하는 멀티탭 꼽혀있는 걸 뽑으면 됨.

단순하게 말하자면,
사용 순서를 계속 popleft하면서 확인하는데,

멀티탭에 이미 있으면 패스,
멀티탭에 없는데,
멀티탭에 있는 것들의 인덱스를 남은 사용순서 리스트에서 확인해서,
그 인덱스 목록을 넣어놓은 인덱스 리스트를 만들어서,
가장 큰 인덱스를 가진 걸 찾아서,
그 인덱스 값을 가진 멀티탭을 지금 전기용품으로 체인지.
카운트 +1.

인덱스 리스트를
매번 지워야하는 것과,
0으로 비워져있는데 비어져있는걸 감지 못하는것까지 고치고 끝!

2253 점프

N개의 돌이 놓여있고, 현재 1번 돌 위에 있고,
돌을 점프하여 N번째 돌로 이동하는데,
1. 이동은 앞으로만 가능(돌 번호가 증가하는 순서)
2. 제일 처음 점프는 한칸. 이후에는 이전에 x칸 점프했으면 x-1칸, x칸, x+1칸 점프할 수 있다. 최소 한칸이다.
3. 몇개의 돌은 너무 작아 못 올라간다.
그래서 1번부터 N번까지 점프시, 필요한 최소 점프 횟수를 구하라.

하....
..........
..........

이게...
점프의 규칙을....
...
속도....

최대한 큰 속도로 이동하되,
n번째에는 도달하게 또 감속해야하거든...

그래서 이전 가속도를 그냥 갱신하는 걸로는
남은 부분을 임의의 기준을 정할 수 밖에 없어서 불가한데.

공식이 있길래?
아ㅠ 공식이 있구나..했는데
다른 방법도? 된다고 팀원분이 말씀해주셔서 찾아볼 예정.

2098 외판원 순회

1번부터 N번까지의 도시. 그 사이의 길이 있지만, 없을 수도 있다.
한 도시에서 출발해, N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오고자 할 때.
한 번 갔던 도시는 다시 갈 수 없다면....
가장 적은 비용을 들이는 여행 경로를 세우려고 할때,
최소 여행 비용을 구하라.

쩝...
비트 마스킹을 쓴다고 힌트들어서
엥? 집합처럼 하나? 했는데
그냥 방문 처리를 최적화를 위해 비트 마스킹을 할 뿐이었음.
(물론 그것도 복잡하지만.)

아직 전부 이해 못했음.