[Programmers] Level 4
문제 목록 바로가기 : https://programmers.co.kr/learn/challenges
3 x n 타일링
도둑질
Link : https://programmers.co.kr/learn/courses/30/lessons/42897
solution
이웃한 집들을 선택할 수 없는 상황에서 최댓값을 취할 수 있도록 집을 선택해야 한다.
처음에 시작했는지 여부가 마지막 집을 선택할 수 있는지 여부를 나타낸다. 때문에 이를 인자로 나타내줘야 한다.
dp[i][start] : i번째 집을 선택 + 시작점을 선택했는지 여부
start 유무가 점화식에 영향을 주진 않는다. 현재 위치를 선택하는지 선택하지 않는지로 나눌 수 있다.
$dp[i] = max(dp[i-2]+money[i], dp[i-1])$
4단 고음
Link : https://programmers.co.kr/learn/courses/30/lessons/1831
solution
곱하기 뒤에는 더하기 2개가 나와야 한다. 하지만 꼭 곱하기와 붙어있을 필요는 없다.
n의 범위가 굉장히 크기 때문에 일일이 구현해서 탐색하기에는 너무 케이스가 많다.
배열로 선언해서 처리하기에도 메모리, 시간 문제가 있으므로 수식으로 해결해줘야 한다.
1부터 시작하지 않고 끝에서부터 시작하도록 하며, 더하기(plus)가 2개 이상이고 3으로 나누어 떨어지면 나눠준다.
그렇지 않은 경우는 현재 값을 1씩 빼면서 더하기를 1씩 증가시키면서 재귀를 돌려준다.
1에서 n으로가 아닌 n에서 1로 간다고 생각을 해봐야 한다.
현재 더하기(plus)의 갯수가 4이라면 (모르는 상태)++++ 인데 곱하기가 2개 등장해야 하므로 값은 $3^2$가 된다.
일반화 하면 현재 값이 cur일 때 $3^{\frac{plus}{2}} <= cur$이어야 한다.
이를 성립하지 않으면 더 이상 진행할 수 없으므로 바로 리턴해 커팅해주면 통과할 수 있다.
가사 검색
Link : https://programmers.co.kr/learn/courses/30/lessons/60060
solution
범위가 너무 커서 설마설마 했는데.. 트라이 알고리즘으로 풀어야 한다.
솔직히 한 번 경험해보자는 목적으로 공부했었던 알고리즘인데 코테 문제로 버젓이 나올지 몰랐다.
직접 구현할 자신이 없어서 예전에 백준에서 썼던 코드를 조금 긁어서 썼다. ㅠㅠ
신박하면서도 난이도가 높다는 생각이 들었었는데 코테 영역에 들어오다니..
트라이 알고리즘에 대한 자세한 설명은 생략한다.
간만에 만져보는 알고리즘이어서 삐걱삐걱대며 풀었는데 유의하면 좋은 점이 크게 3가지 정도 있는 것 같다.
물론 트라이 알고리즘으로 푼다는게 전제다.
- 구조체 Trie의 지역 변수에 SIZE를 배열로 선언해 길이를 인덱스랑 매핑시켜 구하면 TLE를 받는다.
words[i]의 길이는 최대 1만이므로 root를 1만개 만들어 놓고 이 인덱스에 words[i]의 길이를 매핑하자.
그럼 정확성 테스트에서 메모리는 거의 10MB 안쪽으로 들어올 것이다. (전자로 풀면 900MB가 넘기도 한다)
- 구글링해서 코드를 긁어와 푸는 경우라면 대부분 string을 받는 인자에 레퍼런스(&)가 붙어있겠지만
웃기게도 내가 예전에 썼던 코드에서는 &가 붙어있지 않았다..! 이 부분은 속도에 분명히 영향을 준다.
- 설명에도 포함돼있는 내용이지만 놓치기 쉬운 문자열이 있다. 바로 ?로만 이루어져 있는 문자열이다.
이 부분을 예외 처리해주지 않으면 당연하게도 AC를 받을 수 없다. 어렵지 않으니 꼭 처리해주자.
올바른 괄호의 갯수
Link : https://programmers.co.kr/learn/courses/30/lessons/12929
solution
DP로 풀 수 있다. Level 4에 실려있는데 비해서 굉장히 쉬운 편.
a를 괄호의 갯수, b를 총합(열린 괄호는 +1, 닫힌 괄호는 -1)이라 하면 점화식은 다음과 같다.
$f(a, b) = f(a-1, b-1) + f(a-1, b+1)$
게임 맵 최단거리
Link : https://programmers.co.kr/learn/courses/30/lessons/1844
solution
BFS 기본 유형.
개인적인 생각이지만 Level 4에 있을 문제는 아닌듯 하다.
숫자 블록
Link : https://programmers.co.kr/learn/courses/30/lessons/12923
solution
[begin, end]에 있는 값을 idx라 했을 때 idx로 나누어지는 (idx를 제외한) 가장 큰 약수를 구해야 한다.
처음엔 범위도 그렇고 이분 탐색으로 구해볼까 했는데 나누어 떨어지는 조건 말고는 떠오르지 않아서
이리저리 건드려보다가 이분 탐색으로 푸는건 포기했다. (애초에 풀 수 있는 방법인지 의문이다)
그래서 직접 약수를 구하는 방법으로 접근해보자는 생각에 에라토스테네스의 체에서 아이디어를 가져왔다.
어떤 수 $N$이 있을 때 이 수의 약수를 판별하는데는 $O(\sqrt{N})$의 시간이 걸린다. (solve())
따라서 효율성 테스트도 무리없이 통과할 수 있었다.
begin이 1이면 첫번째 값은 반드시 0이 되고, 블록의 번호는 $10^7$까지임에 주의하자.
호텔 방 배정
Link : https://programmers.co.kr/learn/courses/30/lessons/64063
solution
Union-Find로 풀 수 있다.
처음엔 k가 $10^{12}$까지 커질 수 있다고 하길래 이분 탐색으로 처리하려고 시도해보다 실패했다..
Union-Find는 그래프 문제나 알고리즘에서 Union-Find가 쓰이는 경우(MST 등)말고는 써본 적이 없었는데
이런 경우에서도 쓰일 수 있다는 점이 인상적이었다!
그래프 문제에서만 주로 써봤기 때문에 가장 먼저 언급된 숫자 N이 있으면 N보다 큰 숫자들 중
N과 한 집합으로 묶어야 할 때 N번을 기준으로 묶었었는데 이 문제는 반대로 해줘야 한다.
가령, 3번과 4번을 집합으로 묶는다고 하면 3번은 4번을 가리키고 4번은 자기 자신을 가리키도록 하면 된다.
이런 컨셉으로 설정해놓으면 문제에서 요구하는 방향과 같다는걸 알 수 있다!
다만 일반적인 Union-Find는 다른 집합과 엮이지 않은 경우 스스로를 가리키도록 기본값이 설정돼있기 때문에
전처리를 다음과 같이 해주게 된다.
for(int i=1; i<=n; ++i)
uni[i] = i;
근데 이 문제는 방 번호가 $10^{12}$까지 커질 수 있다. 이런 전처리를 해주게되면 틀림없이 TLE를 받게 된다.
방 번호가 1번부터 시작하고 기본값은 모두 0이므로 위와 같은 전처리를 해주지 말고 기본값인 0을 이용하자.
그럼 본인의 집합을 찾는(부모를 찾는) 함수 find()는 다음과 같이 설정하면 된다.
ll find(ll n){
if(uni[n] == 0) return n; //원래는 if(uni[n] == n)
return uni[n] = find(uni[n]);
}
서로 같은 집합으로 묶어주는 하는 함수 make_union()는 방 번호가 큰 쪽으로 향하도록 수정해주면 된다.
void make_union(ll a, ll b){
ll pa = find(a), pb = find(b);
if(pa>pb){ //원래는 pa<pb
uni[b] = pa;
}
else
uni[a] = pb;
}
위에서 말했듯이 집합(부모)이 설정되지 않았다면 uni[n]=0이고, find(n)는 n를 반환하게 된다.
고객이 n번 방을 원하는데 빈 방이라면(if(find(n)==n)) find(n)을 다음 칸(n+1)의 집합(부모)와 엮어줘야 한다.
따라서 다음과 같이 처리해주자.
if(find(room_number[i]) == room_number[i]){
answer[i] = room_number[i];
make_union(room_number[i], room_number[i]+1);
}
이미 있는 방이라면 다음과 같이 처리해주면 되겠다.
else{
answer[i] = find(room_number[i]);
make_union(find(room_number[i]), find(room_number[i])+1);
}
최적의 행렬 곱셈
Link : https://programmers.co.kr/learn/courses/30/lessons/12942
solution
백준에서 비슷한 문제를 풀었던 기억이 있어서 바로 DP로 접근했다.
구간의 왼쪽을 $l$, 오른쪽을 $r$, 중간에 나누는 지점을 $m(\in [l, r))$로 설정했다.
$f(l, r)$를 구간 $[l, r]$에서 행렬 곱셈의 최솟값이라 하면 점화식은 다음과 같이 설정할 수 있다.
$f(l, r) = max(f(l, m)+f(m+1, r)+matrix_sizes[l][0]\times matrix_sizes[m][1]\times matrix_sizes[r][1])$
스티커 모으기(2)
Link : https://programmers.co.kr/learn/courses/30/lessons/12971
solution
프로그래머스 lv4에 있는 도둑질과 풀이가 같다.
다만 도둑질은 N>=3 이고 이 문제는 N>=1임에 주의.
단어 퍼즐
Link : https://programmers.co.kr/learn/courses/30/lessons/12983
solution
간단한 DP 문제.
dp[i] : 문자열 t에서 [0, i)까지 만드는데 필요한 문자열(str)의 최소 갯수
$if(match): dp[i+str_len] = dp[i]+1$
지형 편집
Link : https://programmers.co.kr/learn/courses/30/lessons/12984
solution
브루트 포스로 처음에 풀었는데 TLE를 받았다.
백준에서 브루트 포스로 풀 수 있는 비슷한 문제는 여기에 있다.
시간을 어떻게 줄일 수 있을까 고민을 하다가 잘 모르겠어서 검색을 해봤는데 이분 탐색으로 푸는 풀이가 있었다.
일단 답이 나올 수 있는 하한과 상한은 land에 있는 최솟값(lf)과 최댓값(hf)이 된다.
그렇다면 [lf, hf]에서 이분 탐색으로 답을 구해줘야 한다는건 알겠는데, 기준이 없어서 좀 당황스러웠다.
어떻게 기준을 잡아야 할지 보니 현재 층을 cur, 현재 층으로 편집할 때 드는 비용을 f(cur)이라 하면
f(cur)과 f(cur+1)의 대소 비교를 통해 어느 쪽이 더 많이 들 것인지 정해졌다면 바운더리를 좁혀갈 수 있다.
즉, $f(cur)<f(cur+1)$일 때 항상 $f(cur)<f(cur+k), k>1$를 만족한다. (반대도 당연히 성립)
최종적으로 이분 탐색을 통해 최적의 층(Floor)을 찾아준 뒤 f(Floor)을 반환해주면 되겠다.
같은 로직으로 이렇게 저렇게 풀어봤는데 큰 차이가 없는 코드에서 TLE를 여러번 받았었다.
계속 효율성 테스트 4번에서 걸렸는데, 다른 효율성 테스트에서는 다른 코드 결과와 별로 다르지 않았던 걸로 보아서
시간 제한이 굉장히 빡빡한걸로 조심스럽게 예상해본다.
문제 없이 한 번에 통과한 분들도 분명 많이 계시겠지만 나같은 경우 시간 복잡도상으로 차이가 없는 코드였는데
계속 통과를 못해서 시간을 버린 케이스라(..) 솔직히 굉장히 마음에 안드는 문제다. 😠
블록 게임
Link : https://programmers.co.kr/learn/courses/30/lessons/42894
소스 코드
solution
하드코딩 하는 것 말고는 좋은 방법이 떠오르질 않아서 접어놨습니다.
구현 문제. 생각보다 시간이 오래 걸렸고 허를 찌르는 반례를 만나서 시간도 좀 걸렸다.
4개의 1x1 블록으로 구성된 도형 4개를 회전하면 12가지가 나오지만 속을 꽉 채울 수 있는 도형은 5가지 뿐이다.
위에서 1x1 블록을 쌓을 수 있도록 열려있는 도형만 찾으면 된다. 이 케이스들을 찾으려고 solve 1~5 함수를 만들었다.
탐색은 맨 위의 행부터 맨 아래 행까지 탐색하도록 하고 블럭을 발견하면 solve()를 통해 열린 도형인지 체크한다.
만약 열린 도형이 맞다면 쌓아야 하는 부분에서 첫 번째 행까지 블록이 없는지 체크(highest())하고
없다면 채울 수 있는 도형이므로 답을 갱신하고 블록이 차지하고 있던 값을 모두 0(빈 칸)으로 돌려준다.
처음에 탐색할 때 도형을 발견할 때까지 같은 열에서 행을 위에서 아래로 훑어가는데 발견하고 멈추면 안된다.
이 부분때문에 바로 AC를 받지 못했는데 이 부분때문에 막힌다면 이 글을 참고해보길 바람.
블럭에 닿는 부분이 어느 부분인지 모르기 때문에 위치가 어디냐에 따라 탐색해야 하는 다음 좌표값을 다르게 설정해주느라
하드코딩이 돼버렸는데 좀 찝찝하다. 실전에서 이 문제를 만났으면 푸는건 둘째치고 멘탈부터 나갔을거 같다.
[3차] 자동완성
Link : https://programmers.co.kr/learn/courses/30/lessons/17685
solution
Trie 알고리즘으로 풀었다.
지역 변수로 문자열이 끝나는 위치임을 의미하는 finish 외에
단어가 끝난 흔적이 있는지를 의미하는 WORDFIN, 현재 경로에서 등록된 단어의 갯수를 의미하는 SIZE를 추가했다.
기저 사례로는 finish가 true일 때 또는 SIZE가 1일 때 단어가 1개임을 의미하므로 값을 바로 리턴하도록 했고
이외의 경우는 연결된 경로를 탐색(DFS)하도록 했다.
하다보니 백준 문제만 계속 풀게돼서 프로그래머스 문제는 잘 손이 안갔는데 어떻게 lv4 문제도 풀 수 있는만큼 끝냈다.
사이트 내에서 최근에 대회가 진행되면서 업로드되는 문제가 레벨별로 조금씩 있던데 천천히 건드려봐야겠다.
시간재고 푸는 시스템도 있던데 이것도! 코테 준비하기 전에 미리미리 해보자!
댓글남기기