전체 글
-
[11403] 경로 찾기BOJ 2022. 2. 5. 09:32
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net int가 bool로 바뀌었을 뿐인 단순한 플로이드 문제 #include using namespace std; int n; bool a[101][101]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; int i, j, k; for (i = 0; i a[i][j]; for (k = 0; k
-
[11265] 끝나지 않는 파티BOJ 2022. 2. 5. 09:20
https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 입력받은 인접행렬로 플로이드를 돌려두고, 쿼리당 O(1)에 해결하는 문제 #include using namespace std; using ll = long long; const ll INF = (ll)1e13; ll n, m, a[501][501]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin ..
-
[2210] 숫자판 점프BOJ 2022. 2. 5. 08:43
https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 완전탐색하면 된다. 6개의 숫자가 만들어지면 set에 넣어두면, set의 size가 답이된다. #include using namespace std; int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}; char a[5][5]; set st; void f(int cy, int cx, string s) { if (s.len..
-
LIS + 역추적템플릿 2022. 2. 4. 15:38
"[14003] 가장 긴 증가하는 부분 수열 5"를 베이스로 둔다. dp로 O(N^2)에 풀 수 있는 문제이지만, 이분탐색으로 O(NlogN)에 동작하도록 만들 수 있고 다익스트라와 마찬가지로 '이전에 어디에서 왔는지'를 저장하면 최장 길이와 해당 수열도 구할 수 있다. 이분탐색은 lower_bound()로 간단하게 구현할 수 있고, iterator를 index처럼 사용하려면 begin()을 빼면 된다. #include using namespace std; using ll = long long; vector a; ll n; void lis(vector& ret) { vector v, path(n); for (ll i = 0; i = 0 && S > 0; i--) { if (path[i] == S - 1)..
-
[2776] 암기왕BOJ 2022. 2. 4. 06:29
https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 시간제한이 아슬아슬한데, set도 통과가 되어 unordered map따위를 쓸 필요는 없었다. 상수가 걸림돌이 될때에는 이분탐색도 한가지 방법이 되겠고, O(1)에 동작하는 해시도 충분히 적용할 수 있는 문제다. #include using namespace std; int t, n, m; set st; int main(void) { ios_base::sync_with_stdio(0); cin.tie(..
-
[11779] 최소비용 구하기 2BOJ 2022. 2. 3. 16:57
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 경로가 갱신될때마다 이전 노드를 저장한다면, e에서 s까지 역으로 경로를 복원할 수 있다. 물론, 이렇게 만들어진 경로는 도착->출발 순서이므로, 필요에 따라 reverse해주면 된다. #include using namespace std; using ll = long long; const ll MAX_N = 100'000, INF = (ll)1e17; ll n, m..
-
[18870] 좌표 압축BOJ 2022. 2. 3. 13:42
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표압축은 naive로 풀기 어려울때, 다른 알고리즘을 적용하기 좋게 전처리하는 느낌인듯 싶다. 값의 범위가 상당히 줄어듦에 이점이 있어 counting sort처럼 값의 개수등을 저장하는 선형 자료구조를 MLE에 대한 걱정없이 선언할 수 있으나 압축후에는 값간의 대소관계만이 남음에 유의해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 1..
-
[1238] 파티BOJ 2022. 2. 2. 10:45
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 처음에 주어지는 X에 대한 다익스트라의 결과값을 미리 base[]에 저장해두고 i=[1, n] 에 대해 dst[x]+base[i]의 최대값을 구하면된다. 역추적이 없으니 보다 구현이 간단하지만, 다익스트라의 시간복잡도에 대한 이해, 다익스트라가 구하는것의 의미를 잘 알아야 풀 수 있는 문제인것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..
-
[12605] 단어순서 뒤집기BOJ 2022. 1. 29. 07:35
https://www.acmicpc.net/problem/12605 12605번: 단어순서 뒤집기 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 www.acmicpc.net 한줄입력은 getline(), 공백기준 파싱을 string stream으로 해준다. cin.ignore()을 해주어야 getline()이 첫줄부터 제대로 받아온다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int T; vector v; int main(void) { ios..
-
[10422] 괄호BOJ 2022. 1. 29. 07:05
https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net dp를 채우는 방식이 독특한 문제, 홀수일 때에는 불가능하니 짝수일 때만 고려해주면 된다. 카탈란 수와 관련 있는 문제다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; using ll = long long; const ll M = 1e9 + 7; ll t, n, d..