aqusiz / ps_practice Goto Github PK

2110 공유기 설치
2110 코드
참고한 풀이

함수 set_router: 최소 거리를 받아, 설치 가능한 총 공유기 개수를 반환하는 함수
최소거리에 대한 이진 탐색으로 설치 가능한 공유기 개수가 C를 넘기는지 넘기지 못하는지에 대해 판별

이때 upper bound 탐색

boj 단계별로 풀어보기 12. 집합과 맵 완료

시간복잡도와 실제 시행시간

대략 10^8(1억)개의 O(n) 알고리즘 시행시간을 1초로 잡고 계산
O(n^2)의 알고리즘은 1만개 정도의 케이스를 1초에 계산 가능

python set의 시간복잡도

python의 set 자료형은 hash table로 구현되어있다.
즉, in 을 이용한 원소 찾기를 O(1)에 가능

python 빠른 입력

import sys
sys.stdin.readline()

이때, \n까지 함께 읽어들이기 때문에 필요없다면 rstrip()으로 벗겨낼 수 있다.

2252 줄 세우기
2252 DFS 코드

위상정렬이란

사이클이 없는 방향 그래프(DAG)에서 vertex 간의 순서를 선형으로 정렬하는 것

DFS 구현

인접 리스트 사용 시 $O(V+E)$, 인접 배열 사용 시 $O(V^2)$

1. 모든 정점을 순회하면서 방문하지 않은 vertex에 대해 DFS 수행
2. 이때 DFS는
   1. 해당 vertex 방문 체크
   2. 해당 vertex와 연결된, 방문하지 않은 vertex들에 대해 재귀적으로 DFS
   3. 리스트의 front에 해당 vertex 삽입 (가장 먼저 끝난 vertex가 가장 뒤로 오도록)

BFS 구현

in_degree 배열을 사용(해당 vertex로 들어오는 edge의 수)
인접 리스트 사용 시 $O(V+E)$, 인접 배열 사용 시 $O(V^2)$

1. 모든 vertex들의 in_degree 설정
2. in_degree가 0인 vertex들을 방문 표시하고 queue에 삽입
3. queue가 빌 때까지
   1. queue의 맨 앞 vertex를 dequeue하고, 리스트에 append
   2. 해당 vertex와 연결되어 있는, 방문하지 않은 vertex들을 방문표시하고, in_degree를 1 감소시킨 다음 enqueue

1753 최단경로
1753 코드

Dijkstra algorithm 동작 과정

1. 출발 노드 설정
2. 출발 노드 기준으로 각 노드의 최소 비용 저장
3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 -> 우선순위 큐를 이용해 비용 절감
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신(relaxation)
5. 3~4를 반복

2589 보물섬
2589 코드

결국 모든 지점에서 bfs로 가능한 경로를 확인해야 함
1회 bfs -> $O(HW)$
각 tile마다 실행하므로 $O(HW * HW) = O(H^2W^2)$

시간 초과가 발생한 이유

1. python list를 활용한 큐가 너무 느려서
   collections 모듈의 deque을 사용(popleft, append에 $O(1)$, 대신 random access에 $O(N)$ )

from collections import deque

q = deque()
q.append()
q.popleft()

2. 중복 방문이 너무 많아서
   visit 체크로 중복 제거

while q:
        y, x, dist = q.popleft()
        if visited[y][x]:
            continue
        
        visited[y][x] = True
        ....

option) 가능한 최대 거리는 결국 맨 왼쪽 위 -> 맨 오른쪽 아래 = H + W - 2
최대 거리 도달 시 즉시 종료하도록 최적화 가능 (ex: 바다 없이 모든 타일이 육지인 경우)

1600 말이 되고픈 원숭이
1600 코드

k가 몇이냐에 따라 방문 가능한 위치의 상태가 계속 바뀌기 때문에 단순한 2차원 visit 배열로는 해결 불가
따라서 3차원 visit 배열 사용
visited[y][x] -> visited[k][y][x]

2042 구간 합 구하기
2042 코드
풀이 참조

2357 최솟값과 최댓값
2357 코드

세그먼트 트리란?

