#implementation
개빡구현문제다.....
우선 전체 프로세스는 상어를 잡는다 -> 상어 이동 -> 상어끼리 먹는다 이다.
각 프로세스 별 구현해주면 된다.
상어의 움직임을 수식화하여 매 이동을 하지 않고, 시간을 개선할 수 있을 것 같긴한데, 일단 통과했으니 넘어가자. 개선점이 있어 보인다.
| 11월 2째주 PS 정리 (0) | 2024.11.04 |
|---|---|
| 11월 1째주 PS정리 (0) | 2024.10.28 |
| 10월 4째주 PS정리 (0) | 2024.10.22 |
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
| SCC & 2-SAT (1) | 2024.11.05 |
|---|
Strongly Connected Components with 2-SAT.pdf
0.75MB
Study 내 발표했던 자료 upload
TODO : https://www.acmicpc.net/problem/11281 2-SAT 명제 추적 해설 내용 올릴 것.
| Ternary Search (0) | 2024.11.06 |
|---|
#ad_hoc, #geomatry
초기에 sweeping 하여 xy를 정렬하여 작은 순서대로 상하좌우 길이1의 직선을 긋는 방법으로 생각하였다.
94%에서 WA를 받았고, edge cases에 대해서 많이 생각을 해보았는데 맞왜틀의 연속
입력으로 들어오는 좌표랑 출력해야하는 좌표의 범위가 서로 다른데, 이걸 바탕으로 기울기가 모두 같은 직선을 작성하면 되는 문제 이다.
초기에 너무 많은 case를 맞추어 접근을 잘못하였지만, 새로운 접근법을 찾는 것 보다 edge case를 찾는데 집중한문제
#deque_trick
덱트릭을 활용해 size 내 구간 별 최대 값을 구하는 문제이다.
새로운 원소가 추가 될 때 마다 현재 처리 중인 원소 li[i]가 덱의 뒤쪽에 있는 원소들보다 크거나 같으면, 그 뒤의 원소들은 더 이상 최대값이 될 수 없으므로 덱의 뒤에서부터 해당 원소들을 모두 제거한다 그 후, 현재 원소의 인덱스 i를 덱의 뒤에 추가한다. 이 과정을 매번 반복해주며, 구간 내 최대값을 출력해주자.
세그트리로 구간 별 최대값을 구하는 코드도 가능 할 듯 해 보인다.
http://boj.kr/383006e102234141b3d2edea51db0548
#topological_sort
문제에서 언급하는 출처와 출처를 인용하는건 그래프의 edge로 똑같이 생각해볼 수 있다.
위상정렬을 한 다음, 위상정렬 한 결과를 DFS했을 때, 한개의 그래프로 구성되어 있다면 1을 출력, 아니다면 2를 출력 하면 된다.
topological sort을 했을 때, cycle이 생긴다면, 0을 출력해주면 된다
#2-SAT
일반적인 2-SAT을 적용하고 역추적을 어떻게 해야하는가를 물어보는 문제
Tarjan 알고리즘으로 SCC를 구성하였다면, 역순으로 위상정렬된 SCC 그룹에 해를 적당히 부여해주어야 한다.
부여하는 방법을 greedy하게 생각하여 SCC 번호가 큰 순서대로 변수를 할당해보자.
dfs를 수행할 때 깊이가 깊은 것부터 scc 번호가 매겨졌으므로, scc 그룹의 번호가 큰 것이 위상적으로 앞에 위치하기 때문이다. 따라서 scc 번호를 기준으로 내림차순 정렬을 한 뒤, 앞에서부터 false를 매겨주면 된다.
#2-SAT, #Bruteforce
위 11281 코드를 복붙했지만, 이 문제같은 경우, n이 작기 때문에 2^n 비트배열을 활용하여 bruteforce로 순회가 가능한 것으로 보인다.
#trie
trie class를 선언해 trie 안에 trie를 넣고.. 이런 방식으로 trie를 구성해주면 된다.
반대로 출력은 trie를 sort해 dfs하여 내림차순으로 출력해주도록 하자
trie 기본 구현문제
굳이 trie 몰라도 다진 트리로 구현가능해 보인다.
| 11월 3째주 PS정리 (0) | 2024.11.11 |
|---|---|
| 11월 1째주 PS정리 (0) | 2024.10.28 |
| 10월 4째주 PS정리 (0) | 2024.10.22 |
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
#greedy
n이 10만이기 때문에 dp보단 O(n), O(n log n) 그리디하게 접근해보자.
맨앞에 있는 사람은 무조건 발휘할수 있다. <- 이는 젤 큰 값을 배치하면 될 것.
그렇다면 그 다음 사람은 무조건 할 수 없다. <- 제일 작은 값을 배치하면 됨.
... 이런 방식으로 배열을 정렬 한 다음, 큰값-작은값 순으로 배치하면 O(n log n)만에 풀 수 있다.
여담으로 예제에 나온 내용은 그냥 낚시다.
#bit dp
외판원순회문제처럼 보이지만, 사뭇 다르다. (다시 출발로 돌아오지 않아도 되고, 이미 갔다온데를 한번더 갈 수도 있다.)
bit dp으로 해결해보자.
dp[cur][visited]: 현재 행성이 cur이고, visited는 지금까지 방문한 행성들의 집합일 때, 시작점에서부터 현재 상태까지의 최소 시간을 비트로 표시 한거라고 정의하자.
현재 상태에서 모든 가능한 다음 행성으로 이동하면서 DP 값을 갱신하자.
모든 행성에서 끝날 수 있으므로, dp 배열의 해당 상태 중 최소값을 찾자.
#geometry
Convexhull과는 아무 상관없는 문제다...
P를 통과하는 어떠한 직선으로 볼록 다각형을 절단해도, 절단 후에 얻어진 2개의 볼록 다각형의 면적이 동일한 점 P의 좌표를 구하라. 는 문제이다.
이 말은 즉슨, 도형이 대칭일 때 그 대칭점의 중심점을 계산해야 되기 때문에, 점의 갯수가 홀수면 불가능하다.
짝수 개의 점들로 이루어진 다각형에서 각 점과 그 대칭점의 중점을 계산한 다음, 그 중 첫 번째 중점을 출력 하면 된다.
#greedy
case를 나눠서 생각해보자. greedy하게 SKH가 같이 있으면 그대로 SK, SH, KH가 있다면 1개씩 끼울 수 있을 것이다. S, K, H 따로 있다면, KH, SH, SK를 끼워 만들 수 있을 것이다. 그 외에도 필요한 SKH 1개씩 사용해 독립적으로 SKH를 만들 수 있을 것이다.
예제를 보면 끼워 넣는 과정에서 한개만 다 사용하는 방법이 아닌 밸런스 있게 SKH를 만들어야 한다.
임의의 ) 에 대해서, K에 SH를 붙이고 H에 SK를 붙이고 SKH를 붙이는 나머지 과정을 모든 x에 대해서 수행한다. 나머지 2가지 방법도 동일하게 수행한다.
https://www.acmicpc.net/source/share/3f9f326f740f4e7aa2bdde8c57f3cbb1
#greedy #string
우선 밑줄갯수의 차가 1이기 때문에 밑줄의 갯수가 n인 경우, n+1인 갯수를 각각 구해주자.
그런 다음, 밑줄 다음 문자가 소문자인경우, 밑줄이 더 우선순위가앞이기 때문에 밑줄 갯수를 n+1이 되어야 한다. 반대로 대문자일 경우, 대문자가 더 우선순위 앞이기 때문에 밑줄 갯수가 n개 되어야 한다.
추가적으로 무조건 문자열의 길이를 k정확하게 맞춰야 하기 때문에 전부 다 대문자일 경우, 문자열 뒤에 밑줄은 강제로 n+1개를 만들어주자.
#bruteforce
먼저달릴 1인 + 나중에 달릴 3인으로 최적의 4인을 뽑아야 하는 문제다.
나중에 달릴 기록으로 먼저 sort를 해준 다음, 1,2,3째 + 나중에 달릴 친구가 가장 최적일 것이다.모든 n을 순회해주면서 나중에 달릴친구 + 1,2,3번쨰의 최적조합을 구성해보자.최종 선정된 사람들의 이름도 출력해주어야 하기 때문에 그 사람들의 index도 신경써주면서 구현해주어야 한다. 처음에 permutation으로 구현하였다가 MLE맞았다...http://boj.kr/669edc1bf2564b3498312e87ed4bf4d4
#dsu #geometry
문제를 정리하자면, 직사각형안에 여러개의 원이 있는데, 왼쪽 하단에서 오른쪽 상단까지 원을 피하는 것이 가능한가?를 묻는 문제이다.
그렇다면 이 원들이 막고 있느냐?를 판단해야 하는데, 각 벽 역시 하나의 componet라고 가정하고, 원하고 벽하고 교차가 된다면, union해주자.
최종적으로 왼쪽 벽이랑 오른쪽 벽의 parent가 같은가? 위아래 벽의 parent가 같은가? 왼쪽벽과 아래 벽의 parent가 같으냐?로 벽의 막힘유무를 체크해주었다.
추가 반례로 애초에 원이 (0,0) (n,m)을 가리면 그냥 안되는 case이다. 이거 떄문에 맞왜틀을 엄청많이하였다...
이 링크에 해설에 있는 figure가 좀 더 명확할 것 같다.
| 11월 3째주 PS정리 (0) | 2024.11.11 |
|---|---|
| 11월 2째주 PS 정리 (0) | 2024.11.04 |
| 10월 4째주 PS정리 (0) | 2024.10.22 |
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
#dsu
곧이 곧대로 구현한다면 시간초과가 난다.
관찰을 해보면, 역순으로 전개했을 때 찍힌 도장이 남아있을 것이다.
이것을 이용해 모든 칸이 한 번만 봐지게 DSU로 구현하였다.
몇일동안 생각만 한 문제였는데 https://ps.mjstudio.net/boj-14632여길 참고하였다...
#flow
grid 내에서 flow하는 문제로 생각해볼 수 있다.
이분 그래프를 source -> 가로 -> 세로 -> sink로 생각해봤을때, 장애물로 막혀있는 구간의 간선을 제거해주고 이분매칭을 돌렸을 때 최대 매칭 수는 필요한 자원의 수와 같다.
#math
x,y,z를 각각 구해보자.
(3,3,3)인 case를 생각해본다면 x,y,z는 /3한값의 곱이 된다.
(2,3,6)인 case를 생각해본다면, x//=2 , y//=3, z //=6한 값의 곱이 된다.
(2,4,4)인 case를 생각해본다면, x//=2, y//=4, z//=4한 값의 곱이 된다.
그왼 모두 -1 이다.
마라톤에 나와서 풀었는데, 많조분 너무싫다..
| 11월 2째주 PS 정리 (0) | 2024.11.04 |
|---|---|
| 11월 1째주 PS정리 (0) | 2024.10.28 |
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
| 10월 1째주 PS 정리 (0) | 2024.09.30 |
