연잎의 develog

13458번: 시험 감독 (acmicpc.net) 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net [문제] [해결전략] 감독관 수를 저장하는 변수 cnt선언. 각 시험장 별 응시자의 수를 담는 배열을 만들고 입력받는다. 그후 1. 각 시험장 인원수에서 총 감독관이 담당할수있는 학생수(B)를 빼주고 cnt++; 만일 인원수 > n; int* A = new int[n]; //각 시험장에 있는 응시자의 수를 저장할 배열 동적할당. for (int i = 0; ..

1316번: 그룹 단어 체커 (acmicpc.net) 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net [문제] [해결전략] : 현재 가리키고 있는 문자(p)가 이미 나온적이 있는데(a), 바로 이전문자(p-1)가 이미 나온적이 있는 문자 (a)와 같지 않다면 그 단어는 그룹단어가 아니다. [코드] #include #include using namespace std; int main() { int n; //단어의 개수 int cnt=0;// 그룹단어의 개수 int i, j, k;..

합병정렬이란? 하나의 배열을 n개의 리스트로 분할하고, 나뉜 배열들을 다시 하나의 배열로 합병시키면서 정렬시키는 방법. [원리] 일단 반으로 쪼개고나서 나중에 정렬한다. :합병정렬은 어떤 문제를 우선 작은 문제로 쪼개고 난 후 다시 조합하여 원래의 문제를 푼다는 분할 정복의 개념을 활용한다고 볼 수 있다. 우선 각 배열들을 반으로 쪼개어 조각낸다. 더이상 쪼갤수 없는 상태까지 도달하면 그제서야 하나의 배열로 다시 합병시키면서 정렬한다. 정렬하는 방법은 다음과 같다. :하나의 배열로 합병시키기위해서 i번째 인덱스와 j번째 인덱스에 있는 원소를 비교하고, 둘중 더 작은 원소를 새로운배열의 K번째 원소에 넣는다. 그리고 소진한 원소가 포함된 배열의 인덱스를 +1 해준다. 이와 같은 방식으로 둘중 하나의 배열의..

버블정렬이란? 인접한 두원소를 비교하여 왼쪽원소>오른쪽원소 라면 swap하고 가장 큰 데이터를 뒤로 보내면서 오름차순으로 정렬하는 기법 [원리] : 크기가 n인 배열에서 for문을 한번 돌때마다 arr[0] ~ arr[n-i] 중에 가장 큰값이 arr[n-i]번째에 오게됨. 1회전 -> 9가 맨오른쪽으로 이동. 2회전 ->8이 맨 오른쪽으로 이동. 3회전 -> 4가 맨 오른쪽으로 이동 ... 4회전 -> 2가 맨 오른쪽으로 이동 (정렬완료) 배열의 크기가 n이라고 했을때 n-1회전을 통해 배열의 원소를 모두 오름차순으로 정리할수있다. [코드] #include #include using namespace std; //정렬할 배열 vector arr; void bubbleSort(int n) { int cn..