띵동

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..

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

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 이전에 작성한 백준 1927번 최소 힙 문제와 거의 똑같다. 최소 힙 문제는 오름차순 정렬을 위해 greater를 사용하여 큐를 생성했지만, 이 문제는 큐를 생성할 때 greater만 지워주면 된다. priority_queue q; 이러면 숫자가 클수록 우선순위가 높은 우선순위 큐가 만들어진다. 즉, 내림차순으로 정렬된다. #include #include using namesp..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 입력하는 정수가 자연수라면 배열에 그 정수를 추가하고, 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 제거하는 문제이다. 작은 데이터일수록 우선순위가 높은 우선순위 큐를 만들기 위해 priority_queue q; 로 큐를 생성했다. 큐는 앞에서 원소를 빼기 때문에 가장 작은 원소를 출력 후 삭제하려면 오름차순 정렬을 해야되므로 오름차순으로 정렬해주는 greater를 추가..

백준 11050번은 이항 계수를 구하는 문제이다. https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 공식을 보면 팩토리얼을 사용하는 것을 볼 수 있다. 따라서 이 문제는 팩토리얼 알고리즘만 알면 쉽게 풀 수 있다. #include using namespace std; int factorial(int num) { if (num == 0 || num == 1) { return 1; } else return num * factorial(num - 1); } int main() { ios::sync_with_stdio..