티스토리

복습 정리 노트

검색하기

블로그 홈

복습 정리 노트

restudycafe.tistory.com/m

공부 기록 저장용

구독자: 78

방명록 방문하기

반응형

주요 글 목록

12월 알고리즘 공부 : 퍼시스턴트 세그먼트 트리, 머지 소트 트리, 오일러 회로 등 백준 BOJ 11012번 : Egg 문제 난이도 : Platinum II 알고리즘 분류 : 퍼시스턴트 세그먼트 트리 2차원 좌표계에서 점들의 좌표가 주어질 때, 직사각형 영역이 쿼리로 주어지면 해당 영역에 점이 몇 개가 있는지를 구하는 문제이다. (0 ≤ x, y ≤ 10^5, Q ≤ 50,000) 1차원 좌표계였다면 일반적인 세그먼트 트리로 해결이 가능한 것은 물론이고 값의 갱신이 없으므로 누적 합으로도 쉽게 계산이 가능하다. 2차원 좌표계 + 작은 범위였다면 2차원 배열의 누적 합으로 쉽게 계산이 가능하다. 이 문제에서는 세그먼트 트리 또는 2차원 배열을 선언하면 메모리 초과가 발생하게 되는데 이를 어떻게 해결할 수 있을까? 이러한 문제는 퍼시스턴트 세그먼트 트리(Persistent Segment T.. 공감수 0 댓글수 1 2022. 12. 14.
백준 BOJ 2-SAT 알고리즘 심화 문제 풀이 백준 BOJ 1739번 : 도로 정비하기 문제 난이도 : Platinum I 알고리즘 분류 : 2-SAT 어떤 가로 도로에 대해서 왼쪽 일방 통행의 경우 T, 오른쪽이면 F로 임의로 두자. 마찬가지로 세로 도로에 대해서도 위 방향은 T, 아래 방향을 F로 두자. 방향은 푸는 사람이 정의하면 된다. 명제 연결할 때만 제대로 연결하면 관계없다. 이제 어떤 점에서 다른 점으로의 이동에 대해, 두 가지 경로가 있으므로, 두 경로에 대해 (A and B) or (C and D)꼴이 나온다. 이것을 식을 풀어서 (나는 분배 법칙으로 풀었다.) (E or F) and (G or H) 꼴로 바꾼 뒤 2-SAT를 적용해주면 된다. 이 문제는 2-SAT에 다른 알고리즘이 접목된 문제도 아닌데 난이도가 Platinum I이.. 공감수 0 댓글수 0 2022. 11. 27.
빠른 MCMF 최소 비용 최대 유량 알고리즘 등 (+ 응용 문제 풀이) 11월 말 백준에서 풀이한 문제들 중, 플래티넘 이상 난이도 문제들에서 다른 사람들이 잘 다루지 않는 내용들을 선별하여 정리해보려고 한다. 이번 기간에 다룬 알고리즘은 MCMF(최소 비용 최대 유량)이다. 낮은 난이도나 다른 사람들이 많이 푼 문제들은 이미 다 풀어서 플래티넘 난이도 중에서도 어려운 것만 남았고, 그에 대한 풀이를 다룬 사람들이 별로 없어서 간략하게나마 적어본다. 어디까지나 스스로 공부, 잊어버렸을 때 나중에 다시 참고하기 위한 목적이지만 혹시나 검색 유입으로 보는 사람이 있다면 도움이 될 수 있으면 좋겠다. 백준 BOJ 14424번 : 두부장수 장홍준 3 문제 난이도 : Diamond V 알고리즘 분류 : MCMF (최소 비용 최대 유량) 사실 이 문제는 이전에 백준 BOJ 11111번.. 공감수 0 댓글수 0 2022. 11. 27.
11월 알고리즘 공부 : 최소 외접원/구, 가장 가까운 두 점, 번사이드 보조정리 등 최근 글 작성 빈도가 현저히 낮아졌는데, 바쁘다거나 그런 이유보다는 2022년 막바지로 갈수록 의욕이 떨어져간다는 표현이 맞는 것 같다. 그래도 아직 백준에서 2022년 푼 문제 수 랭킹 1위를 유지하고 있기 때문에 최소한 유종의 미라도 거두기 위해 연말까지는 열심히 풀어보려고 한다. 아무튼 11월 중순동안 공부한 내용들을 나중에 스스로 참고할 수 있도록 정리해보려고 한다. 백준 BOJ 2626번 : 헬기착륙장 문제 난이도 : Diamond V 알고리즘 분류 : 최소 외접원 2차원 좌표 평면 상의 N개의 점이 주어질 때 이들을 모두 포함하는 가장 작은 원의 중심과 반지름을 구하는 문제이다. 세 점을 지나는 원이 반드시 존재함을 이용하여 풀이하는 문제이다. (여담으로, 타원의 경우 최대 다섯 개의 점을 지.. 공감수 0 댓글수 1 2022. 11. 22.
백준 BOJ 17030번 : Cow Dating 풀이 (Diamond V, 투 포인터) 백준 BOJ 17030번 : Cow Dating 문제 난이도 : Diamond V 알고리즘 분류 : 투 포인터, 누적 합 N개의 선택받을 확률 p_i가 주어질 때 (실제 입력은 p_i의 10^6배를 한 값들로 주어진다.) 연속한 구간 p_l ~ p_r을 선택하여 그들 중 하나에게만 선택이 될 확률의 최댓값을 구하는 문제이다. 구간을 잡고 관계식을 찾는 것이 핵심이다. 구간 [l, r]에서의 확률이 이미 있을 때, 어떤 조건에서 구간을 늘렸을 때 확률이 늘어나는지 계산해보자. 구간 [l, r]에서 하나에게만 선택받을 확률 f(l, r)은 위의 식처럼 나타낼 수 있고, 거기에 항을 하나 추가하여 f(l, r+1)을 관계식으로 구할 수 있다. 그러면 f(l, r+1) > f(l, r)일 조건을 찾아주면 된다... 공감수 0 댓글수 0 2022. 11. 12.
백준 BOJ 24486번 : Counting Haybales 풀이 (Diamond II, DP) 백준 BOJ 24486번 : Counting Haybales 문제 난이도 : Diamond II 알고리즘 분류 : DP N개의 자연수가 주어지고, 크기 차이가 1인 인접한 두 수를 서로 swap할 수 있다고 할 때, 만들 수 있는 서로 다른 수열의 개수를 구하는 문제이다. 문제의 풀이는 USACO 사이트를 참고하였다. 먼저 관찰을 통해 알 수 있는 사실은 홀짝성이 같은 수들끼리는 순서가 바뀔 수 없다는 것이다. (이것은 오직 크기 차이가 1인 인접한 두 수만 교환이 가능하므로, 홀짝성이 같은 = 크기가 2 이상 차이나는 수는 서로 위치가 바뀔 수 없기 때문이다.) 원래 정석적인 풀이는 이 사실을 이용하여 그래프의 단방향 간선들을 만들 수 있으므로, 위상 정렬로 푸는 풀이로 보인다. 아무튼 홀짝성을 활용하.. 공감수 0 댓글수 0 2022. 11. 10.
백준 BOJ 10058번 : 센서 네트워크 풀이 (Ruby V, 이분 매칭) 백준에서 3600문제 넘게 풀면서 루비 난이도 문제를 처음으로 푼 기념으로 이 문제만 별개의 포스트로 정리해본다. 무려 월드 파이널 문제이며 그 해 문제 중에서도 solved.ac 기준으로 난이도가 가장 높은 문제이다. 백준 BOJ 10058번 : 센서 네트워크 문제 난이도 : Ruby V 알고리즘 분류 : 기하학, 이분 매칭 2차원 좌표 평면 상에 N개의 점이 주어질 때, 어떤 두 점의 거리도 M 이하가 되게 하는 점들의 집합의 최대 크기와 그 때의 점들의 번호 목록을 구하는 문제이다. 가장 naive하게 생각할 수 있는 풀이는 각 점을 집합에 포함시키거나 시키지 않은 뒤 해당 집합에서 가장 먼 두 점 사이의 거리가 M 이하라면 집합의 최대 크기를 비교하여 갱신해주는 방식이 있다. 이 때의 시간 복잡도.. 공감수 0 댓글수 0 2022. 10. 29.
이분 매칭 알고리즘 어려운 문제들 풀이 (Platinum II ~ Diamond) 백준 BOJ 3419번 : Racing Car Trail 문제 난이도 : Diamond III 알고리즘 분류 : 이분 매칭 N x M 크기의 배열이 주어지고, X가 없는 칸에서만 이동이 가능하다고 할 때, Alice와 Bob이 번갈아가면서 지나온 칸은 다시 이동하지 않도록 칸을 이동시키면서 상대가 더 이상 이동하지 못하도록 최선의 전략으로 이동시킨다고 할 때, 각 칸에서 시작할 때 누가 이기는지를 구하는 문제이다. 격자 그래프는 이분 그래프이므로 이분 매칭 알고리즘으로 최대 매칭을 구한 뒤, 시작점 v를 포함하지 않는 최대 매칭이 존재한다면 Bob이 항상 이길 수 있다. 왜냐하면 그러한 매칭이 존재하는 경우 Alice는 어떻게 이동해도 최대 매칭에 포함되는 정점으로 이동하게 되고, Bob은 그 격자점과 .. 공감수 0 댓글수 0 2022. 10. 23.
이분 매칭 최대 독립 집합 (Maximum Independent Set) 외 문제 풀이 이 포스트에서는 이분 매칭의 응용 중 하나인 최대 독립 집합(Maximum Independent Set)에 대해서 다룬다. 어떤 노드들의 집합에서 어떤 두 노드도 서로 간선으로 연결되어 있지 않을 때, 이 집합을 독립 집합이라고 한다. 그래프에서 최대 크기의 독립 집합을 최대 독립 집합이라고 한다. 이분 매칭 문제에서 최대 독립 집합은 전체 노드에서 최소 정점 커버(= 최소 꼭짓점 덮개)를 뺀 나머지가 된다. 그리고 최소 정점 커버는 쾨니그의 정리에 의해서 최대 매칭 수와 동일하다. 즉, 최대 독립 집합의 크기 I = V - M이다. (V = vertex의 수, M = 최대 매칭 수) 백준 BOJ 14986번 : Punching Power 문제 난이도 : Platinum III (난이도 기여로 난이도 상.. 공감수 1 댓글수 0 2022. 10. 20.
이분 매칭 (Bipartite Matching) 문제 풀이 모음 221019 이분 매칭 알고리즘에 대해서는 이전에 다룬 적도 있고 문제 풀이도 한 적 있지만 잊어버린 내용이 많아서 공부를 위해 다시 정리해본다. 이분 매칭 알고리즘 1. 이분 그래프란 그래프의 정점을 같은 그룹의 노드 사이에 간선으로 연결된 노드 쌍이 존재하지 않도록 두 그룹으로 나눌 수 있는 그래프를 의미한다. 2. 이분 매칭 알고리즘은 이러한 이분 그래프에서 하나의 노드가 두 개 이상의 간선에 포함되지 않도록 선택할 수 있는 최대 간선의 수를 말한다. (즉, 최대한으로 매칭시킬 수 있는 노드 쌍의 수를 찾는 것이다.) 3. 쾨니그의 정리는 최대 매칭 수 = 최소 꼭짓점 덮개 수라는 정리이다. 여기서 최소 꼭짓점 덮개란 몇 개의 노드를 선택하여 이들과 이 꼭짓점들을 포함하는 간선들을 체크할 때, 모든 간선들이 체.. 공감수 5 댓글수 0 2022. 10. 19.
백준 BOJ 풀이 (IGRUS Newbie Programming Contest 일부 포함) 백준 BOJ 25711번 : 인경산 문제 난이도 : Gold V 알고리즘 분류 : 누적 합 2차원 좌표 상의 N개의 점이 주어지고, 어떤 인접한 구간의 두 점 사이를 이동할 때 필요한 에너지는 내리막길일 경우 거리에 해당, 평지일 경우 거리의 2배, 오르막길일 경우 거리의 3배라고 할 때 M개의 쿼리에 대해 두 지점 사이의 필요한 에너지들을 구하는 문제이다. 쿼리 문제이므로 O(1)이나 O(log N)과 같이 짧은 시간에 쿼리를 처리할 수 있어야 한다. 이 문제에서는 누적 합을 이용하여, 맨 왼쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록을 구해둔다. 반대로, 맨 오른쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록도 구해둔다. 각각의 값들은 위에서 정의한 식대로 구해주면.. 공감수 1 댓글수 0 2022. 10. 3.
알고리즘 분할정복 거듭제곱, 투포인터 등 알고리즘 문제 풀이 221001 풀이한 문제들 중에서 인상적인 문제만 몇 개 뽑아서 정리한다. 문제 알고리즘은 무작위로 선정하였다. 백준 BOJ 25569번 : My뷰 꾸미기 문제 난이도 : Platinum IV 알고리즘 분류 : 조합론, 분할 정복을 이용한 거듭제곱 N개의 (a, b)쌍에 대해 min(a, b) = c라고 할 때, (a C 1 x b C 1) + (a C 2 x b C 2) + ... + (a C c x b C c)의 합을 구하는 문제이다. N과 a, b는 30만 이하이다. 각 항을 팩토리얼과 분모는 페르마의 소정리 + 분할 정복을 이용한 거듭제곱으로 계산이 가능하나, 항이 매우 많아 시간 초과에 걸리게 된다. 이 경우 항을 줄여주어야 하는데, (a C 1 x b C 1) + (a C 2 x b C 2) + ... +.. 공감수 16 댓글수 1 2022. 10. 1.
삼분 탐색 알고리즘 문제 풀이 모음 220926 삼분 탐색 알고리즘(Ternary Search Algorithm)이란 말 그대로 구간에서 1/3 지점과 2/3 지점의 함수값의 크기 비교를 기반으로 탐색을 해나가는 알고리즘이다. 이분 탐색 알고리즘은 그래프가 단조 증가 또는 단조 감소한다는 조건 하에서만 사용이 가능하지만, 삼분 탐색은 극값이 최대 1개 이하로 있는 모든 그래프에 대하여 사용 가능하다. (즉, 단순히 극값을 갖는 그래프 뿐만이 아닌 단조 증가, 감소 그래프에서도 사용이 가능하다.) 1개의 최솟값을 갖는 y = x^2 꼴의 그래프를 [l, r]의 구간에서 삼분 탐색하는 상황에 대해 생각해보자. (물론 극값을 구간에 포함하고 있다고 가정한다.) 1/3 지점을 x = m1, 2/3 지점을 x = m2라고 하며, 우리는 극값의 x 좌표 x_mi.. 공감수 2 댓글수 0 2022. 9. 27.
백준 BOJ 새로 나온 문제들 풀어보기 220904 백준 BOJ 25513번 : 빠른 오름차순 숫자 탐색 문제 난이도 : Gold V 알고리즘 분류 : BFS 주어진 5 x 5 크기의 배열에서, 특정 위치에서 시작하여 1, 2, 3, 4, 5, 6을 순서대로 방문하는 최소 경로의 길이를 구하는 문제이다. (이 때, -1은 지나갈 수 없는 칸이며 만약 순서대로 방문하는 것이 불가능하다면 -1을 출력해야 한다.) BFS를 반복문으로 여러 번 사용하는 문제이다. 초기 위치에서 cur(1 ~ 6으로 반복문을 돌려준다.)를 방문하는 BFS를 구현하고, 방문이 되었다면 초기 위치를 해당 칸의 위치로 바꿔주고 다음 루프를 돌면 된다. 만약 방문이 불가능하다면 -1을 출력해주고 즉시 종료해주면 된다. 더보기 #include #define int long long usi.. 공감수 0 댓글수 0 2022. 9. 4.
무작위화 알고리즘 문제 풀이 모음 220903 백준 BOJ 12041번 : Password Security (Small 2) 문제 난이도 : Gold III 알고리즘 분류 : 무작위화, 구성적 모든 대문자 알파벳을 하나씩 사용하여 26자리 비밀번호를 만들 때, 해당 비밀번호가 N개의 주어진 문자열을 포함하지 않도록 만드는 문제이다. 1 ~ 26으로 이루어진 순열을 무작위로 만든 뒤, 이 순열에 해당하는 문자열이 N개의 문자열을 포함하지 않을 때까지 돌리면 된다. 문제는 아예 불가능한 경우가 있는데, 이를 해결하기 위해 1만번까지는 돌려보고, 그래도 해당하는 정답이 없으면 impossible로 간주해주면 모든 테스트케이스를 통과할 수 있다. (참고로 1천번은 넉넉하지 않아 WA를 받을 확률이 높다.) 더보기 #include #define int lon.. 공감수 0 댓글수 0 2022. 9. 4.
Mo's 알고리즘 (모스 알고리즘) 구현해보기 220902 Mo's 알고리즘이란 오프라인 쿼리(= 원소의 업데이트가 없어야 함)를 특정한 순서로 배치하여 효율적으로 처리하는 알고리즘이다. 보통 제곱근 분할법(= 루트 N개의 버킷으로 나누어, 원소들을 버킷 단위로 다루다가 필요할 때 원소 단위로 들어가 값을 다룸)을 활용하여 하나의 쿼리를 O(√N) 시간에 처리할 수 있다는 점에서 특이한 시간 복잡도를 갖는다. ** kks227님의 블로그를 통해 공부하였다. 문제도 거기서 소개한 문제들을 공부했다. 백준 BOJ 11659번 : 구간 합 구하기 (연습용) 문제 난이도 : Silver III 알고리즘 분류 : 누적 합 (..이지만? Mo's 알고리즘으로 풀어보았다.) 굳이 Mo's 알고리즘까지 필요하지는 않지만, 쿼리들을 재배치하여 풀어볼 수 있는 문제라는 점에서 한.. 공감수 0 댓글수 0 2022. 9. 1.
백준 BOJ 문제 풀이 기록 220831 백준 BOJ 18017번 : 총알의 속도 문제 난이도 : 난이도를 매길 수 없음 알고리즘 분류 : 물리학 A m/s로 달리며 B m/s로 총알을 발사했을 때 총알의 속력을 구하는 문제이다. 이 때 A, B는 10^8 이하이며, 10^(-9) 이내의 오차로 답을 구해야 한다. 상대성 이론을 사용하는 문제이다. 왜냐하면 속력이 10^8 수준까지 매우 커지면 빛의 속력을 고려할 필요가 있기 때문이다. 따라서 다음의 공식을 사용한다. 더보기 #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); double a, b; cin >> a >> b;.. 공감수 0 댓글수 0 2022. 8. 31.
백준 BOJ 브론즈 브루트포스 문제들 밀기 220830 오늘은 백준 브론즈 브루트포스 알고리즘 문제들을 밀어볼 것이다. 참고로 3,000문제를 넘게 풀면 나머지 브론즈 문제들은 솔직히 문제를 풀기보다 번역기에 돌린 문제의 지문을 "해석"하는 과정이 더 어렵다. (말 그대로 문장 구조의 앞뒤가 안 맞아서 대충 그동안 푼 문제들의 경험으로 문제의 지시를 끼워맞춰야 한다.) 백준 BOJ 9703번 : Anti-Arithmetic Permutation 문제 난이도 : Bronze II 알고리즘 분류 : 브루트포스 N개의 수가 주어졌을 때, 순서를 뒤집지 않고 어떤 3개의 수를 선택해도 그 세 수가 등차수열을 이루지 않도록 하는 수열을 Anti-Arithmetic Permutation이라고 할 때, 주어진 수열이 Anti-Arithmetic Permutation인지를.. 공감수 0 댓글수 0 2022. 8. 30.
백준 BOJ 알고리즘 공부 일기 (오프라인 쿼리 포함) 220829 백준 BOJ 13306번 : 트리 문제 난이도 : Platinum IV 알고리즘 분류 : 오프라인 쿼리, 분리 집합 트리와 쿼리가 주어질 때, 각 쿼리에 대해 특정 간선을 지우거나 두 정점이 연결 상태인지를 구하는 문제이다. 오프라인 쿼리 문제인데, 오프라인 쿼리 문제는 주어진 쿼리 순서대로 처리를 하는 것이 아니라 문제를 효율적으로 풀 수 있게끔 쿼리의 순서를 재배치하여 풀이하는 방식의 문제를 말한다. 예를 들어 이 문제에서는 쿼리를 역순으로 배치한 뒤 분리 집합으로 노드들을 연결해가면서 풀어주면 아주 쉽게 풀 수 있다. 역순 배치가 아닌 다른 순서대로 푸는 문제도 있는 것 같던데 조만간 공부할 것이다. (예를 들면 mo's 알고리즘. 지금 제곱근 분할법 문제 몇 개는 풀어봤는데 mo's를 공부 안해서.. 공감수 0 댓글수 0 2022. 8. 29.
선분 교차 판정 알고리즘 문제 풀이 정리 220828 백준 BOJ 20149번 : 선분 교차 3 문제 난이도 : Platinum IV 알고리즘 분류 : 기하학, 선분 교차 판정 두 선분의 끝 점의 좌표가 주어질 때, 두 선분의 교차 여부를 구하고, 만약 한 점에서만 교차한다면 그 좌표를 오차 범위 1e-9 이내로 구하는 문제이다. CCW 값들을 가지고 잘 푸는 것인지는 당연히 아는데, 케이스를 어떻게 나눠야 깔끔하게 정리되는지 도저히 구상이 안 되어서 다른 블로그를 보고 공부했다. 개인적으로는 이 링크에 설명이 가장 잘 되어있다고 생각하고 또 여기서 대부분의 코드를 참고했다. (20220829 수정 : 링크가 잘못 걸려 있었다;;) 일단 교차 판정을 먼저 해보자. 점은 a, b, c, d의 네 점이 주어지고 a, b를 잇는 선분과 c, d를 잇는 선분이 있.. 공감수 0 댓글수 0 2022. 8. 28.
2-SAT 알고리즘 응용 문제 풀어보기 220827 백준 BOJ 11281번 : 2-SAT - 4 문제 난이도 : Platinum III 알고리즘 분류 : SCC, 2-SAT 2-SAT에 맞는 식이 주어질 때 x1 ~ xN에 참 또는 거짓을 넣어 식 전체가 참이 되도록 만들 수 있는지 판별하고, 만약 가능하다면 식을 참으로 만드는 각 변수 x1 ~ xN의 값으로 가능한 것을 하나 구하는 문제이다. 식을 참으로 만들 수 있는지 여부의 판별은 2-SAT - 3의 풀이와 동일하다. 이제 식을 만족시키는 각 변수의 참/거짓 값을 찾아야하는데, 그리디하게 접근해보자. x → y라는 식이 거짓이 되는 경우는 x = true, y = false인 경우뿐이다. x = false이면 y는 true든 false든 관계없다. 식을 최대한 참으로 만들기 위한 최선의 전략은 노.. 공감수 0 댓글수 0 2022. 8. 27.
백준 BOJ 2-SAT 알고리즘, 우선순위 큐 등 풀이 220826 백준 BOJ 11280번 : 2-SAT - 3 문제 난이도 : Platinum IV 알고리즘 분류 : SCC, 2-SAT bool 변수 x1, ... , xn에 대해서 F = (xi ∨ xj) ∧ (xk ∨ xl) ∧ ... 와 같은 꼴의 식이 주어질 때, 변수들의 참 거짓을 적절히 설정하여 F의 값이 참이 되게 할 수 있는지 판별하는 문제이다. (a ∨ b)와 같은 식이 있을 때 a가 거짓이면 b가 참, b가 거짓이면 a가 참이라는 두 개의 식을 얻을 수 있고 이렇게 2M개의 식을 얻은 뒤 x와 ~x가 모두 참인 식이 하나라도 나오면 불가능, 나머지 경우는 가능이다. 이것은 SCC로 풀이 가능한데, 2N개의 노드에 대해 2M개의 간선을 모두 연결한 그래프를 만든 후 a와 ~a가 같은 scc에 속해있는 .. 공감수 0 댓글수 0 2022. 8. 26.
백준 BOJ 우선순위 큐(Priority Queue) 문제 풀이 220825 백준 BOJ 13904번 : 과제 문제 난이도 : Gold III 알고리즘 분류 : 그리디, 우선순위 큐 N개의 과제들의 남은 날짜 수와 그 과제의 점수가 주어질 때, 하루에 하나씩 과제를 하여 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 먼저 문제들을 남을 일 수를 기준으로 오름차순 정렬해준 뒤, 우선순위 큐에 할 과제들만 남겨보자. 우선순위 큐에 과제를 하나씩 넣고 만약 우선순위 큐의 size가 방금 넣은 날짜 수보다 많다면 같아질 때까지 빼주면 된다. i번째 과제를 넣는 과정을 통해 i일까지 할 과제들을 우선순위 큐에 남긴다고 생각하면, 하루에 한 개씩 과제를 할 수 있으므로 i보다 많은 수의 과제가 들어있으면 안되기 때문이다. 더보기 #include #define int long long us.. 공감수 0 댓글수 0 2022. 8. 25.
백준 BOJ 안 푼 문제들 중에서 쉬운 문제들 아무거나 220824 백준 BOJ 1477번 : 휴게소 세우기 문제 난이도 : Gold IV 알고리즘 분류 : 이분 탐색 길이가 K인 도로 위에 N개의 휴게소가 있고, 여기에 M개의 휴게소를 더 지어 휴게소 간 거리의 최댓값이 최소가 되도록 할 때, 그 최솟값을 구하는 문제이다. 이분 탐색을 이용하여 풀이할 수 있다. 답을 m으로 두고 l ~ r 범위 내에서 이분 탐색을 하면서 휴게소 간의 거리를 m으로 두고 휴게소를 설치했을 때 휴게소가 M개 이하로 설치되었는지 확인하면서 값을 갱신해주면 된다. 주의할 점은 두 휴게소 사이의 거리가 x라면, 휴게소는 max(x-1, 0) / m개 설치된다. 왜냐하면, 예를 들어서 생각해보면 휴게소 사이의 거리가 100인데 거리 50으로 휴게소를 설치한다고 하여 휴게소가 2개 설치되지는 않기.. 공감수 0 댓글수 0 2022. 8. 24.
강한 결합 요소(SCC) 알고리즘 solution들 정리 220823 백준 BOJ 2150번 : Strongly Connected Component 문제 난이도 : Platinum V 알고리즘 분류 : 강한 결합 요소 (SCC) 방향 그래프가 주어질 때, 이들을 SCC로 나누어 출력하는 문제이다. 여기서 말하는 SCC(Strongly Connected Component)란, 한 Component 내의 어떤 두 점 사이에도 이동이 가능한 요소를 말한다. (SCC를 나눌 때는 당연히 한 Component의 크기가 최대가 되도록 나누어야 한다.) 그래프를 입력받고 adj 벡터에 간선들을 저장해주는 부분은 기본적이므로 설명을 생략한다. 이제 DFS 방식으로 노드들을 탐색하며, 노드 번호를 방문하는 순서대로 오름차순으로 매긴다. (nnum 벡터에 저장) 즉, 번호를 먼저 매기는 것.. 공감수 2 댓글수 0 2022. 8. 23.
백준 BOJ 다양한 해시맵(map) 활용 문제들 solution 220822 백준 BOJ 24411번 : Stamp Combinations 문제 난이도 : Silver I 알고리즘 분류 : 누적 합, 해시를 사용한 집합과 맵 길이 N인 수열에 대해, 앞의 부분합과 뒤의 부분합의 합으로 쿼리로 입력된 값을 만들 수 있는지 구하는 문제이다. 이 때 N x Q(쿼리의 수) ≤ 10^7이다. 누적 합을 사용하는 것은 확실해보이나, 누적 합을 사용하더라도 O(N^2)에 돌아간다. 따라서 시간 복잡도를 조금 더 개선할 방법을 찾아보아야 한다. v_i를 1 ~ i번째 원소의 합이라고 하자. 그러면 뒤쪽 부분의 합은 v_N - v_i이고, 앞쪽 부분은 쿼리 값이 x라고 했을 때 x - (v_N - v_i)이다. map을 활용하여 v_0 ~ v_N 값들을 모두 저장해두고 m[x - (v_N - .. 공감수 0 댓글수 0 2022. 8. 22.
중간에서 만나기 : 밋 인더 미들 알고리즘 풀이 모음 220821 백준 BOJ 16287번 : Parcel 문제 난이도 : Platinum V 알고리즘 분류 : 중간에서 만나기 (밋 인더 미들), DP N개의 물품 중 "서로 다른" 물품 4개를 골라 그 무게의 합이 M이 되도록 하는 경우가 있는지 확인하는 문제이다. 우선 N이 5,000이므로, O(N^4) 같은 방법은 안 된다. 각 원소는 최대 20만이므로, 두 원소의 합을 배열에 저장하고, 나머지 두 원소의 합을 배열의 기록을 이용하여 비교해보는 방식을 사용해볼 수 있다. O(N^2) 시간에 두 원소의 합을 구성하는 원소의 주소를 u, w에 저장한다. 다음으로 O(N^2) 시간에 나머지 두 원소의 합이 기록된 것들 중에서 주소가 둘 다 겹치지 않는 것이 있으면, YES를 정답으로 출력해주면 되고 그러한 조합이 하나도.. 공감수 0 댓글수 0 2022. 8. 21.
트리를 사용한 집합과 맵 알고리즘 풀이들 정리 220820 백준 BOJ 6325번 : Definite Values 문제 난이도 : Silver V 알고리즘 분류 : 트리를 사용한 집합과 맵 N개의 (변수) = (변수) 꼴의 수식이 주어지고, 처음에는 a만 값이 제대로 지정되었다고 할 때, 모든 등식이 적용된 이후 값이 제대로 지정된 변수의 목록을 구하는 문제이다. set을 사용한다. a = b라는 등식에서, a가 값이 지정되지 않고 b가 지정되었다면 a는 제대로 된 값이 지정된다. (set에 insert 해준다.) 반대로 a가 값이 지정되고 b가 지정되지 않았다면 a의 값은 쓰레기 값으로 덮어진다. (set에서 erase 해준다.) 이 과정을 N번 반복한 다음 set의 모든 원소들을 출력해주면 된다. #include #define int long long usi.. 공감수 0 댓글수 0 2022. 8. 20.
백준 BOJ 스위핑, 값/좌표 압축 알고리즘 문제 풀이 모음 220819 백준 BOJ 18869번 : 멀티버스 II 문제 난이도 : Gold V 알고리즘 분류 : 값/좌표 압축 두 집합에 대해, a_i, a_j와 b_i, b_j의 대소 관계가 모두 같다면 두 집합은 동일하다고 할 때, N개의 집합에 대해 몇 개의 집합 쌍이 동일한지를 구하는 문제이다. 각 집합에 대해 좌표 압축을 수행해주면, 원소들의 대소 관계가 같은 집합은 동일한 원소들을 가지게 된다. 이를 활용하여 좌표 압축을 N번 반복해준 뒤 브루트포스로 답을 구해주면 된다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int M, N; ci.. 공감수 0 댓글수 0 2022. 8. 19.
백준 BOJ 문제 풀이 모음 : 그래프와 인접 행렬의 활용 220818 백준 BOJ 17272번 : 리그 오브 레전설 (Large) 문제 난이도 : Gold I 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 N초를 길이가 1초인 스킬과 길이가 M초인 스킬로 구성하는 방법의 수를 구하는 문제이다. dp[N] = dp[N-1] + dp[N-M]이라는 점화식을 세울 수 있다. 그러나 Large 문제에서는 N이 10^18 이하이므로 dp로는 풀이가 불가능하다. 따라서 점화식을 행렬로 구성하여 행렬의 거듭제곱으로 답을 구해주어야 한다. 위와 같이 점화식을 만들 수 있다. 참고로 M이 100 이하이므로, 행렬의 크기는 아무리 커도 100 x 100을 넘어가지 않는다. 위의 A 행렬을 N 제곱 해주면, 곱해지는 행렬은 a_0, a_-1, ...으로 구성되는데, 정의에 의해 a_0 = 1.. 공감수 0 댓글수 0 2022. 8. 18.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.