𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

문제 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scoville의..

문제 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. 정렬을 이용하여 풀 수 있는 문제. 수를 입력을 받은 뒤, sort 함수를 이용하여 정렬한 뒤 K번째 수를 출력하면 되는 간단한 문제다. 코드 #include #include #include using namespace std; int main(void) { int n, k; scanf("%d %d", &n, &k); vecto..

문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출력 첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다. 정렬을 이용하여 풀 수 있는 문제. 카드에 적혀있는 숫자와 그 숫자 카드의 장수를 매치시키기 위해 map이라는 자료구조를 사용하였다. iteration을 ..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 정렬을 이용한 문제. ..인데 시간 제한이 3초고 메모리 제한이 8MB고 입력받을 수 있는 수의 개수 범위가 [1, 10000000] 이다. 즉 다른 정렬 문제처럼 수를 모두 배열에 입력받은 뒤, STL 함수나 일반 정렬 알고리즘을 통해 정렬하는 방식으로 풀지 말라는 뜻이다. 대신 수의 범위가 [1, 10000]이기 때문에 1부터 10,000까지의 인덱스를 표시할 수 있..

문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 입력 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 정렬을 이용하여 푸는 문제. 11650번 좌표 정렬하기 와 동일하게 풀면 된다. 병합 정렬을 사용하여 풀었고, y좌표가 증가하는 순으로 - y좌표가 같으면 x좌표가 증가하는 순으로 정렬해야되기 때문에 11650번 문제 풀때랑 살짝만 다르게 ..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 정렬을 이용하여 푸는 문제. 병합 정렬을 사용하여 풀었고, x좌표가 증가하는 순으로 - x좌표가 같으면 y좌표가 증가하는 순으로 정렬해야되기 때문에 조건문을 하나 더 붙였다. 코드 #include void merge(int** sorted,..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 정렬 문제. 처음에 퀵 정렬로 풀었으나 제출 전에 쎄한 느낌이 들어 구글링을 해봤더니 퀵정렬은 최악의 경우 시간복잡도가 O(n2)로, 시간초과의 위험이 있다고 하더라.. 그리하여 병합 정렬을 구현하여 풀었다. 병합정렬 : 🔗 코드 #include void merge(int* sorted, int* arr, int begin, int mid..

2. 퀵 정렬 ; Quick Sort 2.1 개념 분할 정복 알고리즘을 이용한 정렬 방법 중 하나로, 병합 정렬과 마찬가지로 전체 집합을 작은 크기의 부분집합으로 나누어 정렬을 수행한 뒤 다시 합치는 정렬 방법을 의미한다. 병합 정렬의 핵심 연산은 병합인 데 비해 퀵 정렬의 핵심 연산은 분할이다. 퀵 정렬은 다음과 같은 단계로 진행된다. 1. 분할(Divide) : 정렬할 집합을 기준값을 중심으로 두 부분집합으로 분할 2. 정복(Conquer) : 부분집합 내에서 기준값의 정렬 위치 선정 이 때 사용하는 기준값을 피봇(Pivot) 이라고 하는데, 첫 번째 원소 / 마지막 원소 / 가운데 원소 등 임의의 순서의 값을 정하면 된다. 이렇게 정한 기준값을 중심으로 왼쪽(L)과 오른쪽(R) 부분집합으로 나누어 ..

1. 병합 정렬 ; Merge Sort 1.1 개념 분할 정복 알고리즘을 이용한 대표적인 정렬 방법 중 하나로, 여러 정렬된 집합들을 병합하여 하나의 정렬된 집합으로 만드는 정렬방법을 의미한다. 병합 정렬은 다음 세 가지의 단계를 통해 진행된다. 1. 분할(Divide) : 큰 집합을 부분집합으로 분할 2. 정복(Conquer) : 부분집합 내의 원소 정렬 3. 결합(Combine) : 정렬된 부분집합들을 하나의 집합으로 정렬하여 결합 원리만 생각하면 복잡해 보이지만, 그림과 함께 보면 쉽게 이해할 수 있다. 정렬되지 않은 집합 A는 다음과 같이 구성되어있다. A = { 3, 8, 7, 2, 5, 1, 4, 6 } 집합 A를 오름차순으로 정렬한다고 가정을 해보자. 병합 정렬하는 과정은 아래 그림과 같다...