띵동

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 이 문제는 최대 중량을 구하는 방법을 아는 게 관건인 것 같다. 최대 하중이 제일 작은 밧줄의 값 * 밧줄의 개수를 통해 최대 중량을 찾아야 한다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, ans = 0; cin >> n; vect..

https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 입력값으로 1과 자기 자신을 받지 않기 때문에 약수에서 최솟값과 최댓값을 곱해주면 된다. 입력받은 약수를 벡터에 집어넣고 정렬한 후 벡터의 맨 앞 값과 맨 마지막 값을 곱해주었다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, num; i..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 처음에 이중 우선순위 큐라는 제목을 보고 priority_queue를 사용해 코드를 짜느라 많은 시간을 소비했다. 우선순위 큐보다는 multiset을 사용하면 더 간단하게 풀 수 있는 것 같다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t, k, n; cha..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 이 문제는 벡터와 이중 for문을 사용하여 풀었다. vector v를 활용하여 키와 몸무게를 한 쌍으로 입력하여 벡터에 넣은 후 이중 for문으로 v.first와 v.second 값을 비교했다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, h, w..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이 문제는 벡터와 이진 탐색을 사용해 풀었다. 헤더파일에 binary_search STL이 정의되어 있기 때문에 이것을 사용하면 쉽게 풀 수 있다. n개의 정수를 벡터에 저장하고 이진 탐색을 위해 정렬한 후, m개의 정수를 입력하면서 이진 탐색을 하여 그 정수가 벡터에 존재하는지 알아내는 것이다. #include #include #include us..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 이 문제는 벡터와 이진 탐색을 통해 풀었다. 듣도 못한 사람의 명단을 벡터(v)에 저장한 후, 이진 탐색을 하기 위해 정렬하고 보도 못한 사람의 이름(s)을 입력받으면서 해당 이름이 벡터 v에 있는지 확인하기 위해 이진 탐색을 사용했다. binary_search(v.begin(), v.end(), s) 이진 탐색 STL은 해당 값이 존재하면 1을 리턴하므로 만약 보도 못한 사람의 이름(s)이 벡..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net deque는 Double Ended Queue의 줄임말로 두 개의 큐를 가지고 있는 자료구조이다. 이것은 앞/뒤의 데이터 삽입과 삭제를 할 수 있다. deque는 C++ STL에 정의되어 있기 때문에 이라는 헤더 파일을 include 하여 풀면 쉽다. 여기서 주의할 점은 문제에 나온 pop_front와 pop_back 명령어가 덱에서 해당하는 정수를 빼고, 그 수를 출력한다는 것이..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net queue는 C++ STL에 정의되어 있기 때문에 이라는 헤더 파일을 include 하여 풀면 쉽다. 여기서 주의할 점은 문제에 나온 pop 명령어가 큐에서 가장 앞에 있는 정수를 빼고 그 수를 출력한다는 것이다. pop()을 사용하면 큐의 front 데이터를 삭제할 뿐 출력하지 않는다. 따라서 문제 속 pop 명령어대로 실행하려면 front()을 사용해 최상위 데이터를 반환한 다..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net stack은 C++ STL에 정의되어 있기 때문에 이라는 헤더 파일을 include 하여 풀면 쉽다. 여기서 주의할 점은 문제에 나온 pop 명령어가 스택에서 가장 위에 있는 정수를 빼고 그 수를 출력한다는 것이다. pop()을 사용하면 스택의 top 데이터를 삭제할 뿐 출력하지 않는다. 따라서 문제 속 pop 명령어대로 실행하려면 top()을 사용해 최상위 데이터를 반환한 다음..

https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이전에 작성한 좌표 정렬하기와 매우 비슷하다. 이 문제 역시 x 좌표와 y 좌표를 한 쌍으로 묶기 위해 pair형 벡터를 생성하여 문제를 풀었다. 벡터의 첫 번째 인자에는 x 좌표를, 두 번째 인자에는 y 좌표를 넣었다. y 좌표를 오름차순으로 정렬하고, 만약 y 좌표가 같으면 x 좌표가 증가하는 순서로 정렬하는 함수를 만들면 된다. #in..