.png는 무시하삼(궁금하다? 카톡하면 보내드림)
A
f(남은 칸수)
B
f(남은 칸수)
C
f(OO 남은 칸수, XX 남은 칸수), f(0, 0)일때만 return 1
그 이외에 f(x, y)에서 $x\leq 0 || y \leq 0$이면 return 0
D
f(남은 칸수, 이전에 오른 칸)
E
f(올라간 칸수), f(x)에서 x=m이면 return 0
F
f(올라간 칸수, 3의 배수 밟은 횟수)
!! 0은 3의 배수가 아니므로 초기 상태 f(0, -1)로 하면 깔쌈함
G
f(남은 칸수), f(n)+f(n-2)
H
f(남은 칸수, 1칸 오른 횟수, 2칸 오른 횟수, 3칸 오른 횟수)
I
f(OO 올라간 칸수, XX 올라간 칸수), f(n, n)만 예외처리
J
f(OO 올라간 칸수, XX 올라간 칸수, OO 3의배수 밟은 횟수, XX 3의배수 밟은 횟수), 초기 f(0, 0, -1, -1)로 하면 깔쌈함
K
f(남은 칸수, 이전에 오른 칸수) ->f(남은 칸수-i, max(i, 이전에 오른 칸수))
L
f(남은 칸수, 이전에 오른 칸수), f(n)+f(n-2)
M
f(남은 칸수, 이전에 오른 칸수, 2번 전에 오른 칸수)
N
작년 기출에 나옴
$n \choose k$
O
f(현재 관리하는 번호, 누적 앉은 사람 수, 이전 사람 존재 여부)
if 이전 칸 빈칸 : 현재 칸 앉던가 비우던가
if 이전 칸 사람 : 현재 칸 비우던가 현재 칸 앉고 다음 칸 비우던가
![[Pasted image 20240416201042.png]]
P(재귀)
f(남은 사람 수, 초기 섬에 있는 사람 배열) : 초기 섬 -> 다른 섬(2명)
모든 $N \choose 2$가지 경우에 대해 다 재귀적으로 진행하면 됨
g(남은 사람 수, 초기 섬에 있는 사람 배열) : 다른 섬 -> 초기 섬(1명)
가장 값이 작은 사람을 보내는 것이 자명함
사실 재귀함수 하나로 짜도 ㄱㅊ은듯
Q
f(a=1행 남은 칸, b=2행 남은 칸)
if a=b, return f(a-1, b-1) + f(a-1, b) + f(a-2, b) + f(a-3, b) (WLOG)
else 둘 중 많은 놈에 대해 -1/-2/-3
R
f(현재 관리하는 번호, 누적 무게, 누적 가격)
현재 관리하는 물건을 넣던가, 안 넣던가
S
f(현재 처리하는 쿼리, 열린칸 1, 열린칸 2) (1 < 2)
두 열린칸 사이에 쿼리가 있다면 2가지 모두 고려,
그 이외의 경우 가까운 것만 옮기는 것이 최적임이 자명
T
if 문제가 원형 X, 선형이였으면 쉬움
( f(n, k) = f(n+1, k) + f(n+1, k+1) )
1번 칸 칠해져있으면 2번/n번 칸 X, 나머지 : f(n-3, 1)
1번 칸 칠해져있지 않으면 나머지 : f(n-1, 0)
-> 두개 더하면 됨
U
f(현재 처리하는 소방차 번호, 남은 호스 리스트(set..?))
현재 소방차에서 왼쪽/오른쪽으로 가장 가까운 호스 2개만 고려하면 됨
이유: 소방차 - 호스를 선분으로 연결한다 한다면, 모든 선분은 완전한 포함 관계이거나 독립적인 관계이다.
( 1, 2, 3, 4에서 1-3, 2-4 길이 = 2-3, 1-4 길이, 포함 관계로 치환 가능 )
set 쓰면 lower_bound 찾기 쉽지만...
쓰면 안되니깐 vector로 표현하면 될듯
$\uparrow$ 쓰레기 풀이
펌프 P개중 F개 고르는 $P \choose F$가지에 대해 순서대로 연결해주고 더한 것의 minimum. ( $\because$ 1-a, 2-b 연결 시 1-b, 2-a로 바꿔도 길이 일정, 치환 가능)
V
f(현재 쿼리 번호, 소방차1 위치, 소방차2 위치)
현재 사건을 소방차1이 처리하거나, 소방차2가 처리하거나
W
f(s, e) s->끝으로 가고, 끝->e로 되돌아오는 경우의 수
둘 중 작은 값을 크게 만드는 방향으로... ( $\because$ 중복 방지)
갈 수 있는 모든 새로운 위치 p에 대해 f(p, e) or f(s, p)의 합
(이걸로 플레 ㄱㄴ)
X
f(n, k) = f(n-1, k) + f(n-1, k-1), 삼각형 상에서 끝값은 return 1
Y
f(그리는 level)
f(n-1) -> * n개 -> f(n-1), 누적 별 개수 return
Z
f(n=옮기는 원판 번호, 현재 위치, 목표 위치)
f(n-1, 현재 위치, 남은 위치)
move disk n 현재 위치->목표 위치
f(n-1, 남은 위치, 목표 위치)
AA
f(n=옮기는 원판 번호, 현재 위치, 목표 위치)
if 현재 위치와 목표 위치가 인접
f(n-1, 현재 위치, 남은 위치)
n : 현재 위치->목표 위치
f(n-1, 남은 위치, 목표 위치)
else
f(n-1, 현재 위치, 목표 위치)
n : 현재 위치->남은 위치
f(n-1, 목표 위치, 현재 위치)
n : 남은 위치->목표 위치
f(n-1, 현재 위치, 목표 위치)
AB
A에서 k개 B로, n-1-k개 C로 이동
n번째 D로 이동, C->D, B->D
를 가능한 k에 대해 모두 진행하여 minimum return
근데 이 경우 중에 하나가 최소임을 증명할 수 없어 나오기 힘들 듯
AC
가장 긴 하노이 = 인접 하노이
($\because$ 가능한 최댓값 : $3^n-1$, 인접 하노이의 횟수랑 같음)
AD
f(n) : 초기 n개 덩어리 2개를 2n개로 합치는 횟수
g(n) : 삼각 하노이 횟수
h(n) : 일반 하노이 횟수
f(n) = g(n-1) + 1 + h(n-1)*2
g(n) = f(n-1) + 1 + h(n-1)*2 + 1 + h(n-1)*2
근데 이 경우 중에 하나가 최소임을 증명할 수 없어 나오기 힘들 듯
AE
중복
AF
중복
AG
초기 n개 꽃혀있는 기둥 A, B, 남은 2개 기둥 C, D
-> A, B에서 k개씩 D로, n-1-k개 덩어리 B로 합치기,
n번째 C로 옮기고, (n-1-k)*2개 A로 옮기고, n번째 C로 옮기고,
(n-1-k)*2개 C로 옮기고, k*2개 C로 옮기기(...)
h(n) : 기본 하노이
h4(n) : 기둥 4개 하노이
f(n), g(n) : 삼각 하노이에서 그거
a(n) : 사각 하노이
a(n) = a(k) + f(n-1-k) + 1 + h(n-1-k)*2 + 1 + h(n-1-k)*2 + h4(k)
를 가능한 k에 대하여 minimum
근데 이 경우 중에 하나가 최소임을 증명할 수 없어 나오기 힘들 듯
AH
중복
AI
(면 +1, )면 -1, 중간에 음수거나 최종 0이 아니면 NO
아니면 AJ랑 똑같이 풀기(stack으로 하고 싶다면)
AJ
stack에 순차적으로 집어넣으면 top이랑 현재 괄호가 세트면 지우기, 아니라면 X, 프로그램 종료
최종 stack에 남아있으면 X, empty면 O
AK
아직 stack에 안넣은 수면, 해당 수까지 모두 stack에 +, 이후 1개 -
넣었던 수면 top일때 -, 아니라면 NO
AL
AK와 동일, 수열, 1~n만 서로 바꾸면 됨
AM
f(s, e) : s~e 구간에서의 괄호 문자열 값
s가 문자열 벗어나면 return 0
s>e면 return 1
a[s]가 닫히는 괄호면 올바른 문자열 X
a[s]가 닫히는 시점 p, 안 닫히면 X
f(s, e) = f(s+1, p-1) * (2 or 3) + f(p+1, e)
$\uparrow$ 너무 ed hoc스러운 풀이긴 함(+stack 안씀)
stack에 여는 괄호면 그대로 넣는다.
닫는 괄호면 괄호가 나올 때까지 stack에서 pop, 숫자 모두 더해놓기
이후 top이 맞는 괄호가 아니라면 return 0
맞는 괄호라면 지우고 역대 더해놓은 숫자에 괄호 고윳값 곱해서 stack에 넣기 (여는 괄호가 처음부터 top인 경우는 예외처리)
즉, 괄호 문자열 확인 + stack에 수 집어넣어서 직관적으로 관리
AN/AO/AP
AO/AP 먼저 보자.
피연산자는 바로 출력, 연산자는 stack으로 관리
+/- : ( 나오기 전까지 pop, 이후 push
*// : (/+/- 나오기 전까지 pop, 이후 push
( : push
) : ( 나오기 전까지 pop, (까지 pop
문자열 모두 확인한 후 stack에서 모두 pop
AN의 경우
피연산자도 stack에 넣어두기, 숫자 연속하게 나오면
피연산자 stack의 top update
연산자 출력 대신 피연산자 top 2개 연산
정답 : 피연산자 stack의 top
AQ
작년 기출에 나옴
순차적으로 stack에 넣기, 만약 stack top이랑 넣을 것이 같다면
pop 후 넣을 것 update, 다시 top이랑 비교
stack은 뒤에서부터만 뺄 수 있으므로 빼낸 순서랑 반대로 출력해야 함
AR
순차적으로 stack에 넣기, stack의 top이 현재 소 키 이하라면 짜피 현재 이후의 모든 소는 볼 수 없으므로 pop, 다시 top이랑 비교
모두 pop한 이후, 현재 소를 볼 수 있는 소의 수는 stack의 size이다.
AS
윗방향만 짜자. (각 열별로 AQ 비슷하게 진행)
다른 방향은 적절히 대칭시킨 후, 윗방향 진행, 원상복구하면 된다.
![[Pasted image 20240416204955.png]]
AT
(이게 왜 queue...)
queue로 (현재 높이, 연결 가능 노드 개수, 남은 차수가 2/1/0개인 노드 개수)
차수가 큰 노드부터 순차적으로 처리하면 된다. 정답은 모든 queue의 원소들의 높이 중 maximum.
![[Pasted image 20240416205154.png]]
억지 queue + $O(1)$ 풀이가 정해였던 문제(in 코포)여서 안나올듯
AU
작년 기출에 나옴
queue로 (시작 번호, 남은 번호 배열)
시작 번호로부터 k번째 원소 확인, 다음 queue에
(k번째 원소, k번째 원소 제외한 배열) 넣으면 됨.
(작년 코드도 참고하삼 그게 정풀이니깐)
![[Pasted image 20240416205510.png]]
AV
n개의 동물을 q[자기 번호]에 push하면 됨, 앞에서부터 출력
AW
작년 기출에 나옴(근데 pq 씀)
각 창구 별 처리가 끝나는 시간 배열 t(초기 : 전부 0)
가장 끝나는 시간이 빠른 창구 중 가장 번호가 빠른 창구 선택,
순차적으로 고객을 해당 창구 queue에 넣고 t update
AX
queue로 (x=현재 값, t=순서)
0->1, 2 / 1->3, 4 / ...
queue에 (nx, 2t+1), (mx, 2t+2) push
AY
queue로 (x=현재 위치, t=시간), 체크배열
입력값들은 (x, 1)로 등록, 체크
queue에 (x $\pm$ 1, t+1) push
AZ
queue로 (x, y=현재 위치, t=시간), 체크배열
입력값들은 (x, y, 1)로 등록, 체크
queue에 (x $\pm$ 1, y $\pm$ 1, t+1) push
BA
생략
BB
queue로 (x, y=현재 위치, t=시간), 체크배열
입력값들은 (x, y, 0)로 등록, 체크
queue에 ((x, y에서 다음 이동), t+1) push
모두 체크되었는데도 도달 못한점은 -1
BC
queue로 (x=현재 번호, t=시간), 체크배열
못가는 곳은 체크, 입력값은 (x, 0)로 등록, 체크
queue에 ((x에서 이동 가능한 값 mod 10000), t+1) push
BD
queue로 (x, y=현재 위치, t=시간), 체크배열 (500*500)
현재 좌표를 (x, y), 시작 좌표를 (sx, sy)라 하면
체크 배열 상에서 [x-sx+200][y-sy+200]로 대응 시 최대 100칸
움직여도 200칸만 좌표가 바뀔 수 있으므로 커버 가능
정확히 k번 = k와 기우성이 같은 모든 칸
이후 기존 나이트의 이동과 비슷하게 코드 짜면 됨. long long!!
BE
(냄새)
실험 장비 사용 순서 queue, 대기열 queue 미리 만들어놓자.
매 시간, 매 실험 장비에 대해 대기열이 존재한다면 대기열에서 1명 꺼내서 사용 순서 queue에 집어넣는다. 이후 꺼낸 사람을 임시 배열에 넣어둔다. (없다면 continue)
이후 임시 배열의 모든 사람들의 다음 사람들에 대해 사용할 실험 장비 별로 정렬 후, 대기열 queue 뒤에 그대로 집어넣는다.
(넣은 후 정렬하면, 이미 줄을 서 있던 사람들이 존재하기 때문에 새로 줄을 서게 된 사람끼리만 정렬해야 한다.)
$\uparrow$ 나도 왜 이랬는지 모르겠음
정렬 기준이 이전 실험 장치 번호 하나임을 알 수 있다.(초기 상태 제외)
ans : 정답 queue, wait : 대기 줄 queue라 하자.
input도 queue로 받은 후, 각 queue의 top들을 알맞은 wait에 넣어두자.
충분히 많은 횟수동안(10000번) 연구 장비 번호 순서대로 각 대기 줄이 비어있지 않다면 ans에 집어넣고, 해당 사람의 input queue 상 다음 사람을 임시 queue에 넣어둔다. (한 줄에서 모든 연구 장비 순차적으로 쓰는 것 방지)
모든 연구 장비 확인 후, 각 임시 queue의 모든 원소를 대기열에 넣어주면 된다.
BF
queue로 (x, y=부서질 모래성 후보, t=시간), 체크배열 (int형)
queue를 많이 만들자. q[t]에는 t번째 시간에 부서질 모래성 후보를 넣는다.
(q[1]에는 모든 모래성을 넣으면 된다.)
q[t]에 대해, 모래성이 부서진다면 임시 배열에 넣어두고, 인접한 모든 모래성들에 대해 아직 체크되지 않았다면 q[t+1]에 넣는다.
(사실 queue 대신에 vector 쓰면 sort, erase하면 되니깐 편하다!)
q[t] 순회 만료 후, 임시 배열의 모든 모래성을 물로 바꿔준다.
(만약 그때그때 바꾸면 남은 모래성들 중 안 부서져야할 게 부서질 수 있다.)
체크는 그때그때 해야하므로 bool로 하면 안되고,
ch[x][y] = t ? 여부로 확인하면 편하다.
BG
스킬 : 트리를 배열에 저장하는 법
a[n]의 왼쪽 노드는 a[n*2], 오른쪽은 a[n*2+1]에 저장하면 된다.
i번째 원소를 a[i]에 저장하면 스킬의 방법대로 원소 접근 시 트리 접근 순서와 동일해진다. 전위순회 : DLR
BH
중복, 중위순회 : LDR
BI
중복, 후위순회 : LRD
BJ
따로따로 받으면 여러가지 이슈가 많이 발생하는 것 같으니...
그냥 getline(cin, s)으로 받고 space 기준으로 vector<string>으로 끊자.
위에서 말한 스킬대로 배열에 순서대로 넣어두자.
string은 string 간 덧셈 연산이 구현되어 있기 때문에
1번째 줄의 경우 중위순회에 괄호랑 + 잘 추가하면 된다.
![[Pasted image 20240416220036.png]]
2번째 줄의 경우 전위순회 순서대로 출력하면 된다.
3번째 줄의 경우 후위표기식 연산이랑 동일하게 진행하면 된다.
만약 숫자가 한자릿수가 아니라서 애를 먹었다면 stoi()라는 함수를 쓰자.
이 문제 테케에 3자릿수 입력 있음(...)
BK
f(배열에 저장할 인덱스, 중위순회 a 시작/끝, 전위순회 b 시작/끝)
b의 시작은 현재 노드이다. 저장하도록 하자.
a에서 b의 시작 값이 나오는 시점을 p라 하면,
a 시작~p-1 : L, p : D, p+1 ~ a 끝 : R이다.
b에서도 길이가 같도록 잘 끊어줘서 재귀적으로 하고, return 조건만 잘 잡아주면 된다. 이후 후위순회로 배열을 출력하면 된다. (BI)
map에 트리 저장할 필요 없이, 재귀를 string으로 한 후 return 조건 시 ""를 return 하여 string 간 합 연산을 진행해주면 쉽게 구현 가능하다.![[Pasted image 20240422222416.png]]
BL
스킬 2가지
\1. 후위순회는 LRD, 후위순회의 역순은 DRL이다.
\2. 답은 2^(차수가 1인 노드 개수)이다.
(만약 한 노드의 차수가 1이라면, 왼쪽 연결/오른쪽 연결 2가지 존재)
f(배열에 저장할 인덱스, 전위순회 a 시작/끝, 후위순회 b 시작/끝)
a/b의 시작은 현재 노드이다. 저장하도록 하자.
a에서 b의 2번째 값이 나오는 시점을 p라 하면,
a 2번째p-1 : L, pa 끝 : R이다.
b에서도 길이가 같도록 잘 끊어줘서 재귀적으로 하고, return 조건만 잘 잡아주면 된다. 깊이가 깊게 들어가므로 인덱스 저장은 map으로 하는 것이 좋다.
이후 모든 노드에 대해 차수가 1인 노드를 세주면 된다.
얘도 비슷하게 인덱스 저장 할 필요 없이 재귀에서 그때그때 자식노드 존재 여부에 따라 전역변수 ans에 2를 곱해주면 된다. (bool 사용 추천)
BM
답을 f(n)이라 하면, n의 자식 노드 좌/우에 연결할 수 있는 노드 개수는
0/n-1, 1/n-2, ..., n-1/0이므로 다 곱해서 더하면 된다.
(이는 카탈란 점화식 꼴과 동일하다.)
BN
f(현재 노드 인덱스, s=시작 인덱스 값, e=끝 인덱스 값)이라 하면,
현재 노드의 두 자식의 크기는 정확히 같으므로
mid=(s+e)/2에 대해 크기 비교하여 재귀적으로 넘길 지, 현재 원소를 출력할지를 결정하면 된다. 초기값은 $f(1, 1, 2^{h+1}-1)$이다.
BO
f(n, k) : 노드가 n개, 높이가 k 이하인 트리 개수라 하자. 문제 조건 상 차수가 무조건 0 또는 2여야 하므로 f(1, k)=1이고,
f(n, k)=f(1, k-1)*f(n-1-1, k-1) + ... + f(n-1-1, k-1)*f(1, k-1)이다.
정답은 k 이하 - k-1 이하 = k이므로 f(n, k) - f(n, k-1)이다.
모듈러 처리를 잘 하도록 하자.
BP
문제 조건을 트리로 생각하면, 갈림길 전은 부모 노드, 갈림길 2개는 자식 노드임을 알 수 있다. 따라서 보물로 가는 갈림길에서 입구까지의 모든 경로를 부모를 따라 올라가며 역순으로 출력하면 된다.
BQ
(냄새)
유일하게 안품. 도와주세요! (근데 나올리가 없긴 함)
BR
모든 위치에 대해 순회하지 않았다면 해당 위치와 인접한 모든 위치를 체크하고, 그 사이즈를 vector에 넣어둔다. 이후 sort, 출력
대서진이 추천하는 문제 24개
J, K, O, P(재귀로), U, V, W, AA, AG, AJ, AK, AM, AN, AU(queue로), BC, BD, BE, BF, BJ, BK, BL, BN, BO, BP