정수 배열의 구간 합을 구하는 경우, 누적합 배열을 활용하면 $O(1)$ 시간 안에 구간 합을 구할 수 있지만 값을 업데이트 하기 위해 $O(n)$ 시간이 걸린다.
이때 구간 별 누적합을 저장하는 세그먼트 트리를 활용하면 구간 합 구하기와 값 업데이트를 모두 $O(\log n)$ 시간 안에 수행할 수 있다.

• 세그먼트 트리는 리프 노드가 아닌 모든 노드들이 2개의 자식을 갖는 Full Binary Tree이고, 배열로 구현 가능하다.
  • 왼쪽 자식은 index * 2, 오른쪽 자식은 index * 2 + 1
• 세그먼트 트리의 모든 리프 노드들은 배열의 각 한 자리의 숫자를 의미한다. 루트 노드(index 1 사용)는 index 0 ~ index N-1 까지 모든 수의 합을 저장한다.
  • 왼쪽 자식은 [Left, (Left + Right) / 2]의 구간 합, 오른쪽 자식은 [(Left + Right) / 2 + 1, Right] 의 구간 합을 나타낸다.
• 만약 N이 2의 제곱꼴이라면, 세그먼트 트리는 Perfect Binary Tree의 꼴이 된다.

세그먼트 트리 만들기

간단하게는 원본 배열의 크기의 4배를 할당한다.
- 원본 배열의 크기가 $N$이라는 것은, 리프 노드의 갯수가 $N$개라는 것이다. Full Binary Tree의 특성 상, 리프 노드가 $N$개라면 리프 노드가 아닌 노드의 갯수는 $N-1$개이고, 총 $2N-1$개의 노드가 사용되게 된다.
- 세그먼트 트리의 높이 $H = \lceil\log N\rceil$이 되고, Perfect Binary Tree의 노드의 갯수 $2^{H+1} - 1$이 필요한 배열의 크기가 된다.

void init(vector<lli>& seg, vector<lli>& arr, int pos, int l, int r) {
    // left == right인 경우는 리프 노드이므로 값을 그대로 저장한다.
    if(l == r) {
        seg[pos] = arr[l];
    } else {    // 리프 노드가 아닌 경우 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 초기화한 후 양쪽 값을 더해준다.
        init(seg, arr, pos*2, l, (l+r)/2);
        init(seg, arr, pos*2 + 1, (l+r)/2 + 1, r);
        seg[pos] = seg[pos*2] + seg[pos*2 + 1];
    }
}

구간 합 구하기

총 4가지 경우로 조건을 분기할 수 있다. ([left, right]은 구간 합을 구하길 원하는 구간, [start, end]는 세그먼트 트리의 현재 노드가 포함하는 구간)

1. [left, right]이 [start, end]에 전혀 포함되지 않는 경우
   • 필요 없는 구간. 0을 바로 반환한다.
2. [left, right]이 [start, end]를 완전히 포함하는 경우
   • 구해야 하는 구간을 현재 노드가 모두 포함하고 있고, 그 자식들도 마찬가지이므로 더 이상 탐색을 진행할 필요가 없다. 해당 노드의 값을 바로 반환한다.
3. [start, end]가 [left, right]을 완전히 포함하는 경우
4. 그 외 나머지
   • 왼쪽에서의 값과 오른쪽에서의 값을 재귀적으로 구한 후 더해준다.

값 업데이트하기

목표 index가 [start, end] 구간에 포함하는지 아닌지로 조건을 분기할 수 있다.

1. target idx가 [start, end] 구간에 포함되지 않는 경우
   • 더이상 할 일이 없다. 즉시 반환한다.
2. target idx가 [start, end] 구간에 포함되는 경우
   • start == end라면 리프 노드이므로, 목표 value로 바로 수정한다.
   • 리프 노드가 아니라면, 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 업데이트한 후 해당 노드를 업데이트한다.
     2-1. 원래의 값과 바꾸려는 값의 차이(diff)를 구해서 구간에 포함되는 모든 노드를 즉시 업데이트 하는 방법도 있다!

응용

구간의 합 뿐만 아니라 구간의 최소값, 최대값, XOR 등등을 모두 구할 수 있다.
ex)최소값을 구하는 경우, +로 계산되는 모든 부분을 min으로 고치면 된다.

Heap

