20.07.02 | Notion

Number of Ways (부분합)

배열 세 부분을 나눠서 각 부분합이 동일하도록 나눠라 → 전체합의 1/3씩 있게 나누면 된다.
Twins (그리디)

최소 개수의 동전으로 가장 큰 값을 가질수 있는가 → 큰 값의 동전부터 가져가면 된다.
Painting Fence (그리디)

가로로 칠할수 있는 부분은 모두 가로로 칠해야 한다. 모든 판을 세로로 칠하는 것이 답이 아닌 이상, 가장 아래는 가로로 칠해야한다.→ 1) 전체를 세로로 칠하는 답 체크, 2) 키가 가장 작은 부분 펜스까지 가로로 칠한다.
Boredom (dp)

직전 수까지의 최적의 답에서 현재 수를 고르는 경우/ 고르지 않는 경우
Approximating a Constant Range
Linova and Kingdom (트리)

루트까지 거리 - 자신 아래쪽 도시 개수를 모든 노드에서 구해서 큰 값부터 순서대로 구한다.
Maximum White Subtree (어려운 트리)

v를 포함한 서브트리 중, 흰색이 가장 많이 포함된 서브트리를 구해라

양수인 노드는 무조건 포함 + 자기 노드를 포함하면 자기 노드를 포함한 가장 좋은 서브 트리
Woodcutters (기본적인 DP)

서있는 나무와 쓰러진 나무가 겹치면 안된다.(끝점도 겹치면 안됨)

각각의 나무에서 왼쪽으로 쓰러질 경우, 서있는 경우, 오른쪽으로 쓰러질 경우에서 최선의 선택을 고른다.
LIS
Circular RMQ (Lazy update) n^2 → nlogn에 해결 가능
A simple Task (문자열 sort)

index tree를 26개 만들고 lazy update 사용. 내 아래쪽에 a 개수가 얼마나 있는지
Ice Skating (graph, DFS)
Dijkstra

실제 path를 찾는 다익스트라

Longest Increasing Subsequence (LIS)

값이 증가하는 순으로 선택할 수 있는 가장 긴 부분 배열을 고르는 문제
1. n^2의 방법
  1. 배열의 각 인덱스마다 가장 길게 만들 수 있는 부분 배열의 길이를 저장한다.
  2. 배열의 각 인덱스마다 이전 인덱스의 값(value)을 확인한다.
  3. 이전 인덱스들 중 가장 긴 부분 배열을 만드는 인덱스의 부분 배열 길이를 가져와서 1을 더해서 저장한다.
2. nlogn의 방법
  
  같은 부분배열 길이를 가졌을 때, 배열의 인덱스가 커질수록 배열의 값(value)이 작아진다. → 모든 인덱스의 len값을 기억하는게 아니라 가장 작은 값의 len만 기억하는 것이 효율적
  - 성질
  1. 같은 len값을 가지면 인덱스 값이 커질수록 value값은 커진다.
  2. len 값이 커질수록 인덱스 값이 커질수록 value값은 커짐
  3. 1,2번에 의해 값이 커질수록 len 값도 점점 커진다.
DP와 재귀 문제의 차이
1. DP는 계속해서 고려해야할 문제가 생기지만 겹치는 부분이 많아서 결국은 조금만 고려해도 될 때
2. 재귀는 같은 문제를 계속 고려해야할 때

문자열에서의 숫자 처리

string s; // 처리할 문자열
string tmp; 
    for(int i=1; i<s.size()-1;i++){
        if(s[i]-'0'>=0 && s[i]-'0'<=9 ){
            tmp+=s[i]; // 숫자 한자리씩 처리
        }else{
            if(tmp.length()){
                stoi(tmp); // 문자열을 숫자로 바꿈
                tmp.clear();    
            }
        }
    }