[코딩 일지] 2024. Jan ~ Feb 중간정산

요즘 코딩을 하면서 다양한 난이도의 문제들을 풀어보았습니다. 

대회 기간이기도 하고 대회 개최도 해보고 이것저것 할 게 많다보니 공부는 강제되었습니다. 

뭐 그래도 제 의지대로 공부한 거고 새로운 문제나 알고리즘 유형을 공부하는 것도 즐겁다 느껴서 거의 즐겁게 문제를 풀었습니다. 

 

 

앞으로 일정 주기별로 코딩 일지를 만들어서 복습용으로 써야겠다 생각이 들었어요.

고난이도 문제를 풀 때 주로 새로운 알고리즘을 공부한 경우도 많고, 제가 특히 약한 유형인 그리디나 애드 혹 같은 문제들은 정해에 접근하는 방식이 어려웠기 때문에 이런 문제들을 풀면서 처음에 어떤 식으로 접근하였고 이후에 어떤 식으로 AC를 받게 되었는지 기록함으로써 이후에 다른 비슷한 문제들을 만났을 땐 더 짧은 시간 안에 풀 수 있도록 공부하려고 합니다. 

 

 

[코딩 일지] 포스트는 다른 분들께 문제를 해설하는 목적이 아닌 제 스스로의 복습 용도로 적는 글이라 가독성이 떨어지고 정말 비효율적으로 문제를 접근하거나 풀었을 수 있으니 읽으실 때 주의 바랍니다. 

 

---

 

1766번 문제집

 

기본적인 위상정렬 문제. 방향 비순환 그래프에서 위상정렬을 구현하기만 하면 된다. 

다만 주의 해야할 점이 있는데, 

         1. N개의 문제는 모두 풀어야 한다.
         2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
         3. 가능하면 쉬운 문제부터 풀어야 한다.

 

여기서 3번 조건으로 인해 그냥 큐를 이용한 위상정렬을 이용해 구현할 경우 틀리게 된다. 

예제로 주어진 4 2와 3 1을 보자. 일반적인 큐를 이용한 위상정렬을 사용할 경우, 진입 차수가 우선적인 3과 4가 먼저 출력되어 최종적으로 3 4 1 2가 나오게 될 것이다. 하지만 주어진 입력에서 4는 2보다 먼저나와야한다고만 되어있지 4가 1보다도 앞에 나와있어야한다는 조건은 없다. 3번 조건으로 인해 더 쉬운 문제 (더 작은 숫자)가 먼저 출력되어야하기 때문에 답은 3 1 4 2가 된다. 그래서 이 문제는 큐가 아니라 우선순위 큐를 이용하여 위상 정렬을 구현하면 맞을 수 있다. 

 

 

 

28433번 게리맨더링

 

엄청나게 뇌절했던 문제이다. 일단 뇌절했던 접근법까지 다 기록하겠다. 

<첫 접근법>

"YES"에 접근할 수 있는 2가지 방법
1. 연속한 음수들을 하나로 묶는다          
2. 연속한 양수와 음수를 묶어서 양수가 되는 경우가 있다면 묶는다

일단 1번 방법만 고려해보자. 연속한 음수끼리 묶어주는 건 자명하게 음수의 갯수를 줄이기 때문.
음수끼리 묶고 나면 더 이상 음수끼리 연속하여 붙어있는 일이 없음

1번을 실행하고 나면 3가지 경우 중 하나가 나올거임 (양=양수의 갯수, 음=음수의 갯수라고 하였을 때)
1. 양>음 (이러면 정답이 YES)
2. 양<음 (이러면 정답이 현재로썬 NO)      
3. 양=음 (이러면 정답이 현재로썬 NO) 

물론 "1. 연속한 음수들을 하나로 묶는다"를 실행한 후 양<=음이 되었다고 해서 바로 NO라고 확정지을 수는 없음.
양수와 음수를 묶어서 양수를 만들 수 있는 경우가 존재한다면 음수의 갯수를 더 줄이는 게 가능하기 때문. 
양<=음 케이스가 걸리면 양수+음수를 묶는 경우를 고려하기 시작해야함. 
위에서 말했 듯, 연속한 음수들끼리 묶어놨기 때문에 더 이상 음수끼리 연속해서 붙어있을 일은 없음. 