완전 이진 트리. 모든 부모는 자신의 자식보다 작아야 한다(최소 힙. 큰 경우 최대 힙)
배열로 구현. left_child = parent * 2, right_child = parent * 2 + 1

• 데이터 삽입: 끝 자리에 삽입한 후, 부모와 비교해 조건에 성립하지 않으면 서로 자리를 바꾼다
• 데이터 삭제: 루트 노드 제거 후, 가장 끝 노드를 루트로 올린 다음, 자식들과 비교해가며 자리를 바꾼다.

최대 힙, 최대 힙 구현
최소 힙, 최소 힙 구현

어려웠던 문제: 이중 우선순위 큐
최소 힙과 최대 힙을 함께 사용
이때, 최소 힙에서 삭제되는 값들을 큰 순서대로 저장하고, 최대 힙에서 삭제되는 값들은 작은 순서대로 저장해둔다.
삭제된 값이 힙에서 발견되면 삭제 처리해준다.

단일 변수의 동적 할당

int *ptr = new int;  // 단일 변수의 동적 할당
int *ptr1 = new int(6);  // 단일 변수의 동적 할당 및 초기화
int *ptr2 = new int { 6 }; // 단일 변수의 동적 할당 및 유니온 초기화

delete ptr;

배열의 동적 할당

bool *visited = new bool[N+1];
for(int i = 1; i <= N; i++) visited[i] = false;  // 반드시 따로 초기화 해줄 것!!!
...
delete[] visited;

16235 나무 재테크
16235 코드(TLE in python 3, AC in pypy)

어린 나무부터 양분을 먹는다는 조건 때문에 heapq를 사용하였지만, 각 처리마다 정렬을 해주는 건 시간을 많이 쓴다.
deque을 사용해도 되는 이유 --> 처음 주어지는 나무는 모두 다른 위치에 1개씩 주어지기 때문에, popleft, appendleft, append를 적절히 사용하면 정렬하지 않고도 정렬된 상태를 유지할 수 있다.

1806 부분합
1806 코드

Two Pointers Algorithm

1차원 배열에서, 2개의 포인터를 움직여가며 원하는 결과를 얻는 알고리즘
Sliding Window와 비슷하지만, Sliding Window는 정해진 길이가 존재한다.

1967 트리의 지름(n=10,000)
1967 코드
1167 트리의 지름(n=100,000)
1167 코드

• 각 leaf node마다 dfs로 가장 먼 node 찾기 -> $O(N^2)$의 시간 복잡도를 가짐. c++로 해결할 수는 있으나 정해는 아니다

• 양방향 그래프로 만든 다음, bfs를 2번 사용 -> $O(N)$의 시간 복잡도

  1. root node(1번 node)로부터 가장 먼 leaf node를 탐색
  2. 해당 leaf node로부터 가장 먼 node 탐색

1987 알파벳
1987 코드

기본적으로 최대 경로를 찾는 문제이기 때문에, 평소처럼 방문 노드를 체크하는 방식의 bfs로는 풀 수 없는 케이스가 존재한다

example
3 6
HFDFFB
AJHGDH
DGAGEH    // answer = 6, bfs = 5

따라서 전역 bool 배열을 이용하여 dfs(backtracking) 방식을 사용하거나, set을 이용한 bfs를 사용한다.

2098 외판원 순회
2098 코드

아이디어

1. 완전탐색 진행 시 $N!$의 시간 복잡도를 가짐
2. $N \le 16$이므로, bitmask를 이용해 이미 지난 정점을 체크하며 동적계획법 및 dfs 사용
3. dp[a][b] = c -> 현재 a번 정점에 있고, 현재 방문상태 b에 대한 cost 최소값은 c
   3-1. ex) dp[1][0010] = 1: 현재 1번 정점에 있고, 지금까지 1번 도시만 방문한 상태일 때, cost의 최소값이 1이다.

틀린 풀이(시간 초과)

void go(int n, int mask) {
    int new_mask;
    for(int i = 0; i < N; i++) {
        if(mask & (1 << i)) continue;
        if(w[n][i] == 0) continue;

        new_mask = mask | (1 << i);
        // dp는 모두 INF로 초기화 되어 있음. 최소값 갱신 발생 시 해당 지점 재탐색
        if(dp[i][new_mask] > dp[n][mask] + w[n][i]) {
            dp[i][new_mask] = dp[n][mask] + w[n][i];
            if(new_mask != done) go(i, new_mask);
        }
    }
}
// main에서 dp[i][done] + w[i][0]을 계산하여 최소값 탐색

