#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 |
#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 |
#dp
bfs나 dfs로 관리해준다면 visited의 존재가 없기 때문에 8^50번의 탐색이 필요하다. 따라서 dp를 이용해 중복연산을 제거해보자.
dp[i][j] = 현재 i,j에 말이 있을 확률이라고 가정해보자.
그렇다면, 처음 위치 dp[x][y]는 1이 될 것이다. 매 이동횟수 k를 진행하면서 갈 수 있는 경우의수는 8가지 이기 때문에
dp[next_knight_move][] += dp[x][y] * 0.125될 것이다. 이 과정을 위치에 벗어나지 않는한 계속 해주자.
dp보단 브루트포스에 가깝다... 시간복잡도 O(n^4)
#greedy
탑승 정거장 기준으로 정렬을 해보자.
#tsp #graph
대각선으로 BFS을 하여 adjust matrix를 만들 수 있다.
그런 다음, 접근을 못하는 정점이 있으면 불가능한 걸 알 수 있다.
그 다음 tsp를 활용 해 최단 거리를 구할 수 있다.
난이도에 비해 어렵게 풀었는데 n의 범위가 작아서 10!으로 permutation을 만들면 brute force으로도 풀리는 듯 하다.
#dsu
평범한 dsu 문제
adjust matrix를 순회하면서 i,j가 1인 경우, parent를 find 했을 때, parent가 다르다면 union을 해준 다음, +=1 해주면 된다.
그것이 최소의 간선으로 전체를 순회할 수 있는 방법 중 하나이다.
#sort, #hash
정렬한 다음, dictonary와 같은 hash set으로 처음 등장한 index를 관리해주면 된다.
풀고 난 다음 태그를 봤는데 이분탐색이 있어 이방법도 있겠구나 싶었다.
http://boj.kr/da8cf1e839bf4e7f9a53ebaa884725df
#greedy #prefix_sum
관찰 해보았을 때, 우체국은 사람이 있는 장소에 설치하는게 가장 최적일 것이다.
그리고 Greedy하게 푸는 방법을 생각해보았을 때 현재 index기준 사람이 전체 사람의 50%가 넘어가는 시점에 설치해야 한다. (이 과정이 증명하기 힘들지만, 가장 최적의 방법이다.) 이 과정을 누적합을 이용해서 구현해주자.
추가로 input으로 들어오는 우체국의 위치가 정렬이 되어 있지 않은듯하다. sort를 해주어야 함.
이 방법외에도 여러가지 풀이방법이 존재하는 듯하다.
#graph
트리의 지름을 구하는 문제와 유사하다.
다만, 모든 정점이 하나의 트리로 구성되어 있지 않기 때문에 bfs로 탐색 할 수 있는 트리들의 지름의 합을 구해주어야 한다.
트리의 지름을 구하는 방법은 임의의 정점 w를 잡고 가장 길이가 먼 x를 잡은 다음, x에서 가장 먼 정점 y를 잡는다면, x->w->y는 트리의 지름이 된다.
#dsu
union을 했을 때, 그 그룹 내에 모든 power의 곱의 합을 쿼리로 출력하는 문제
union할 때 power라는 새로운 리스트를 만들어 parent를 관리함과 동시에 power을 update해주자.
쿼리가 들어오면 매 쿼리마다 그 그룹을 union하고, power을 출력해주면 되는 문제.
#math
2^n개가 홀수개 있다는 거는, 해당 비트위치의 연산을 xor 했을때 1인 경우를 의미할 것이다.
그리고 최대 1개를 지운 다는 것은 전체 xor 한 값에 한번 더 해당 값을 xor연산 한것과 동치 일 것이다.
그렇게 해준 다음, 위 2 case의 최댓값을 출력시켜주자.
| 11월 1째주 PS정리 (0) | 2024.10.28 |
|---|---|
| 10월 4째주 PS정리 (0) | 2024.10.22 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
| 10월 1째주 PS 정리 (0) | 2024.09.30 |
| 9월 4째주 PS정리 (2) | 2024.09.24 |
#bruteforce, #implementation
N이 매우 작기 때문에 매번 i or x한 값을 리스트에 넣은 다음, MEX를 구해주면 된다.
MEX를 구하는 방법은 여러가지 있겠지만 나는 i or x한값을 정렬했을때, 인덱스와 값이 다른 시점을 mex로 구현하였다.
XOR만 나오면 항상 정수론적인 생각을 먼저하게 된다...
#greedy #math
모든 자리에 퀸을 넣는 것이 가장 최적의 경우이다.
그렇다면 가로방향의 공격 쌍수, 세로방향의 공격 쌍 수 대각선 방향의 공격쌍수 이렇게 3가지로 나누어서 생각을 해보았을때, 점화식을 도출할 수 있다.
문제에비해 난이도가 저평가된것 같다..
http://boj.kr/abb650e031d34f4fa24702fc4788f6e7
#graph #scc
저번주에 푼다고 하고 못푼 문제다.
SCC으로 묶을수 있는 간선들은 모두 동치가 될 수 있다고 설명할 수 있다.
그렇기에 SCC단위를 정점으로 간소화 한다음, 이 정점 집합들을 하나의 SCC로 만들어야 하는 문제로 바꿀 수 있는데,
그렇다면 각 node의 indegree와 outdegree가 모두 1이상이 되어야 하기 때문에 max(indegree == 0, outdegree == 0)인 수를 찾으면 된다.
SCC 구현 코드를 코사라주 알고리즘을 사용했는데, 아무래도 똑같은 그래프를 2개 만들다 보니 MLE가 자주 발생한다. 그렇기 때문에 비교적 느린 python3이나, 타잔 알고리즘으로 SCC를 구현해야 한다.
타잔알고리즘과 SCC를 정점으로 치환하는 방법을 배운 문제
#greedy #stack
일단 m번 무조건 지워야 하기 때문에 최대 자릿수는 n-m자리일 것이다.
그렇다면 무조건 앞에 수를 가장 큰 수로 두어야 할 것이고, 스택에 하나씩 넣으면서 앞에 자리수가 뒤에자리수보다 작다면 계속 그 작업을 수행해주어야 할 것이다.
추가 반례로 모두 다 같은자리인경우 m번 연산을 안할경우가 있는데, 이 점을 따로 예외 처리해주자.
#dfs #greedy
연산 내용이 주어진 트리의 부분 그래프의 가중치를 1 늘리는 과정이기 때문에 현재 노드를 기준으로 본다면, 현재 노드의 부모노드의 목표 weight보다 작으면 부모노드의 연산으로 수행할 수 있다.
그러기 때문에 대충 1번 노드를 root node으로 잡고 정답은 root node의 weight + sigma 2~n : max(node weight - parent node weight, 0)으로 정의할 수 있다.
dfs으로 각 노드의 부모노드와 목표 가중치를 비교하자
#kmp #sweeping
KMP알고리즘을 수행하면, 원본 문자열에서 부분문자열이 몇개 있는지, 어디에 있는지 모두 구할 수 있을 것이다. 그렇다면 투 포일터를 활용해 l~r 범위 내에 모든 부분문자열이 있느냐?를 체크할 수 있다. 매번 체크를 해주면서 최소 구간을 찾자.
대충 시간복잡도를 O(N+M+2N) 정도로... 선형시간내에 해결할 수 있을 것이다.
#implementation, #math
m을 3진수로 나눌 때 bit가 2인 경우, 왼편, 그 외인경우 오른편에 두어 비트연산을 했을 때 그 수가 나올 수 있게 구현하면 된다.
#tsp
각 좌표간의 거리를 n^2으로 구해 distance를 구한 다음, 그것을 활용 해 외판원순회를 해주면 된다.
Bitonic Tour라는 좌표상의 외판원순회 알고리즘이 있던데, 이 문제인줄 알았는데, 알고보니 더 쉽게 해결할 수 있었다.
Bitonic Tour 공부해보면 좋을듯. .
#bruteforce
그리디하게 접근해볼까 하다가 같은 가장 사전순 작은 문자열 일때, 얼마나 더 길게 나눌것인가 생각을 좀 해보았는데, n이 매우작기 때문에 n^3으로 모든 문자열조합을 만드는 방식으로 풀 수 있다.
#bruteforce
1251과 동일
#stack #implementation
스택을 사용해 구현해주면 된다. 다만 신경써줘야할 부분은 태그 내에 공백이 있는 case를 예외처리 해주면 쉽게 풀린다.
| 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 |