<첫 번째 시도 WA>
a라는 배열을 linear search를 한다 치자. 왼쪽에서 오른쪽으로 하나씩 탐색을 시작하겠지.
0 <= n < a.size 라고 하고, 모든 n에 대하여 탐색을 돌려볼 때,
a[n]+a[n+1] >=0 이면 a[n+1]에는 a[n]을 더하고, a[n]을 0으로 초기화함 (즉, 둘의 값을 한 쪽에다가 합친다는 소리)
(대신 이때 a[n], a[n+1] 둘 중 하나는 음수여야함. 양수들끼리 merge하면 손해임)
 

<두 번째 시도 WA>
내 접근 방식에서 찾은 반례:

4
2 -2 3 -4

위의 접근대로면 0 3 -4 가 되어 NO가 답이 되지만
가운데의 -2와 3을 묶으면 2 1 -4 가 되어 YES라는 정답이 도출될 수 있음
위의 접근에서 잘못되었던 건 a[n]+a[n+1] >=0
여기서 >=0이 되면 안됨. 
이 문제에서 YES라는 답에 도달하기 위해선 1) 음수의 갯수를 줄이거나, 2) 양수의 갯수를 늘리거나 인데
음수 한 개와 양수 한 개를 합쳐서 0을 만들 경우, 음수의 갯수와 양수의 갯수 둘 다 한 개씩 줄어들기 때문에 결과론적으로 안 묶을 때와 달라진 게 없음.

그래서 >0으로 수정하고 다시 시도함. 

<세 번째 시도 WA>
수정한 풀이에서 찾은 또다른 반례:

이상하게 0만 주어지면 터졌음
0 예외처리해서 이거 고침


<네 번째 시도 WA>
반례가 진짜 뭘까
다시 태초마을로 돌아와서 다시 그리디하게 생각해보자
수열의 크기는 짝수개거나 홀수개임
"연속한 음수들끼리 묶어놨기 때문에 더 이상 음수끼리 연속해서 붙어있을 일은 없음."
이 수열에서 음수의 개수는 최대 n/2+1

-1 2 -3 4 -5 -6 -7 3 -2 4 -1 

리스트에 들어있는 원소의 갯수가 짝수개면, 무조건 양수>=음수 

양수=음수+1
양수=음수   ---> "양수+음수=양수"가 되는 케이스 1개라도 존재한다면 YES
양수=음수-1 ---> "양수+음수=양수"가 되는 케이스 2개만라도 존재한다면 YES



양수=음수-1

리스트 안의 모든 원소의 갯수는 홀수개
그리고 순서는
음 양 음 양 음 양.... 음

음 양 음 양 음 양 음

양 음 양 음 양 음
음 양 음 양 음 양 

음 양 양 음 양 음


여기서 한 번 더 그리디하게 접근을 해보자
양수를 기준으로 생각하냐
음수를 기준으로 생각하냐

양수 기준이 맞음
양수+음수의 짝

2짝을 찾아야함

음수와 짝을 지어줄
본인+본인 옆의 음수를 더했을 때 양수가 나오는
양수 2개가 필요함
모든 양수에 대하여 자신의 왼쪽값과 오른쪽 값을 확인해서 만약에 본인이 짝을 만들 수 있다 << 2명 
만약에 본인 왼쪽과 오른쪽의 값을 합쳤을 때의 절댓값보다 본인의 절댓값이 큰 양수가 존재한다면 (a[n-1]+a[n+1] < a[n]) 바로 끝

다만 이거 생각보다 구현이 빡셌다. 

 

 

<마지막 시도 (AC)> 

결국 싹 갈아엎었다. 간단하게 생각해보자. 

- 양수를 최대한으로 한다.

- 음수를 최소한으로 한다.

 

만약 현재가 양수면 무조건 분리시키는게 이득이다 << 이건 자명함.