수정된 풀이(참조)

int go(int n, int mask) {
    // 모든 정점을 지나온 상태라면 n -> 0 weight 반환
    if(mask == done) return (w[n][0] == 0) ? INF : w[n][0];
    // 이미 탐색한 적 있는 정점이라면, 메모이제이션 값을 그대로 반환
    if(dp[n][mask] != -1) return dp[n][mask];

    int new_mask;
    dp[n][mask] = INF;
    for(int i = 0; i < N; i++) {
        if(mask & (1 << i)) continue;
        if(w[n][i] == 0) continue;

        new_mask = mask | (1 << i);
        dp[n][mask] = min(dp[n][mask], w[n][i] + go(i, new_mask));
    }

    return dp[n][mask];
}

13549 숨바꼭질 3
13539 코드
풀이

0-1 bfs란?

가중치가 0 또는 1로만 구성된 그래프에서 다익스트라 알고리즘보다 빠르게 최단 경로를 찾을 수 있는 알고리즘

• 다익스트라 알고리즘의 시간복잡도: $O(E\log E)$ or $O(E\log V)$
• 0-1 bfs의 시간복잡도: $O(V+E)$

0-1 bfs의 작동

deque을 사용하여 구현

1. 덱의 front에서 현재 노드를 pop한다
2. 연결된 인접 노드를 살펴보고, 현재 노드 비용+ 가중치 < 인접 노드 비용 이라면 비용을 갱신한다
3. 그 노드로 향하는 가중치가 0이라면 덱의 front에, 1이라면 덱의 back에 push 해준다
4. 덱에 남아 있는 게 없을 때까지 반복한다

$O(V+E)$인 이유

위 방식을 사용하면, 가중치가 1인 간선을 0번 거쳐간 노드 -> 1번 거쳐간 노드 -> ... -> n번 거쳐간 노드 순서로
비용이 적은 경로부터 탐색하기 때문에, 거쳐간 간선을 다시 거쳐가는 경우가 없으므로 $O(E)$
같은 이유로 모든 정점을 한 번씩만 거쳐가기 때문에 $O(V)$
그러므로 $O(V+E)$가 성립한다

2533 사회망 서비스(SNS)
2533 코드 1
2533 코드 2
코드 2 참고 풀이

트리: 사이클이 없는 그래프
그래프에서처럼 dp 기법 활용 가능(다익스트라 알고리즘처럼...)

dfs를 활용해 탐색하면서 서브트리에서의 답을 구한 후, 그 답을 활용해 트리의 답을 구해나가는 방식

1541 잃어버린 괄호

• cin은 iostream에 정의된 istream 클래스에 속하는 객체이다
• cin 객체의 리턴 형은 cin 객체 그 자체이지만, 조건 검사식에 위치하게 되면 Boolean으로 변환된다
• cin이 조건 검사식 위치에 속하면 Method의 특성을 띰 -> 입력이 성공할 경우 true, 실패할 경우 false 리턴

입력의 끝을 구분 짓는 방법

1. Sentinel Charactor(표지 문자): 임의의 특수 문자를 선정해 그 문자를 입력 중지 신호로 사용
2. 각 데이터형 별 데이터 처리

• char: 입력 행에 있는 첫 문자 (공백문자, 개행문자는 모두 무시하고 건너 뛴다) (cin.get() 멤버함수는 빈칸문자와 공백문자 모두 받음)
• int: 숫자가 아닌 첫 문자가 나오기 전까지
• double: 부동소수점수의 일부가 아닌 첫 문자가 나오기 전까지
• char형 배열: 빈칸 문자가 나올때까지 (cin.getline() method를 사용하는 경우, 개행문자 전까지)

cin을 이용한 입력: 버퍼를 사용하기 때문에, Enter 키를 누르기 전까지 프로그램에 전달 X

cin.get() 멤버함수를 이용한 입력 (overloading을 이용해, 0~2개의 매개변수를 가진다)

1. cin.get(): 그 다음 문자를 읽어 리턴. 객체가 아닌 문자를 리턴한다
   ch = cin.get();

