PS(백준)

DP, LBS, LIS, LDS

DP, LIS 알고리즘

DP, LCS 알고리즘 활용 문제

부분 문제 정의 아이디어가 핵심인 문제

DP를 활용하는 냅색 알고리즘의 전형적인 문제

그리디 배우기 좋은 문제

종료 시간 기준으로도 고려할 것이 있는게 핵심인 문제

그리디 알고리즘의 전형적인 문제

최선의 선택이 무엇인지 알아내는게 핵심인 문제

최선의 선택이 뭔지 생각하는게 핵심인 문제

배수와 약수 구하는 문제

약수의 성질 하나를 배울 수 있는 문제

유클리드 호제법으로 최대공약수를 구하고, 두 수의 곱을 최대공약수로 나눠 최소공배수를 구하는 문제

최대공약수 = 유클리드 호제법으로 구하기, 최소공배수 = 두 수의 곱 // 최대공약수

조건을 식으로 세워 규칙을 찾는 문제. 약수를 오름차순으로 나열했을 때 원래의 수가 되도록 하는 두 수의 곱 쌍들의 개수와, 제곱근 수의 상관관계 파악이 핵심

기약분수를 만들기 위해서 "분자와 분모의 최대공약수를 구하고, 분자와 분모에 각각 나눠준다"

조합 공식과 재귀 활용

팩토리얼 재귀 함수, 파스칼 삼각형 DP, 조합 공식 변형 for 등 다양한 풀이

경우의 수 구하는 문제

팩토리얼을 소인수분해 했을 때 5의 지수는, 팩토리얼의 뒤에서부터 0의 개수이다.

1676 팩토리얼 0의 개수와 비슷하지만, 0의 개수를 구하려는 값이 팩토리얼 형태가 아님. 1676번 문제의 원리는 그대로 써먹을 수 있다.

제너레이터를 사용하면 보다 간결한 코드로 풀 수 있는 문제. 분할 정복 함수의 리턴 값은 튜플 또는 다 인자로 반환하도록 하면 global을 쓰지 않아도 된다.

2630 색종이 만들기 문제와 유사하다. 현재 재귀에 해당하는 사이즈의 영역을 돌면서, 전체가 1이거나 0인 경우인지를 미리 판단해놓자.

2630, 1992 문제랑 똑같다. 차이점은 9분할이라는 점. 그에 따라 분할 정복 함수 리턴 형태가 달라진다.

거듭제곱을 분할정복으로 풀기

페르마의 소정리를 알아야 하는 문제

행렬의 곱셈

자연수의 거듭제곱 풀이와 행렬의 곱셈 풀이 짬뽕시키기

피보나치 수 점화식을 행렬을 사용한 식으로 나타내고, 선형대수 지식을 통해 식을 변형해서 어떤 상수 행렬의 거듭제곱 꼴로 바꾸는게 핵심. 그러고 나면 행렬의 거듭제곱 문제로 단순하게 바뀌게 된다.

이분 탐색 알고리즘을 배우기 좋은 문제

딕셔너리 활용하는 문제. 이분 탐색 알고리즘은 써도 되고 안써도 됨.

이분 탐색에서 분할하는 방법의 변형. 문제의 조건에 맞게, 수의 범위를 이분 탐색하면서, 현재 단계의 수로 어떤 함수를 거쳐 유의미한 값을 생산하고, 그 값을 이용하여, 조건에 맞는 "최대"의 수를 찾아야 하므로 그에 맞게 재귀를 분할한다.

1654 랜선 자르기 문제와 유사한 문제. 수의 범위를 이분 탐색하면서, 각 단계의 수에 대해서 문제의 조건에 맞는 값으로 어떻게 가공할 것인가. 그 값에 따라 분할을 어떻게 할 것인가가 핵심이다.

이분 탐색의 범위와 분할 기준을 생각해내는게 핵심인 문제

이분 탐색의 탐색 범위, 분할 기준, 분할 방법(조건문)을 생각해내는게 핵심인 문제

"길이 값"만 LIS 조건을 만족하고, 수열의 값 자체는 LIS 수열이 아닐 수도 있는 리스트를 만들어서 풀어야 하는 문제

최소 힙 heapq 모듈을 약간의 트릭과 함께 활용하여 최대 힙을 구현하는 문제

최소 힙 활용 문제

힙에 튜플을 넣음으로써, 우선순위를 매기는 값과 실제 데이터를 분리

모든 원소의 총 개수와, 중간값의 위치 사이의 규칙을 찾고, 그 것을 구현하기 위해 두 개의 힙을 사용하는 문제

