민우의 코딩노트

[문제] https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net [풀이] 스택에 넣을때 순감소 수열(Ex 10 9 8 ..)이 되도록 넣어야 한다. 중복 되는 경우(Ex 2 2 2)를 고려해야 한다. 1. 스택의 top()보다 지금 값이 큰 경우 순감소 수열이 되어야 하므로, 스택의 second 값인 중복 누적 값을 더하고, top()을 pop 한다. 2. 스택의 top()보다 지금 값이 같은 경우 순감소 수열이 되어야 하므로,..

[문제] https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net [풀이] STL 스택을 이용하는 문제이다. 입력된 정수가 0일 경우에는 가장 최근에 쓴 수를 지우므로, 스택의 empty()를 이용하여, 값이 들어있는 지 확인후, pop() 함수로 삭제하면 된다. 입력된 정수가 0이 아닌 경우에는 원소를 스택에 집어넣기 위해서 push() 함수를 이용하면 된다. 합계 결산은 empty()를 이용하여 값이 있는지 확인하고..

[문제] https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net [풀이] 기본적인 스택 풀이 문제이다. C++ STL 중 하나인 스택의 개념과 사용법을 알아보자. 1. 스택 스택(Stack)은 대표적인 LIFO(Last In First Out) 구조이다. 즉, 제일 마지막에 넣은 데이터가 처음으로 빠져나오는 구조를 말한다. C++ STL 사용법 > 스택 선언 stack 이름으로 스택 선언하기 stack stack; > 스택에 데이터 ..

[문제] https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [유형] 스택 [코드] #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; stack S; vector v; int index = 1; while(n--) { int t; cin >> t; if(index == 1) { S.push({t, index}); v.push..

[문제] https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net [코드] #include using namespace std; int arr[201]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,v; cin >> n; for(int i=1; i> t; arr[t+100]++; // 만약 t가 -100 -> 0, t가 0 -> 100, 100 -> 200 } cin >> v; cout

[문제] https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i > n; int sum =0; for(int i=1; i> t;..

[문제] https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [분류] 배열 [코드] #include using namespace std; int arr[10]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int sum = 1; int first = 0; while(n > 0){ int k = n%10; if(k == 6 || k == 9){ if(arr[6] >= arr[9]) { arr[9]++; } else arr[6]++; } else { arr[k]++; } n/..

[문제] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [풀이] 그리디 알고리즘 [코드] #include using namespace std; int n; pair s[100005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> s[i].second >> s[i].first; } sort(s, s+n); int ans=0; int t=0; for(int i=0; i s[i].second) continue; ans++; t = s[i].first; } cout

[문제] https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net [풀이] 그리디 알고리즘 [코드] #include using namespace std; int n; int w[100005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> w[i]; sort(w, w+n); int ans=0; for(int i=1; i

[문제] https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net [풀이] 그리디 알고리즘 [코드] #include using namespace std; int a[105], b[105]; int n; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> a[i]; for(int i=0; i> b[i]; sort(a, a+n); sort(b, b+n); int..