• <cstdio>의 getchar(), putchar() -> <iostream>의 cin.get(), cout,put()으로 변환
• EOF가 감지되었을 때, 에서 정의한 상수 "EOF" 리턴

2. cin.get(char ch): 입력을 수행하고 cin 객체 리턴 (연속적인 입력을 가능하게 함)
   cin.get(ch1).get(ch2); // cin.get(ch1)이 cin 객체를 반환하기 때문에 get(ch2)에 적용되는 cin 객체로 다시 활용

• 문자 코드를 int형으로 리턴(getchar() 함수와 유사)

3. cin.get(char* arrName, int ArSize)

char temp[30];
cin.get(temp, 30);
while(cin && cin.get != '\n') continue;

• cin 객체는 EOF를 감지했을 때 두 개의 비트값을 (eofbit & failbit)를 1로 설정한다.
• eofbit, failbit 둘 다 가장 최근에 읽은 결과를 저장하고 있는 비트이며, 따라서 cin.eof()나 cin.fail() 검사는 언제나 읽기 시도 다음에 수행되어진다.
• cin의 Method는 EOF를 감지하면 cin 객체에서 EOF 조건을 나타내는 Flag를 설정하는데, 이 플래그가 설정되면 cin은 더 이상의 입력을 받아들이지 않는다.

cin.eof() : 는 EOF가 탐지되었을 경우 True 값을 리턴하고, 그 이외에는 False 값을 리턴한다.
cin.fail() : eofbit나 failbit 둘 중 하나라도 값이 1로 설정되어 있으면 True 값을, 그 이외에는 False 값을 리턴한다.
cin.clear() : EOF 플래그를 지우고 다시 입력이 진행될 수 있도록 허용한다. (입력 Buffer를 초기화하는 역할을 한다.)

12100 2048(Easy)
12100 코드

문제 자체는 모든 케이스를 탐색해보면 답을 구할 수 있다.(모든 케이스가 $4^5$)

vector 내에서 두 개의 원소를 병합하기

연속한 두 원소가 같을 때 하나로 병합하고 값을 2배로 늘리는 구현

void merge(vector<int>& v) {
    vector<int>::iterator cur, next;
    for(cur = v.begin(); cur != v.end();) {
        next = cur + 1;
        // next가 v.end()일 때의 예외처리 필수
        if(next != v.end() && *cur == *next) {
            cur = v.erase(cur);    // erase(vector<T>::iterator pos)는 해당 pos를 지운 뒤, 그 다음 iterator를 반환
            *cur *= 2;
        }
        cur++;
    }
}

backtracking의 구현

이차원 vector 전체를 parameter로 넘겨 받는 방식을 통해 간단하게 이차원 vector를 통째로 조작하는 backtracking을 구현

vector<vector<int> > up(vector<vector<int> > b, int depth) {
    ...
    return b;
};
vector<vector<int> > down(vector<vector<int> > b, int depth);
vector<vector<int> > left(vector<vector<int> > b, int depth);
vector<vector<int> > right(vector<vector<int> > b, int depth);

void simulate(vector<vector<int> > b, int depth) {
    if(depth == 5) return;
    
    simulate(up(b), depth+1);
    simulate(down(b), depth+1);
    simulate(left(b), depth+1);
    simulate(right(b), depth+1);
}

11049 행렬 곱셈 순서
11049 코드

풀이

2차원 DP (bottom-up)

10986-나머지 합
구간 i, j의 구간 합을 M으로 나눈 나머지가 0이라는 것은,
(psum[j] - psum[i-1])%M = 0이라는 것

N=5, M=3일 때
1 2 3 1 2 라는 수열에서, 구간 합 배열을 구하면 1 3 6 7 9
이를 M으로 나눈 나머지의 배열은 1 0 0 1 0
0 + 1 + 2 + 1 + 3 = 7
(빈 배열의 합이 0이므로, 값 0은 1부터 세서 더한다. 하지만 값 1은 2번 등장하고 나서부터 조건에 맞는 구간이 형성되므로 0부터 세서 더한다)

Euclidian Algorithm / 유클리드 알고리즘 / 유클리드 호제법 (정수론)

boj 1934, 2981 등