만약 현재가 음수면, 다음 수가 현재 자신보다 절댓값이 작은 양수인 경우를 제외하고는 더해주는 게 나음. 

음수+음수=음수 (음수 갯수는 1개 줄어듦)

음수+양수=양수 (음수 양수 둘 다 1개씩 줄어들기 때문에 둘의 갯수 차이 변화는 없음)

음수+양수=음수 (양수의 갯수만 줄어들기 때문에 하면 안됨) 

 

 

 

17400번 깃발춤 

 

x - y = x + (-y) 인 것을 생각하면 문제를 쉽게 접근할 수 있다. 

 

세그트리 2개 만들어서 하나는 홀수번째를 모두 +, 짝수번째를 -로, 다른 하나는 홀수번째를 모두 -, 짝수번째를 +로 하여 쿼리를 진행할 때 start 인덱스가 짝/홀이냐에 따라 각각의 세그트리를 경우에 맞게 사용하면 맞을 수 있다. 

 

 

 

27893번 특별한 드롭킥 

 

8개월 전에 반례를 못 찾아서 버렸다가 다시 시도해보았다. 

 

기본적인 아이디어는 2개의 벽이 있을 때 그 사이의 빈 공간이 적은 순서부터 벽을 세워나가면 된다. 

이 부분은 우선순위 큐를 이용하여 처리하였다. 

다만 (X를 추가 안하는 게 더 이득인 경우 / 혹은 모든 구간을 X로 채울 수 있는 경우)의 반례들이 존재하기 때문에 얘네를 예외 처리해줘야만 한다. 

 

 

 

10854번 Divisions

 

1달 전에 폴라드 로 알고리즘을 공부해서 4149번을 시도했었다. 소인수분해를 이용하면 소수의 갯수를 쉽게 구할 수 있고, 이 문제도 4149번처럼 주어지는 숫자의 범위가 굉장히 크기 때문에 폴라드 로 알고리즘을 이용하여 소인수분해를 진행했다. 아이디어 자체는 간단한데 폴라드 로를 이해하는 것과 구현하는 것이 쉽지 않아서 티어가 높게 매겨진 것으로 보인다.

 

어떤 수 N의 약수의 갯수는 N을 소인수분해 하였을 때 나오는 모든 소인수들의 지수+1의 곱들이다. 예를 들어서 N=20일 경우, N을 소인수분해하면 2^2 * 5^1이 된다. 이때 N의 소인수들은 2와 5고, 각각의 지수는 2와 1이기 때문에 20의 약수는 (2+1)*(1+1)인 6개가 된다. 실제로 20의 약수는 (1,2,4,5,10,20)으로 6개이다. 폴라드 로 알고리즘을 복습하려고 이 문제를 시도했었지만 아직도 맨땅에 폴라드 로를 구현하는 건 어렵다고 느껴서 4149번때 사용했던 폴라드 로 코드를 재사용하였다. 폴라드 로는 틈틈히 지속적으로 복습해야겠다.  

 

 

 

23400번 No Luck

 

처음에 배열 Arr에 N개의 숫자들이 들어가있다하자. 각 쿼리마다 숫자가 3개씩 질 것이다: a,p,f
만약 Arr[a]가 p 이상이라면 그냥 0을 출력하고, Arr[a]가 p를 미만이라면 Arr [a+1]부터 Arr [a+f]까지 탐색해서 p 이상인 경우를 세서 출력하면 된다. 

머지 소트 트리를 이용하면 쉽게 구할 수 있다. 각 구간별로 들어가있는 숫자들을 정렬시켜준 뒤,  p에 대하여 구간 별로 lower_bound를 사용했을 때의 값을 해당 구간의 트리 크기에서 빼주면 된다. 

tree[node].size()-(lower_bound(tree[node].begin(),tree[node].end(),val)-tree[node].begin())

(해당 구간의 크기 - 해당 구간에 p에 대한 lower_bound 적용했을 때의 값)을 하면 자연스럽게 p 미만의 값들이 걸러지기 때문이다.