⭐ 코딩테스트
[백준 11279번 C/C++] 최대 힙
[백준 11279번 C/C++] 최대 힙
2023.07.03[백준 11279번 C/C++] 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 해결전략 Priority Queue 우선순위 큐 코드 #include #include using namespace std; priority_queue pQ; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; long long input; ci..
[백준 10866번 C/C++] 덱
[백준 10866번 C/C++] 덱
2023.07.01[백준 10866번 C/C++] 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 해결방안 deque 코드 #include #include #include using namespace std; deque DQ; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, num; string input; cin >> n; for (int i=0; ..
[백준 2805번 C/C++] 나무 자르기
[백준 2805번 C/C++] 나무 자르기
2023.06.27목차 [백준 2805번 C/C++] 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 해결전략 이분탐색 코드 #include #include #include using namespace std; int n, cnt; long long m, maxHeight=0; vector v; long long Cal(int x) { long long h = 0; if (x == 0) return h; for..
[백준 1654번 C/C++] 랜선 자르기
[백준 1654번 C/C++] 랜선 자르기
2023.06.26목차 [백준 1654번 C/C++] 나이순 정렬 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 해결전략 이분탐색, 매개 변수 검색 이진 탐색 알고리즘을 사용하여 가능한 가장 긴 랜선 길이를 찾는다. 시간초과 - 처음 시도한 코드 #include using namespace std; int k, n, cnt; long long sum, l; int kin[10001]; int main(){ ios_base::sync..
[백준 10814번 C/C++] 나이순 정렬
[백준 10814번 C/C++] 나이순 정렬
2023.06.24목차 [백준 10814번 C/C++] 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 해결전략 vector에 구조체 변수(struct Tag)를 넣은 후 정렬한다. 이 때 bool Compare 함수를 만들어 원하는 모양으로 정렬해준다. 주의할점 vector v에 값을 넣어줄 때는 v.push_back( Tag { 값1, 값2, 값3 } ) 과 같은 모양으로 넣어줘야 한다. Tag 뒤의 값들은 중괄호 { }를 사용해서 넣어주어야 한다. ..
[백준 10816번 C/C++] 숫자 카드 2
[백준 10816번 C/C++] 숫자 카드 2
2023.06.23[백준 10816번 C/C++] 숫자 카드 2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 해결전략 map과 set은 중복값을 허용하지 않는다. 따라서 이 문제에서는 unordered_map을 사용하였다. unordered_map에 사용되는 헤더는 #include 이다. 주어진 카드 숫자를 인덱스 번호로 사용하는 unorder_map을 만든다. unordered_map unMap; unMap[input]에..
[백준 1021번 C/C++] 회전하는 큐
[백준 1021번 C/C++] 회전하는 큐
2023.06.22[백준 1021번 C/C++] 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 해결전략 deque 코드 #include #include using namespace std; int n, m, input, cnt=0; deque dq; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i input; in..
[백준 2331번 C/C++] 반복수열
[백준 2331번 C/C++] 반복수열
2023.06.22목차 [백준 2331번 C/C++] 반복수열 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 해결전략 구현 코드 #include #include using namespace std; int a, p, nextNum, i=0, cnt=0; int box[10000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> a >> p; box[0] = a; while(true) { cnt++; nextNum = 0; while (a > 0) { nextNum += pow(a % ..
[백준 1931번 C/C++] 회의실 배정
[백준 1931번 C/C++] 회의실 배정
2023.06.21목차 [백준 1931번 C/C++] 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 해결전략 Greedy Algorithm 탐욕 알고리즘 첫번째 풀이 - 시간 초과 #include #include #include using namespace std; int n, a, b, answer, maxDay = -1, maxValue = -1; struct Data { int start, end; Data(int a, int b) { start = a; end = b; } bool operator> n; for (int i = 0; i < n; i++) {..
[백준 10844번 C/C++] 쉬운 계단 수
[백준 10844번 C/C++] 쉬운 계단 수
2023.06.20목차 [백준 10844번 C/C++] 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해결전략 Dynamic Programming (DP) 동적계획법 코드 #include using namespace std; int dp[101][11]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i=1; i
[백준 1966번 C/C++] 프린터 큐
[백준 1966번 C/C++] 프린터 큐
2023.06.17[백준 1966번 C/C++] 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 해결전략 Queue Priorty Queue Queue에 make_pair로 인덱스 번호와 값을 동시에 담는다. 값이 정렬되어 들어가는 PriorityQueue와 Queue를 비교하며 cnt을 한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.t..
[백준 9663번 C/C++] N-Queen
[백준 9663번 C/C++] N-Queen
2023.06.17[백준 9663번 C/C++] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 Backtracking 백트래킹 코드 #include using namespace std; int n; int col[15]; int answer = 0; bool isPossible(int level) { for (int i = 0; i < level; i++) { // 같은 열에 있는 경우 if (col[i] == col[level]) return fals..