재귀를 이용한 구현
https://www.acmicpc.net/source/46833174

두 양의 정수 a, b(a > b)에 대해, a = bp + r 이라면
a, b의 최대공약수 = b, r의 최대공약수 ( gcd(a, b) == gcd(b, r) )

r = 0이 될 때까지 재귀적으로 나누어 내려가면, 그 때의 b'가 곧 a, b의 최대공약수가 된다.

ex) 12345와 1234의 최대공약수
12345 % 1234 = 5
1234 % 5 = 4
5 % 4 = 1
4 % 1 = 0
따라서 gcd(12345, 1234) = 1

시간복잡도
나눗셈 횟수 = O(log a), 정수의 나눗셈의 복잡도 = O(log a)
전체적으로 O((log a)^2)

5430 AC
5430 코드

C++ 문자열 파싱

1. find() + substr()

// example
current= str.find(',');
//find는 찾을게 없으면 npos를 리턴함
while(current!=string::npos){
    string substring=str.substr(previous,current-previous);
    x.push_back(substring);
    previous = current+1;
    current=str.find(',',previous);
}
x.push_back(str.substr(previous,current-previous));

// 문제에서의 활용(n번 반복: 0번을 포함)
curr = arr.find(",");
for(int i = 0; i < n; i++) {
    integer = arr.substr(prev, curr - prev);
    dq.push_back(stoi(integer));
    prev = curr + 1;
    curr = arr.find(",", prev);
} 

2. istringstream + getline()

// example
#include<iostream>
#include<string>
#include<vector>
#include<sstream>

using namespace std;

int main()
{
    string str="java c c++ python";
    istringstream ss(str);
    string stringBuffer;
    vector<string> x;
    x.clear();
    cout<<"어떻게 잘리는지 확인해봅시다 ->";
    //구분자가 , 이라면 getline(ss, stringBuffer, ',')쓰면됨
    while (getline(ss, stringBuffer, ' ')){
        x.push_back(stringBuffer);
        cout<<stringBuffer<<" ";
    }
    
    cout<<endl<<"vector 값을 출력해보자."<<endl;
    for(int i=0;i<x.size();i++){
        cout<<x[i]<<endl;
    }
    
    return 0;
}

2293 동전 1
2293 코드

알고리즘

각 동전의 가치가 배수 관계인 경우, 그리디 알고리즘으로 해결 가능 (11047 동전 0)
하지만 본 문제처럼 배수 관계라는 조건이 없을 경우, dp로 해결

풀이 (참조)

• dp[n] : 주어진 동전을 이용해 n원을 만드는 방법의 수
• base case: dp[0] = 1 (즉, 0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 방법이 존재)
• 점화식: $dp_{new}[n]=dp_{prev}[n] + dp[n - \text{현재 사용하려는 동전의 가치}]$
  

dp[0] = 1;
// 각 동전마다 갱신
for(int i = 0; i < n; i++) {
    // 현재 동전의 가치부터 목표 값 k가지 갱신
    for(int j = coin[i]; j <= k; j++) {
        // 점화식
        dp[j] += dp[j - coin[i]];
    }
}

2096 내려가기
2096 코드

최댓값과 최솟값을 동시에 구해야 하는 문제
단순하게 dp를 위한 배열을 2개 만들 경우 메모리 초과 ($4 bytes * 10^6 * 3 * 2$)

1차원 dp -> 바로 직전 정보만 알고 있으면 다음 단계로 진행 가능 -> sliding window 방식 적용하여 메모리 최적화 가능

Pitfall

매 반복문에서 다음 단계를 위한 dp배열을 새로 초기화해주어야 한다. 그렇지 않으면 이전 단계에 계산한 값이 남아있어 결과에 영향을 줌.

