[BOJ] 11월 1주차
아무 생각없이 비는 시간마다 틈틈이 풀어서 기록했는데 생각보다 너무 많이 풀었다.
겹치는 유형도 꽤 있었지만.. 좋을대로 생각하기로 했다.
BOJ 1818: 책정리
Link : https://www.acmicpc.net/problem/1818
solution
N의 범위가 20만까지 커질 수 있으므로 LIS를 $O(NlogN)$만에 구해야 한다.
전체 길이 N에 LIS의 길이를 빼주면 된다.
BOJ 12014: 주식, BOJ 3066: 브리징 시그널도 같은 문제.
BOJ 13302: 리조트
Link : https://www.acmicpc.net/problem/13302
solution
문제가 상당히 길지만 변수가 많지 않아서 크게 어렵지 않은 DP 유형이다.
리조트에 가지 않는 날인지 아닌지 그리고 쿠폰이 3개 이상인지 유의해서 케이스를 처리해주자.
BOJ 9576: 책 나눠주기
Link : https://www.acmicpc.net/problem/9576
solution
이분 매칭 알고리즘 기본 유형이다.
잘 했다고 생각했는데 계속 틀린다면 사람의 수를 m이 아닌 n으로 착각한건 아닌지 확인해보자..
BOJ 2367: 파티
Link : https://www.acmicpc.net/problem/2367
solution
에드모든 카프 알고리즘으로 풀 수 있다.
start -> 사람 -> 음식 -> end 로 연결한 후
start -> 사람으로는 용량을 k로, 사람 -> 음식은 용량을 1로, 음식 -> end는 용량을 input의 2번째 줄로 설정하자.
그럼 각 사람당 선택할 수 있는 음식의 가짓수는 k개가 되고 사람당 한 종류의 음식에는 1개만 선택하게 된다.
또한 선택되는 음식의 갯수는 입력받은 값으로 상한선이 제한된다.
네트워크 플로우의 기본 유형에 가깝고, 디자인을 잘하면 쉽게 풀리는 문제라고 생각이 들었다.
BOJ 11405: 책 구매하기
Link : https://www.acmicpc.net/problem/11405
solution
최소 비용 최대 유량(Minimum Cost Maximum Flow) 유형에 속하는 문제.
줄여서 MCMF라고 부르는데 저런 글자만 봤었지 사실 무슨 내용인지는 처음 알게됐다.
덕분에 공부하는 와중에 SPFA도 알게됐고 서로 코드상 차이가 별로 없어서 금방 익힐 수 있었다!
이 문제에서는 최단 거리를 출력할 필요는 없고 최소 비용만 구하면 된다.
에드몬드 카프 알고리즘에서는 ret에 최대 유량만 계속 구했는데 MCMF에서는 가중치를 곱해주면 되겠다.
물론 ret부분 외에도 차이가 분명히 존재하고 헷갈릴 수 있으니 잘 익히도록 하기!
BOJ 11407: 책 구매하기 3는 최단 거리도 출력해야 한다.
BOJ 11408: 열혈강호 5와 바로 위 문제는 같은 문제.
당연하게도 END에 도달하는 유량이 최종적으로 최단 거리가 된다.
BOJ 2228: 구간 나누기
Link : https://www.acmicpc.net/problem/2228
solution
DP 문제. 길이 n의 수열이 있을 때 인접하지 않은 구간 M개로 나눠 구간 내 원소 합의 최댓값을 구해야 한다.
설명을 처음 읽었을 때 솔직히 이게 무슨 소린가 했다. 겹쳐있지 않아야 한다는건 알겠는데 인접하지 않아야 한다니..
말 그대로 구간 [a, b], [c, d]가 있으면 $|b-c| \neq 1$이면 된다. 최소 1칸 이상 떨어져야 한다.
현재 인덱스를 cur, 현재 구간 번호를 turn(1부터 시작)이라 두고 구간이 끝난 상태 여부를 on으로 설정했다.
점화식은 다음과 같다.
$if(on=1): f(cur, turn, on) = max(f(cur-1, turn-1, 0), f(cur-1, turn, 1)) + arr[cur]$
$else: f(cur, turn, on) = max(f(cur-1, turn-1, 1), f(cur-1, turn, 0))$
arr[]가 [-32768, 32767]이므로 결과값이 음수가 될 수 있음에 유의.
BOJ 10277: JuQueen
Link : https://www.acmicpc.net/problem/10277
solution
Lazy Propagtion으로 풀 수 있다. 코어 개수의 상한이 무려 4587520이다! 메모리가 굉장히 빡빡하다.
세그먼트 트리 문제는 항상 구현하기 힘들어서 클래스로 만들어두고 두고두고 복사해서 써먹는데
메모리 초과를 받는 경우가 많지 않아서 오버플로우를 피하고자 long long으로 설정해뒀던게 원인이 됐다. ㅠㅠ
int로 바꾸고 나서 다행히도 AC를 받을 수 있었다!
구간 $[l, r]$에 더하는 값을 $v$라고 하면, 구간에 모두 $v$를 더했을 때 N이 넘어서도, 0보다 작아져서도 안된다.
$v>0$일 땐 전자의 경우만 체크하면 되고, $v<0$이면 후자의 경우만 체크하면 된다.
전자의 경우 $[l, r]$ 중 최댓값을 $MAX$라고 했을 때 $MAX+v$가 $N$을 초과하면 $MAX$부터 $N$까지의 차이만큼만 $[l, r]$에 더할 수 있다.
즉, $MAX+v>N$이면 $N-MAX$만큼 [l, r]에 더해주면 되겠다. 물론 그렇지 않으면 $v$를 더해주면 된다.
반대의 경우도 같은 아이디어로 처리해주면 된다.
구간에 있는 모든 원소에 값을 갱신해야 하므로 Lazy Propagtion을 사용했고
최댓값, 최솟값을 관리해주기 위해 최대, 최소 세그먼트 트리를 만들어서 관리하도록 했다.
맨 위에서 언급했듯이 메모리를 아주 많이 잡아먹으므로 주의!
BOJ 13544: 수열과 쿼리 3
Link : https://www.acmicpc.net/problem/13544
solution
머지 소트 트리(Merge Sort Tree) 유형이다.
이 문제를 풀면서 처음 알게된 알고리즘인데 세그먼트 트리를 베이스로 만들어져서 금방 익힐 수 있었다!
이런 종류의 문제에만 적용할 수 있는 알고리즘인진 모르겠어서 더 찾아서 풀어봐야겠다.
여기서는 이전 쿼리와 현재 쿼리를 XOR한 값으로 계속 출력해줘야 한다!
BOJ 13537: 수열과 쿼리 1는 XOR하지 않고 바로 출력하면 된다.
BOJ 16395: 파스칼의 삼각형
Link : https://www.acmicpc.net/problem/16395
solution
쉬운 DP 문제다.
조합의 성질을 이용해주면 된다. 행과 열이 0부터 시작함에 주의.
BOJ 1620: 나는야 포켓몬 마스터 이다솜
BOJ 5525: IOIOI
Link : https://www.acmicpc.net/problem/5525
solution
$P_n$은 $P_1$ n개로, $P_2$ n-1개, …, $P_n$ 1개로 이루어져 있다.
이 점을 이용해 문자열을 끝까지 훑어가면서 각 $P_n$을 구해 입력받은 N으로 $O(1)$만에 처리할 수 있다.
BOJ 3080: 아름다운 이름
Link : https://www.acmicpc.net/problem/3080
solution
트라이 알고리즘으로 풀었는데, 처음에 input으로 받는 모든 문자열을 때려 넣었다가 메모리 초과를 받았다.
도대체 어떻게 처리해야하나 고민을 하다가 잘 모르겠어서 찾아봤는데 2가지 방법으로 처리할 수 있었다.
1. 접두사에 겹치는 부분을 제거
2. 트라이 메모리를 동적 할당
1번으로는 솔직히 어떻게 하는지 모르겠어서 2번으로 처리했다.
쓰는 문자만 벡터 next에 push해주는데 first를 char, second를 포인터(Trie*)로 설정해주면 된다.
답은 자식들의 수를 팩토리얼로 나타내면 된다. 생각한 것보다 되게 어려웠던 문제..
BOJ 5446: 용량 부족
Link : https://www.acmicpc.net/problem/5446
solution
와일드카드로 다 지울 수 있는지 없는지에 중점을 둬서 케이스를 분류해야 한다.
문자열 뒤에 와일드카드를 붙이면 해당 문자열을 포함하고 접미사가 달린 문자열 또한 지우게 된다.
제거하면 안되는 문자열들을 마구 넣어 각각의 위치에서 root->ban을 true로 만들어주면
와일드카드를 쓸 수 있는지 여부를 체크할 수 있다!
또, 단어가 끝나는 위치면 표시(root->wordfin = true)를 해줘야 일부 케이스에서 답을 갱신할 수 있다.
BOJ 1168: 요세푸스 문제 2
Link : https://www.acmicpc.net/problem/1168
solution (WA)
세그먼트 트리 + 이분 탐색으로 풀었다.
N의 범위가 10만까지 커지므로 $O(n^2)$로 풀면 TLE를 받는다. 사실 재채점받고 틀렸다
세그먼트 트리에서 각 인덱스에 1씩 업데이트한 후 현재 위치 + 앞에 있어야 할 사람의 수를 front라 하자.
매번 M번째를 골라야 하므로 앞에 있는 수 즉, front는 처음엔 M, 다음엔 M+(M-1)이 된다. (턴마다 1명씩 제거하므로 M-1)
이 때 계속 더하면서 N을 넘어갈 수도 있으므로 mod N을 해주는데 이렇게 하면 [0, N-1]에서만 값이 나오니까
0일 경우 front를 N으로 설정해준다. (항상 현재 위치를 포함하므로 $front \geq 1$)
이렇게 설정한 front를 가지고 이분 탐색에서 세그먼트 트리의 구간합 쿼리를 이용해
[1, idx]에서 구간합이 front를 만족하는 idx를 찾아 답으로 넣어주면 된다.
난이도도 실버1에서 골드5로 바꼈길래 조금 놀랐는데
개인적인 생각이지만 세그먼트 트리로 푸는게 정해인데 다른 쉬운(?) 풀이가 더 있어서 골드 5로 조정된 것 같다.
정해가 사실상 유일한 풀이였다면 알고리즘 자체 난이도 + 이분탐색 때문에 플레5는 가지 않을까 싶다.
접근 방법이 다른 문제에 도움이 될 것 같아서 더 좋은 문제로 느껴진다. ㅎㅎ
[내용 추가]
위 풀이는 $O(N(logN)^2)$이고 당시 시간 제한이 0.5초여서 AC를 받았었지만
시간 제한이 다시 0.15초로 바뀌면서 TLE 받았습니다. AC받은 코드로 내용 추가합니다.
solution (AC)
세그먼트 트리로 $O(NlogN)$에 풀 수 있다.
슬랙에서 우연찮게 읽었는데 백준님이 의도한 시간 제한은 $O(NlogN)$라고 하니 이게 맞는 풀이인 것 같다.
결국에 Green55님의 도움을 받아 풀 수 있었는데, 세그먼트 트리로 k번째 원소를 찾을 수 있다는 점이 핵심이었다!
BOJ 2243: 사탕 상자가 k번째 원소를 찾는 세그먼트 트리를 이용하는 문젠데
여기서 사용했던 코드를 가져와서 풀었다. 위에서 쓰던 front는 그대로 이용하면 되겠다.
난이도도 골드5에서 골드4로 재조정됐다! 이렇게 속썩인 문제는 오랜만이다..
BOJ 1238: 파티
Link : https://www.acmicpc.net/problem/1238
solution
‘각 점에서 X까지 최단 거리 + X에서 각 점까지의 최단 거리’의 최댓값이 답이다.
최단 거리는 다익스트라로 구하면 된다.
BOJ 1563: 개근상
Link : https://www.acmicpc.net/problem/1563
solution
DP 문제다. 주어진 조건에 맞춰서 개근상을 받지 못하는 경우 바로 리턴하도록 하자.
late, absent가 들어가는 인자도 모두 day와 같이 1001로 잡아버리면 메모리가 엄청나게 커져버린다!
각각 2, 3만 돼도 바로 리턴할테니 그 이상의 값이 필요 없으므로 cache[1001][3][4]로 잡아주면 되겠다.
BOJ 1535: 안녕
Link : https://www.acmicpc.net/problem/1535
solution
쉬운 DP 문제.
현재 사람을 선택한다면 체력을 깎고 기쁨을 얻으면 되고, 선택하지 않는다면 넘어가는 2가지 케이스만 존재한다.
현재 사람의 번호를 person, 현재 체력을 HP, 현재 사람을 선택했을 때 깎이는 체력을 lostHP[person]
그리고 얻는 기쁨을 getHappiness[person]로 설정했다.
BOJ 11286: 절댓값 힙
BOJ 1916: 최소비용 구하기
BOJ 4485: 녹색 옷 입은 애가 젤다지?
Link : https://www.acmicpc.net/problem/4485
solution
각 점에서 상하좌우에 있는 노드들과 연결하고 시작점에서 다익스트라를 돌린뒤 끝점까지의 최단거리를 구하면 된다.
BOJ 7578: 공장
Link : https://www.acmicpc.net/problem/7578
solution
B열에 기계와 매칭되는 A열 기계의 인덱스를 나열했다고 하자. 현재 위치를 $i$라 하자.
그럼 $i$번째보다 앞에있는 수들 중 보다 큰 값의 갯수를 합친게 답이 된다.
매칭시킨 후 세그먼트 트리에 값을 업데이트하면서 답을 갱신해줬다.
BOJ 15899: 트리와 색깔
Link : https://www.acmicpc.net/problem/15899
solution
머지 소트 트리 + DFS로 풀었다.
처음에 엣지의 정보가 입력으로 들어오는데 이걸 갖고 트리는 만들 수 있겠는데 구간은 어떻게 잡을까 싶어서
계속 고민해봐도 모르겠어 가지고 kks227님의 풀이를 참고했다!
전위 순회를 하면서 번호를 새로 부여하면 출력시 루트를 기준으로 뒤에는 서브트리의 정보가 순서대로 나오게 된다.
왼쪽/오른쪽 자식이 픽스된게 아니어서 어떻게 전위 순회를 돌아야하나 하다가 DFS로 돌려버렸다.
입력받은 노드의 번호를 i라 하면 새로 부여한 번호는 match[i], 구간의 끝 번호는 bound[match[i]]로 설정했다.
이후에는 머지 소트 트리에 정보를 입력해준 후 M개의 쿼리를 처리해주면 된다.
BOJ 7469: K번째 수
Link : https://www.acmicpc.net/problem/7469
solution
머지 소트 트리 + 이분 탐색으로 풀었다.
쿼리가 주어진 구간 $[l, r]$에서 정렬한 상태에서 값을 찾으니 머지 소트 트리가 적합하다고 볼 수 있겠다.
그 구간 안에서 K번째 값을 찾아야 하는데 특정 값의 앞 혹은 뒤에 있는 원소의 갯수를 탐색하는 머지 소트 트리 특성을
이용해 이분 탐색으로 답을 찾아주면 된다.
원소가 $[-10^9, 10^9]$임에 주의.
BOJ 3640: 제독
Link : https://www.acmicpc.net/problem/3640
solution
MCMF로 풀 수 있다.
시작 지점과 목적지가 픽스된 상태이고 비용이 가장 적은 길로 이동하도록 해야한다.
MCMF를 돌리기 이전에, 설명에 있는 힌트(TC 그래프)를 참고하면 한 노드에서 엣지가 2개가 생길 수 있다.
이렇게 되면 MCMF를 위해 반대 방향에 비용을 빼주는 부분이 이후 입력되는 값에 의해 수정될 수 있다.
때문에 정점을 분리해서 진행해야 한다. 나는 엣지가 본인을 향하면 IN, 다른 곳을 향하면 OUT을 설정했다.
비용은 MCMF 내부에서 처리하므로 간선의 용량을 모두 1로 설정해주고 MCMF를 한 번 돌린다.
그럼 가장 비용이 적은 길은 용량이 다 차버린 상태기 때문에 다음 탐색에 영향을 주지 못한다.
이제 MCMF를 한 번 더 돌려주면 다음으로 비용이 가장 적게 드는 길을 찾아 마지막에 도달하게 된다.
마지막까지 도달하면서 걸린 비용들의 합이 답이 되겠다.
BOJ 1300: K번째 수
Link : https://www.acmicpc.net/problem/1300
solution
위에서 BOJ 7469: K번째 수를 풀고 나니 생각나서 풀어봤다.
이분 탐색으로 푼다는건 알겠는데 도통 어떻게 해야하는지를 모르겠어서 서너번 시도하다 포기했었던 문제였는데
위에 문제는 푸는데 이건 왜 못풀었지 싶어서 해보니까 금방 풀렸다! ㅎㅎ
N이 $10^5$까지 커지므로 1차원 배열에 나열해놓고 정렬하는건 시간도 메모리도 문제가 생긴다.
(사실 이렇게 풀어서 가능하면 정렬문제지 이분탐색 문제가 아니긴 하다)
그럼 어떻게 해야할까 고민을 좀 해봤는데, 잘 생각해보면 각 열에 있는 원소들은 행의 번호만큼 곱해진다.
예를 들어 N=3이면 첫 행이 [1, 2, 3]이고 2번째 행은 [2, 4, 6]이 된다.
그럼 k번째 값이 뭔지는 모르겠지만 x라고 했을 때 각 행에서 x보다 작은 수를 모조리 더했을 때
k-1개가 되는 즉, x가 k번째가 되는 수를 찾으면 된다.
그럼 첫 행을 1차원 배열 a에 담아주고 시작하자. 배열 a에 대해 x를 이분탐색해서 얻은 값을 답에 갱신한다.
이 때, 다음 행으로 넘어가면서 각 원소를 곱해주게되면 역시 시간 초과의 그림자를 피할 수 없다.
생각해보면 위에서 말했듯이 다음 행의 원소를 아주 간단히 예측할 수 있다. 행의 번호의 곱이라는 점 말이다.
그렇다면 굳이 배열 a에 있는 원소를 직접 곱해줄 필요가 없다. x를 행의 번호로 나눠주면 된다!
이 점만 캐치한다면 간단히 해결할 수 있다.
BOJ 2662: 기업투자
Link : https://www.acmicpc.net/problem/2662
solution
DP 유형.
얻는 이익의 최댓값을 구하기 위해서 DP를 짜는게 메인이기는 하지만 개인적으로 최댓값을 찾는건 쉬웠다.
다만 각 기업이 투자한 액수를 파악하는 방식이 뭘지에 대해 계속 고민해본 것 같다. 생각보다 오래걸렸다!..
DP를 돌리면서 최댓값을 갱신할 때 현재 금액을 M, 팀 번호를 E라 하면 query[M][E]를 투자한 금액으로 설정했다.
이는 나중에 DP로 최댓값을 찾았을 때 (최댓값을 갖는 경로가 정해졌으므로) for문에서 역으로 순회하도록 했다.
그럼 각 팀이 투자한 금액을 차례대로 구할 수 있게 된다!
BOJ 4883: 삼각 그래프
Link : https://www.acmicpc.net/problem/4883
solution
DP 유형.
점화식은 문제 설명에 있는 그림대로 구현하면 되는데 기저 사례를 마지막 행일 때로 설정해서 애먹었다.
열이 어디냐에 따라서 반환해야 하는 값이 달라짐에 유의.
BOJ 1275: 커피숍2
Link : https://www.acmicpc.net/problem/1275
solution
세그먼트 트리로 풀 수 있다.
문제 설명 중 다음 부분을 조심하자.
x~y는 당연히 x번째 부터 y번째가 맞다. 하지만, 이 문제에서는 x>y인 경우 y번째 부터 x번째이다.
BOJ 3653: 영화 수집
Link : https://www.acmicpc.net/problem/3653
solution
영화 번호가 모두 [1, n]에 속한다는 점, 쿼리가 최대 10만번까지 들어올 수 있다는 점을 이용해
영화 번호를 x라 했을 때 처음에 10만+x 인덱스에 저장하도록 한다. (세그먼트 트리에 업데이트)
그리고 idx[x]를 x번 영화가 실제로 있는 인덱스라고 하자.
매 쿼리에서 x번 영화를 뽑으면 그 위에 있는 값은 [1, idx[x]-1]에서 구간합이 된다. 세그트리로 구해주면 된다.
이후 x번 영화를 뽑아 맨 위로 올려놓으므로 현재 위치의 값을 0으로, 그리고 가장 맨 위를 가리키는 cnt번에 업데이트한다.
마지막으로 idx[x]를 cnt로 업데이트하면 쿼리 1개를 처리하는 과정이 끝난다. 이를 반복해주면 되겠다.
BOJ 2517: 달리기
Link : https://www.acmicpc.net/problem/2517
solution
매번 들어오는 값을 x라 할 때 x 이상인 값의 갯수를 출력해줘야 한다.
x가 $10^9$까지 커질 수 있기 때문에 인덱스에 곧바로 업데이트 해주는건 메모리상 불가능 하므로
x의 값을 압축해서 세그먼트 트리를 이용하면 된다.
압축하는 방법은 다른 방법이 있는지 모르겠으나 나같은 경우 구조체와 정렬을 이용했다.
BOJ 5676: 음주 코딩
Link : https://www.acmicpc.net/problem/5676
solution
BOJ 11505: 구간 곱 구하기와 같은 유형 문제.
세그먼트 트리로 풀 수 있다.
BOJ 2268: 수들의 합
BOJ 9426: 중앙값 측정
Link : https://www.acmicpc.net/problem/9426
solution
연속된 K개를 원소로 가지는 모든 구간에 대한 중앙값을 모두 더해 출력해야 한다.
결과값은 int로는 오버플로우가 날 수 있으니 long long으로 처리해야 한다.
세그먼트 트리를 이용해 처리했고, 세그먼트 트리에 들어간 값이 K개가 될 때마다 중앙값을 취한 후
가장 마지막에 업데이트된 값을 빼주는 식으로 업데이트 하면 된다.
BOJ 14438: 수열과 쿼리 17
BOJ 12837: 가계부 (Hard)
BOJ 2342: Dance Dance Revolution
Link : https://www.acmicpc.net/problem/2342
solution
케이스 분류가 좀 필요한 DP 문제다.
위치가 0(문제 설명 참조)일 때 다음 위치로 이동하면서 필요한 2의 힘으로 눌러야 하고
그렇지 않은 경우 다음 위치가 인접하다면 3, 반대라면 4의 힘으로 눌러야 한다.
각 턴을 cnt, 왼발의 위치를 l, 오른발의 위치를 r로 설정했다.
댓글남기기