Problem Solving/BOJ(백준)
-
[BOJ]백준 15988번: 1, 2, 3 더하기 3(C++)/DPProblem Solving/BOJ(백준) 2021. 7. 4. 23:09
https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 오랜만에 DP 기본문제 숫자가 커질 수 있으니 계산 과정에서 나머지 연산을 꼭 해줘야 한다 !! 처음에 최대 숫자까지 미리 계산해준 뒤 입력에 따라 출력만 제대로 해주면 끝 #include #define MOD 1000000009 int n, tc, dp[1000005] = { 0,1,2,4 }; int main() { for (int i = 4; i
-
[BOJ]백준 17490번: 일감호에 다리 놓기(C++)/MSTProblem Solving/BOJ(백준) 2021. 7. 3. 00:35
https://www.acmicpc.net/problem/17490 17490번: 일감호에 다리 놓기 2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다. www.acmicpc.net 간만에 제대로된(화나는) MST 문제 이렇게 호수 주변의 강의실(노드)들이 있고, 가운데에 와우동?이 있으며 각 강의실을 특정 개수의 돌멩이로 연결할 수 있을 때 K개 이하를 사용해서 모든 강의실이 연결될 수 있는지 묻는 문제 우선 이웃한 강의실 끼리는 공사중인 경로를 제외하고 기본적으로 모두 연결되어 있다 그렇기에 공사중인 경로가 1개 이하이면(0개이면 1~N까지의 강의실이 O 형태로 처음부터 연결되어있음,..
-
[BOJ]백준 1939번: 중량제한(C++)/Dijkstra, Binary SearchProblem Solving/BOJ(백준) 2021. 6. 30. 23:09
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 이진탐색+그래프탐색 문제 건널 수 있는 최대 중량(중량의 범위)을 알아내는 것이기 때문에 해당 범위를 binary search로 찾아내야하고, 처음에는 DFS로 돌렸으나 메모리초과가 뜨길래 왜틀렸지?하고 질문게시판을 뒤져본 결과 "인접 행렬로 연결 상태를 저장하면 메모리가 터지기 때문에 인접 리스트로 구현해야 한다"는 것을 알았다 사실 그래프 탐색 ..
-
[BOJ]백준 17396번: 백도어(C++)/DijkstraProblem Solving/BOJ(백준) 2021. 6. 30. 00:49
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 다익스트라 기본 문제 요즘 다익스트라가 어렵게 나오는 것 같아서 다익스트라 심화 문제를 얼른 많이 풀어보고 싶다 어제 카카오 기출 훑어봤을 때에는 트리에서의 다이나믹프로그래밍 문제도 있더라 .... 저번 주에 너무 놀아서 다시 문제 많이많이 풀어야겠다 문제에서 주어진 시야에 보이는 노드들을 disable하고 dijkstra로 탐색하는 과정에서 도착 노드가 아닌 disab..
-
[BOJ]백준 11728번: 배열 합치기(Python)/Two PointerProblem Solving/BOJ(백준) 2021. 6. 29. 00:42
https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net merge sort스러운 투포인터 문제 n,m=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) ans=[] a=0 b=0 while a!=len(A) or b!=len(B): if a==len(A): ans.append(B[b]) b+=1 elif ..
-
[BOJ]백준 1219번: 오민식의 고민(C++)/Bellman-FordProblem Solving/BOJ(백준) 2021. 6. 21. 23:53
https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 조금 어려웠던 벨만포드 문제 ~~~~ 아주 전형적인 벨만포드 문제라면 음수 사이클의 존재 여부만 체크할텐데 이 문제에서는 음수 사이클이 존재하는지 & 해당 사이클에서 목적 노드로의 path가 있는지 또한 검사해야 했다 그래서 3번이 처음에는 음수 사이클이 존재한다면 Gee를 출력하는 줄 알았지만 ~~ 여러개의 음수 사이클이 존재하더라도, 하나의 음수 사이클에서라도 도착지로 가는 path가 있을 ..
-
[BOJ]백준 17836번: 공주님을 구해라!(C++)/BFSProblem Solving/BOJ(백준) 2021. 6. 17. 01:08
https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 응용 BFS문제인 공주님을 구해라 ~!~! 공주에게 도달할 수 있는 최단거리 상태가 검을 얻었을 때/검을 얻지 못했을 때로 나뉘기 때문에 visit 배열을 3차원으로 만들어주어야 한당 이렇게 3차원 visit 배열을 요구하는 BFS문제는 까다로울 수 있기 때문에 주 의 하 자 #include #include using namespace std; typedef struct { int..
-
[BOJ]백준 21924번: 도시 건설(C++)/MSTProblem Solving/BOJ(백준) 2021. 6. 17. 01:01
https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 기본 MST 문제~!~!~!~!~! #include #include #include #define pii pair #define INF 987654321 using namespace std; vector g; int n, m; long long sum; long long pr..