⭐ 코딩테스트/백준
[백준 3015번 C/C++] 오아시스 재결합
[백준 3015번 C/C++] 오아시스 재결합
2024.03.16[백준 3015번 C/C++] 오아시스 재결합 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 해결전략 자료 구조 스택 Stack 정답코드 #include #include using namespace std; struct Info { int height, pair; // height: 키, pair: 조건을 만족하는 쌍의 수 }; int n; long long answer; // 계산할 조건을 만족하는 쌍의 수 stack..
[백준 13907번 C/C++] 세금
[백준 13907번 C/C++] 세금
2024.03.14[백준 13907번 C/C++] 세금 https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 해결전략 다익스트라 알고리즘 Dijistra Algorithm 최단경로 처음 시도한 코드 - 시간초과 #include #include #include using namespace std; const int INF = 987654321; int n, m, k; // n: 도시의 수, m: ..
[백준 13141번 C/C++] Ignition
[백준 13141번 C/C++] Ignition
2024.03.12[백준 13141번 C/C++] Ignition https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 해결방안 그래프 이론 브루트포스 알고리즘 최단 경로 플로이드–워셜 Floyd-Warshall 정답코드 #include #include using namespace std; const int INF = 987654321; int n, m; // n: 정점의 수, m: 간선의 수 vector di..
[백준 13977번 C/C++] 이항 계수와 쿼리
[백준 13977번 C/C++] 이항 계수와 쿼리
2024.03.08[백준 13977번 C/C++] 이항 계수와 쿼리 https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 수학 소페르마 정리 고민하다 힌트를 보았다. 소페르마 정리를 모르면 풀기 힘든 문제였다. 소페르마 정리를 읽고 공식을 코드를 구현하면 되었다. 정답 코드 #include using namespace std; long long factorial[4000001]; long long MOD = 1000000007; long long CustomPow..
[백준 2357번 C/C++] 최솟값과 최댓값
[백준 2357번 C/C++] 최솟값과 최댓값
2024.03.03[백준 2357번 C/C++] 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 해결전략 세크먼트 트리 Segment Tree 자료 구조 정답코드 #include #include #include // ceil, log2, min, max에 필요 using namespace std; #define INF 1000000001 struct Value{ long long minNum, maxNum; ..
[백준 14517번 C/C++] 팬린드롬 개수
[백준 14517번 C/C++] 팬린드롬 개수
2024.02.26[백준 14517번 C/C++] 팬린드롬 개수 https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net 해결전략 팰린드롬 Palindrome 포함 배제의 원리 동적계획법 Dynamic Programming 처음 시도한 코드 - 시간초과 #include #include #include #include #include using namespace std; string s; unordered..
[백준 2533번 C/C++] 사회망 서비스(SNS)
[백준 2533번 C/C++] 사회망 서비스(SNS)
2024.02.22[백준 2533번 C/C++] 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 해결전략 다이나믹 프로그래밍 Dynamic Programming 트리 Tree 깊이우선탐색 DFS 정답 코드 #include #include // min 함수 알고리즘 #include #include // memset 함수를 위한 라이브러리 using namespace std; int n; // 노드의 개수 v..
[백준 1094번 C/C++] 막대기
[백준 1094번 C/C++] 막대기
2024.02.17[백준 1094번 C/C++] 막대기 https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 해결방안 비트 수학 주어진 수 x를 2진수로 표현했을 때의 1의 개수가 우리가 구하고자 하는 막대의 개수와 같다. 정답코드 #include using namespace std; int x; // 입력 받을 수 int cnt; // 막대의 개수 int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0..
[백준 14428번 C/C++] 수열과 쿼리 16
[백준 14428번 C/C++] 수열과 쿼리 16
2024.02.16이 글은 보호되어 있기 때문에 이것을 보려면 암호가 필요합니다.
[백준 16565번 C/C++] N포커
[백준 16565번 C/C++] N포커
2024.02.13[백준 16565번 C/C++] N포커 https://www.acmicpc.net/problem/16565 16565번: N포커 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라. www.acmicpc.net 해결전략 수학 조합 (Combination) 포함 배제의 원리(Inclusion-Exclusion Principle) 여러 개의 집합이 있을 때, 전체 집합의 크기를 구하는 방법. 각각의 집합의 크기를 더하고 그 중에서 겹치는 부분을 빼는 방식. 정답 코드 #include using namespace std; int n; int com[53][53]; // 조합의 결과를 저장 const int mod = 10007; int Combination..
[백준 11689번 C/C++] GCD(n, k) = 1
[백준 11689번 C/C++] GCD(n, k) = 1
2024.02.11[백준 11689번 C/C++] GCD(n, k) = 1 https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 수학 오일러 파이함수 정답코드 #include . using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); long long n; cin >> n; long long answer = n; // 오일러 피를 계산할 변수를 선언하고, 초기값으로 n을 할당. for (long ..
[백준 13334번 C/C++] 철로
[백준 13334번 C/C++] 철로
2024.02.05[백준 13334번 C/C++] 철로 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 해결전략 정렬 set, multiset 우선순위 큐 priority_queue ※ 주의할 점 이 문제에서 set을 사용할거면 multiset을 사용해야 한다. set은 중복된 원소를 허용하지 않는다. 반면 첫 번째 코드에서는 multiset을 허용한다. multiset을 사용하여 시작점이 같은 데이터도 모두 ..