24년 8월

240817

• 백준1562

int& ret = dp[a][b][c];

Top-down DP 재귀함수에서 참조자 표시& 를 빠트렸더니 시간초과가 났다. 까먹지말자!!

• 백준14444

  부분 문자열들의 팰린드롬을 O(n) 에 탐색하는 Manacher’s algorithm에 대해 알아보자!
  (알고리즘을 검색해서 이미지를 하나 열어놓고 읽자)

  1. 팰린드롬은 중간의 문자를 기준으로 양 옆이 대칭을 이룬다 aabaa roddor
     • A[i] : i중심일때 반지름의 최대 길이
     • R : j<i 인 모든 j대해 max(j+A[j])
     • p : R을 만드는 index j
       

  2. 0~n-1 을 탐색하며 A[i]를 채우는데, 이 때 $i<=R$ 이면 이번에 우리가 살펴볼 $i$ 가
     이전에 등장한 팰린드롬의 반지름 속에 속해있다는 것이다
     

  3. 그럼 p를 기준으로 반대편에 있는 $i^{‘}$ 을 살펴보고 싶어지는데 ,
     $i^{‘}$ 부터 왼쪽 반지름 끝까지 , $i$ 부터 오른쪽 반지름 끝(R) 까지 는 당연히 팰린드롬이니까 같다.
     

  4. 따라서 $min(R-i,A[i^{‘}])$ 의 반지름을 $i$는 먼저 확정짓고 갈 수 있다는 것 이다.
     

  5. 짝수 팰린드롬은 숫자 사이사이에 더미 문자를 넣어서 찾을 수 있다.’a#b#c#d#d#c#b#a’

  6. 시간복잡도

     • A[i] == A[2*p-i] 인 경우, i+A[i]<R 인경우 내부 반복문을 돌지 않는다
     • A[i] == R-i , A[i]==0 인 경우, i+A[i]>R 임을 의미하므로, R값을 증가시키는데, R<n 이고 감소하지 않으므로 , armotizedO(n) 에 동작한다

  7. 구현

     int a[200004];
          
     int main(void) { 
         fastio
          
         string s; cin>>s;
         string str;
         for(int i=0;i<s.size();i++) {
             str += s[i];
             str += '#';
         }
         int len = str.size();
         int p = 0; int r = 0;
         for(int i=0;i<len;i++) {
             if(i<=r) {a[i] = min(r-i,a[2*p-i]);}
          
             for(int j=a[i];j<len;j++) {
                 if(i-j<0 || i+j>=len || str[i+j]!=str[i-j]) break;
                 a[i] = j;
             }
             if(i+a[i]>r) {r=i+a[i]; p=i;}
         }
         int ans = 0;
         for(int i=0;i<len;i++) {
             if(i%2==1) ans = max(ans,((a[i]+1)/2)*2);
             else ans = max(ans,1+(a[i]/2)*2);
         }
         cout<<ans;
     }
     

     문자열에 더미 문자를 바로 추가해주면 i가 홀수 일때는 #이 중앙에 있고 반지름의 모양은
     a#a# , a#a 이므로 $(a[i]+1)/2)\times2$ ,
     i가 짝수일때는 숫자가 중앙이고 반지름은 #a#a , #a#모양 이므로
     $1+(a[i]/2)\times2$ 처리 해주었다.

나중에 회문트리 랑 LCP 배열이 무엇인지 개념만 찾아보고 다른 문제를 더 풀어보자!

240825

이진 검색트리에 대해 공부했다.

이진트리 : 각 노드가 왼쪽, 오른쪽 최대 두개의 자식만 가질 수 있는 트리

typedef struct _node{
    int data;
    struct _node *left, *right;
}Node;

k노드의 왼쪽자식은 2k, 오른쪽 자식은 2k+1 으로 배열을 이용해 구현을 할 수도 있다.

이진 검색 트리

이진 탐색에서 아이디어를 가져와서 만든 트리.
각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값을 가진 노드가 들어가고
오른쪽 서브트리에는 해당 노드보다 큰 값을 가진 노드들이 들어간다.

왜 정렬된 배열을 안쓰고 이진 검색 트리를 사용하는데? → 집합에 원소를 추가,삭제 연산이 정렬된 배열은 $O(n)$ 이진 트리는 $O(log n)$

[백준13325 이진 트리]https://www.acmicpc.net/problem/13325

루트부터 모든 리프까지의 거리가 같도록 = 가장 긴 경로 길이에 맞춰서
→ 각 노드부터 출발해서 리프까지 가는 최대 길이를 dp를 이용해 저장한다
→ $a[i] < dp[i/2]-dp[i]$ 이면 $a[i] = dp[i/2]-dp[i]$ 으로 변경해준다.

[백준18240 이진 탐색 트리 복원하기]https://www.acmicpc.net/problem/18240

트리의 모양이 정해지고 나면 , 노드값은 중위순회를 하면서 차례로 채울 수 있다.
각 깊이에서 노드는 왼쪽부터 채워진다고 하면, 간단히 각 깊이의 노드 개수만 기억하면 트리를 구성할 수 있다.

[백준 17255 N으로 만들기]https://www.acmicpc.net/problem/17255

1. n이 천만이하 이므로, 모든경우를 살펴보는게 2^10 이하로 충분하겠다.
2. 같은 경우는 모든경로에서 등장한 숫자가 같아야 하므로 등장한 모든 문자열을 포함하는 문자열을 set에 넣으면 모든 경우의수를 셀 수 있겠다. 1→12→123 이면 112123

• 이진 검색트리은 대부분 set,map 의 STL을 통해 이용된다. 직접 구현하기에는 균형잡힌 이진검색트리가 너무 복잡하기 때문이다.
• 삽입 검색 삭제 ,lower_bound 등의 기능을 $O(log N)$ 에 얻을 수 있다.

240827

• 세그트리에서 루트노드의 인덱스가 1이라면 , $a[0]$이 들어가기 시작하는 노드는 몇 번일까?

  justicehui 2d세그 보고 정리 제대로 하기 이거 꽤 중요한 관찰 필요한듯!!!!!