32290 MEX vs OR B1
#bruteforce, #implementation
N이 매우 작기 때문에 매번 i or x한 값을 리스트에 넣은 다음, MEX를 구해주면 된다.
MEX를 구하는 방법은 여러가지 있겠지만 나는 i or x한값을 정렬했을때, 인덱스와 값이 다른 시점을 mex로 구현하였다.
XOR만 나오면 항상 정수론적인 생각을 먼저하게 된다...
32289 Max-Queen S5
#greedy #math
모든 자리에 퀸을 넣는 것이 가장 최적의 경우이다.
그렇다면 가로방향의 공격 쌍수, 세로방향의 공격 쌍 수 대각선 방향의 공격쌍수 이렇게 3가지로 나누어서 생각을 해보았을때, 점화식을 도출할 수 있다.
문제에비해 난이도가 저평가된것 같다..
http://boj.kr/abb650e031d34f4fa24702fc4788f6e7
3682 동치 증명 P3
#graph #scc
저번주에 푼다고 하고 못푼 문제다.
SCC으로 묶을수 있는 간선들은 모두 동치가 될 수 있다고 설명할 수 있다.
그렇기에 SCC단위를 정점으로 간소화 한다음, 이 정점 집합들을 하나의 SCC로 만들어야 하는 문제로 바꿀 수 있는데,
그렇다면 각 node의 indegree와 outdegree가 모두 1이상이 되어야 하기 때문에 max(indegree == 0, outdegree == 0)인 수를 찾으면 된다.
SCC 구현 코드를 코사라주 알고리즘을 사용했는데, 아무래도 똑같은 그래프를 2개 만들다 보니 MLE가 자주 발생한다. 그렇기 때문에 비교적 느린 python3이나, 타잔 알고리즘으로 SCC를 구현해야 한다.
타잔알고리즘과 SCC를 정점으로 치환하는 방법을 배운 문제
2812 크게만들기 G3
#greedy #stack
일단 m번 무조건 지워야 하기 때문에 최대 자릿수는 n-m자리일 것이다.
그렇다면 무조건 앞에 수를 가장 큰 수로 두어야 할 것이고, 스택에 하나씩 넣으면서 앞에 자리수가 뒤에자리수보다 작다면 계속 그 작업을 수행해주어야 할 것이다.
추가 반례로 모두 다 같은자리인경우 m번 연산을 안할경우가 있는데, 이 점을 따로 예외 처리해주자.
27653 최소 트리 분할 G2
#dfs #greedy
연산 내용이 주어진 트리의 부분 그래프의 가중치를 1 늘리는 과정이기 때문에 현재 노드를 기준으로 본다면, 현재 노드의 부모노드의 목표 weight보다 작으면 부모노드의 연산으로 수행할 수 있다.
그러기 때문에 대충 1번 노드를 root node으로 잡고 정답은 root node의 weight + sigma 2~n : max(node weight - parent node weight, 0)으로 정의할 수 있다.
dfs으로 각 노드의 부모노드와 목표 가중치를 비교하자
17233 문자열 장식 P3
#kmp #sweeping
KMP알고리즘을 수행하면, 원본 문자열에서 부분문자열이 몇개 있는지, 어디에 있는지 모두 구할 수 있을 것이다. 그렇다면 투 포일터를 활용해 l~r 범위 내에 모든 부분문자열이 있느냐?를 체크할 수 있다. 매번 체크를 해주면서 최소 구간을 찾자.
대충 시간복잡도를 O(N+M+2N) 정도로... 선형시간내에 해결할 수 있을 것이다.
22217 Scales S2
#implementation, #math
m을 3진수로 나눌 때 bit가 2인 경우, 왼편, 그 외인경우 오른편에 두어 비트연산을 했을 때 그 수가 나올 수 있게 구현하면 된다.
16991 외판원순회 3 G1
#tsp
각 좌표간의 거리를 n^2으로 구해 distance를 구한 다음, 그것을 활용 해 외판원순회를 해주면 된다.
Bitonic Tour라는 좌표상의 외판원순회 알고리즘이 있던데, 이 문제인줄 알았는데, 알고보니 더 쉽게 해결할 수 있었다.
Bitonic Tour 공부해보면 좋을듯. .
1251 단어 나누기 S5
#bruteforce
그리디하게 접근해볼까 하다가 같은 가장 사전순 작은 문자열 일때, 얼마나 더 길게 나눌것인가 생각을 좀 해보았는데, n이 매우작기 때문에 n^3으로 모든 문자열조합을 만드는 방식으로 풀 수 있다.
2993 세 부분 S5
#bruteforce
1251과 동일
17413 단어뒤집기 2 S3
#stack #implementation
스택을 사용해 구현해주면 된다. 다만 신경써줘야할 부분은 태그 내에 공백이 있는 case를 예외처리 해주면 쉽게 풀린다.
'ps > Solved' 카테고리의 다른 글
| 10월 4째주 PS정리 (0) | 2024.10.22 |
|---|---|
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 1째주 PS 정리 (0) | 2024.09.30 |
| 9월 4째주 PS정리 (2) | 2024.09.24 |
| 9월 3째주 PS 정리 (0) | 2024.09.16 |