전체 구간을 두 구간으로 분할하는 부분 문제 아이디어와, 점화식은 정확하게 어떻게 나타내어지는지 잘 생각해야하는 문제

11066 파일 합치기 문제의 풀이로 똑같이 풀리는 문제

재귀로 DP를 활용하는 top-down 방식으로 풀 되, 재귀 구조로 DFS를 활용하는 문제

냅색 알고리즘으로 풀 수 있는 문제

냅색 알고리즘을 활용하는데, 점화식을 세워보면 메모이제이션 배열을 1차원으로 구성해도 점화식대로 구현할 수 있음을 알 수 있고, 이를 활용하여 메모리 사용량을 최소화하는 문제

냅색 알고리즘으로 풀 되, 전체 문제를 색다르게 정의하면 메모리 최소화, 풀이 간편화가 가능한 문제

전형적인 그리디 문제

그리디 기초

3의 배수 결정조건을 통한 그리디 풀이

그리디 기초

시간복잡도를 고려해야하는 그리디 문제

최선의 선택을 잘 생각해봐야하는 문제

유클리드 호제법

베스킨라빈스31 필승법을 안다면 쉽게 풀 수 있는 문제

전형적인 다익스트라 알고리즘 활용 문제

다익스트라 알고리즘의 활용력을 키울 수 있는 문제

다익스트라를 가볍게 응용하는 문제

벨만 포드 알고리즘 학습에 유용한 기초 문제

플로이드 워셜 학습 문제

DP로 최단 경로 구하기

플로이드-워셜 알고리즘으로 쉽게 풀 수 있는 문제

다익스트라 or BFS 약간 변형

투 포인터 알고리즘 배우기

투 포인터 활용 문제

투 포인터 활용력 향상 문제

투 포인터와 에라토스테네스의 채

Meet In The Middle 알고리즘 배우기

DP에서 최단 경로 역추적

LIS 알고리즘에서 최단 경로도 같이 구하기

O(NlogN) LIS 알고리즘에 역추적 섞기

LCS 알고리즘에 역추적 섞기

최단경로를 역추적할 때 메모리 사용량을 줄이는 참신한 방법

BFS와 최단경로 역추적

다익스트라 알고리즘과 최단경로 역추적

플로이드 워셜 알고리즘에서의 최단 경로 역추적

트리의 모든 노드의 부모 정보를 담는 리스트를 구해보자

set 자료구조에 대해 알아보기

트리의 지름에 관한 성질

트리의 지름 구하기

트리의 전위 순회, 중위 순회, 후위 순회

트리의 순회 응용

이진 검색 트리의 특성을 활용하여 후위 순회만으로 전위 순회 구하기

트리의 판정(BFS나 DFS로 연결 요소를 돌면서 사이클이 없는지를 판정)

집합 학습

딕셔너리 연습 문제

집합 기초 문제

집합 기초 문제

집합과 문자열 슬라이싱

점과 원의 위치 관계

점과 원의 위치 관계 2

사이클이 존재하는 그래프를 stack을 활용하여 DFS할 때 유의할 점

유니온 파인드 개념 학습 문제

BFS 응용 문제

유니온 파인드 기초 문제

weighted union find

유니온 파인드 응용

누적 합 미리 구해두고 인덱싱해서 특정 구간 연속합 구하기

누적합 응용 문제

누적합 + 수학 응용

2차원 누적합, DP

신장 트리 학습

연결 그래프에서 MST를 찾는 두 가지 알고리즘, 크루스칼과 프림

크루스칼 MST (딕셔너리를 사용한 weighted union find 활용)

크루스칼 MST

모든 간선을 활용할 수 없을 때, MST를 만들어낼 수 있는 간선 집합을 어떤 식으로 추려내야할지 잘 생각해보자.

크루스칼 MST 문제인데 고려해야 할 사항이 많아 복잡함

위상 정렬 학습 문제

직접 간선을 만들고 수정한 뒤 위상 정렬 수행하기

최소 힙을 사용한 위상 정렬 알고리즘

2차원 배열 활용 문제

2차원 누적 합

전형적인 덱 문제

뒤집는 행위를 구현하는 부분에서 시간복잡도를 향상시키는 아이디어가 핵심인 문제

문제 예제의 흐름을 따라가면서 스택와 유사한 부분 파악하는게 핵심

문제의 조건을 꼼꼼히 따져가면서 단계적으로 분석하여 스택이 활용됨을 파악하는 문제

오큰수 문제와 유사함

DFS 노드 방문 순서를 기록하는 문제

전형적인 최소 신장 트리 문제