// solve: dp
    for(int i = 1; i < n; i++) {
        // 단계 진행할 때마다 배열을 초기화
        for(int j = 0; j < 3; j++) {
            dp_min[i % 2][j] = INT32_MAX;
            dp_max[i % 2][j] = -1;
        }
        for(int j = 0; j < 3; j++) {
            ...

12015 가장 긴 증가하는 부분 수열 2
12015 코드
참고한 풀이

11053 가장 긴 증가하는 부분 수열 문제의 경우 dp를 이용해 $O(N^2)$ 시간에 해결 가능
하지만 위 문제는 $N = 10^6$이므로 같은 방법으로 해결 불가능하다

Lower Bound

어떤 정렬된 배열에서, 특정 값 val의 lower bound = 정렬된 상태를 유지하면서 val을 삽입할 수 있는 가장 작은 index
이분 탐색을 이용해 $O(\log N)$만에 구할 수 있다
C++의 경우, 헤더에서 lower_bound 함수를 지원 한다 (해당 배열에서 lower bound에 해당하는 자리의 pointer를 반환. 없을 경우 last 반환)

풀이

1. 배열 LIS를 새로 정의 하고, 빈 배열로 초기화 한다. 해당 배열은 정렬된 상태로 유지 된다.
2. 입력 받은 수열을 차례대로 탐색하면서, 탐색값 val의 LIS에서의 lower bound를 탐색한다.
   • lower_bound가 존재하지 않는 경우, last에 값을 추가한다 (LIS의 길이 + 1)
   • lower_bound가 존재하는 경우, 해당 자리의 val로 바꾼다

주의점

14002 가장 긴 증가하는 부분 수열 4
14002 코드
해당 방법으로는 LIS를 구성하는 실제 원소들을 알 수는 없다. 실제 LIS를 구하고 싶다면, 따로 index를 저장하는 배열을 저장한 후 끝에서부터 탐색하는 방식으로 구하여야 한다.

입력되는 수열 A의 원소 $A_i$의 최솟값이 1인 경우, LIS 배열을 그보다 작은 0으로 초기화 해주어야 자연스럽게 코드가 구현된다.
(그렇지 않은 코드의 경우 길이가 1 작게 나오거나, LIS를 구현하는 과정에서 index가 틀릴 수 있다.)

2754 학점계산

float point = 12.3456;
cout << fixed;         // "소수점 이하" 자릿수를 고정하겠다
cout.precision(1);    // 1자리로 고정하겠다 (fixed 없이 사용할경우, 정수부를 합친 전체 자릿수가 고정됨)
// 이후 출력 되는 모든 소수들은 소수부가 한 자리로 고정 됨
cout << point;       // 12.3 출력

cout.unsetf(ios::fixed);    // fixed 해제

1520 내리막 길
1520 코드
참고한 풀이

DP를 응용한 dfs

1202 보석 도둑
1202 코드

풀이

그리디 알고리즘: 가장 가치가 높은 보석부터 하나씩 가방에 담는다
보석은 priority_queue를 이용한 max heap, 가방은 multiset을 이용한 BST로 저장 후 탐색
multiset인 이유는 무게 한도가 같은 가방이 중복으로 들어올 수 있기 때문

시간 초과가 발생한 이유

보석을 담을 수 있는 가장 작은 무게의 가방을 탐색하기 위해 이분탐색(lower_bound) 활용
이때, <algorithm>의 lower_bound(start, last, k) 함수를 이용할 경우, 인자를 넘기는데 $O(n)$의 시간이 걸린다.
따라서 multiset의 member function인 lower_bound를 사용하여야 효율적으로 탐색 가능하다

11066 파일 합치기
11066 코드
참조 풀이

Call by Reference example

void func(int a, queue<int> &q) {
    q.push(a);
    return;
}

int main() {
    queue<int> q;
    func(10, q);
    cout << q.front() << endl;    // print 10
}

빠른 약수 구하기

1부터 n까지 직접 나눠보기 -> O(n)
1부터 sqrt(n)까지 나눠본 후, 그렇게 나온 값들을 이용해 다시 n을 나누어 구하기(중복제거) -> O(√N)

이항 계수 구하기

1. nCr = n! / r! (n-r)! 이용 -> 팩토리얼 계산으로 인해 숫자가 조금만 커져도 오버플로우 가능
2. nCr = n-1Ck + n-1Ck-1 이용 -> 동적계획법
3. 완전탐색 memoization -> 동적계획법 2(https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients)

factorial에서 우측 0의 개수 구하기 1676 팩토리얼 0의 개수, 2004 조합 0의 개수

가령 10!에서 2가 몇번 곱해졌는지 구하려고 할 때,

10 // 2 = 5 -> 2 4 6 8 10 총 5개
10 // 4 = 2 -> 4 8 총 2개
10 // 8 = 1 -> 8 총 1개

즉, 10!은 2가 총 8번 곱해진 수이다.
같은 방식으로 5의 개수를 구해 10의 몇승이 곱해졌는지 구하면 0의 개수를 구할 수 있다.

어려웠던 문제

2981 검문
N개의 숫자가 주어졌을 때, M으로 나눈 나머지가 모두 같은 숫자 M을 모두 찾는 문제

N_1 = M * a_1 + R
N_2 = M * a_2 + R
N_3 = M * a_3 + R
...

각각의 차를 구하면 R이 소거되어, 이들의 최대공약수를 유클리드 호제법으로 구하고 그의 약수를 모두 찾으면 된다.

2206 벽 부수고 이동하기
2206 코드
풀이

1. 가중치가 없는 최단 경로를 찾는 문제: dfs는 불가능, 무조건 bfs

2. 벽을 일일히 하나씩 부숴보는 브루트 포스 방식은 (N*M)^2의 시간 복잡도가 소요. 불가능

3. 지금까지의 일반적인 bfs처럼 칸마다 방문체크를 하는 방식만으로는 불가능

   1. 만약 현재 칸까지 벽을 부수지 않고 최단 거리로 왔다면, 앞으로 벽을 부술 수 있음을 알아야 한다.
   2. 벽을 부숴야 현재 칸까지 최단으로 도착할 수 있지만, 벽을 부수지 않고도 도달할 수 있다면? 그리고 현재 칸에서 목표 지점까지 반드시 벽을 부숴야 한다면? -> 더 멀더라도 반드시 벽을 부수지 않는 방법을 선택해야 함

4. 그렇다면 어떻게 할 것인가?

   • 전역 변수로 저장 -> 불가능 (백트래킹마냥 실패했을 때 되돌릴 수 있어야 함. bfs로는 힘들다)
   • 두 개의 방문 배열 사용(visited[N][M][2]) -> 하나는 벽을 부수지 않고 도달한 경로, 하나는 벽을 부수고 도달한 경로
   • 또한 큐에 이전에 벽을 부순 적 있는지 없는지에 대한 상태를 저장해야 한다

5. 벽을 부순 세계의 경로는 벽을 부수지 않은 경로와는 무관하다. 벽을 부수지 않은 경로에서 이미 지나왔던 길도 중복체크 해야 함. 또한 어떤 경로로든 이전에 지나간 적이 있다면 무시
   ex)

5 6 
000000 
011110 
010000 
010111 
100000

visited[i][j][0](벽을 부순적 없는 경로)는 일반적인 bfs와 크게 다를 바 없지만
visited[i][j][1]의 경로는 벽을 부순 다음 다시 부수는 경우를 제외하면 모두 가능하기 때문에,
(2,5) 또는 (3,5)처럼 중첩되는 경우가 존재할 수 있다.

9251-LCS

input: 2개의 문자열 a, b
각 문자열의 맨 앞에 0을 끼워넣은 2차원 행렬 생성
dp[i][j] == a[:i-1], b[:j-1] 문자열의 최대 LCS 길이

dp[i][j]를 구하기 위해,

if a[i-1] == b[i-1]
    이전까지의 최장 LCS 길이 + 1 (즉, dp[i-1][j-1] + 1)
else
    max(좌, 상) (즉, max(dp[i-1][j], dp[i][j-1])

11659-구간 합 구하기4

주어진 수열에 대해 구간 합을 구하는 것은 O(n)
이때 한 번 누적 합 배열(prefix sum array)을 구해두면, 각 구간 쿼리에 대해 O(1)만에 구간 합을 구할 수 있다

psum[i] = 처음부터 i번째 수까지의 합
i번째 수부터 j번째 수까지의 합 = psum[j] - psum[i-1]

13460 구슬 탈출 2
13460 코드

구현할 때 고려할 것
구슬끼리 만나서 이동하는 경우
파란 구슬이 빠지면 빨간 구슬이 빠져도 무시
파란 구슬이 빠진다고 끝이 아니라, 다른 경우를 더 찾아야 함
꼭 빨간 구슬만 움직일 수 있어야 하는 건 아님
visited는 사용 불가 (복잡하게 움직이는 경우)