Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/2751 #include #include #include using namespace std; int main() { long long N, num; scanf("%lld", &N); vector v; while (N--) { scanf("%lld", &num); v.push_back(num); } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) printf("%lld\n", v[i]); }

많은 정렬알고리즘이 있지만 시간이나 편의상의 이유로 문제를 풀 때는 STL에 있는 sort를 사용하는 것이 더 좋다. 그렇다면 sort함수를 쓰는 방법에 대해서 알아보자. > 일반 배열인 경우 만일 arr[100] 배열을 정렬하고 싶을 때는 sort(arr, arr + n); 이렇게 sort함수를 사용해주면 arr을 arr[0]부터 arr[n-1]까지 정렬해준다. > vector을 정렬하고싶을 때는 다음과 같이 사용하면 vector arr;sort(arr.begin(), arr.end()); 벡터에 있는 값들이 정렬된다. 좌표정렬 이렇게 단순하게 정렬하는 것 외에 두가지 요소를 모두 비교하면서 정렬을 해야하는 경우도 있다.(예를들어 여러명의 수학점수, 영어점수가 있을 때 먼저 수학점수가 높은순으로, 만약..

병합 정렬(merge sort)은 분할 정복 알고리즘을 이용해 정렬하는 알고리즘이다. 분할 정복 알고리즘(Divide And Conquer)이란? 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이나 알고리즘이다. 분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현된다. 분할 정복 알고리즘은 분할, 정렬, 결합의 3단계로 나타내지는데 병합 정렬에 3단계가 적용되는 모습은 다음과 같다. 1. 정렬하기 좋은 상태로 분할을 진행 2. 정렬하기 좋은 상태에서 정렬을 하고 3. 정렬이 완료된 조각들을 결합하여 정렬을 끝낸다. 이런 절차로 병합정렬이 이루어지는 것이다. 실제로 전체적인 과정에 대한 그림을 보이자면 다음과 같이 가장 배열의 가장 작은 단위까지 쪼개졌다가 정렬을 해가면서 올라가..

팩토리얼 0의 갯수 아마 주어진 n에 대해 n!의 0의 갯수를 구하라는 문제가 주어진다면 약수로 2와 5를 가지는 수들을 활용해야할 것 같기는 한데 구체적으로 어떻게 해야할지 몰라서 헤매는 경우가 대부분일 것이다. 하지만 거기서 생각을 조금만 발전시켜본다면 충분히 문제를 잘풀 수 있다. 일단 n!에대해 0의 갯수는 2 x 5의 조합에 의해서 생성된다. 그런데 2의 배수들은 모두 2를 약수로 가지고있기 때문에 n!은 충분히 많은 2를 가지고있고 결국은 5의 갯수에 의해 0의 갯수가 좌우된다고 생각할 수 있다. 예를들어 50!에서 0의 갯수를 구한다고 생각해보자. 5를 약수로 가진 숫자는 5 , 10 , 15 , 20 .... 50 이고 5의 갯수는 50/5 = 10이 된다. 하지만 여기서 우리가 간과한 점..

에라토스테네스의 체는 1에서 N까지 모든 소수를 구하기위해 쓰는 방법이다. 가장 작은 소수인 2부터 시작하여 N까지 소수의 배수를 모두 지우는 방식으로 진행된다. 그림을 통해서 살펴보자. 맨 처음에 소수인 2를 발견한 후 2의 배수를 모두 지운다. 그 다음 소수인 3을 발견한 후 3의 배수를 지운다 이 때 3의 배수중에 3보다 작은 수인 3*1 , 3*2에 대해서는 이미 해결이 됐기 떄문에 3*3부터 지워주면 된다. 이런 방식으로 3보다 큰 수에 대해서도 n*n부터 지워주면 된다. 이렇게 3의 배수도 지워주고 나면 다음 소수인 5가 발견되고 5*5부터 5의 배수를 지운 후 계속 같은 방법을 반복하면 N까지 모든 소수를 발견할 수 있다. 에라토스테네스의 체를 적용하는 문제를 통해 코드로 구현하는 것에 대해..

최대공약수 흔히 최대공약수는 줄여서 GCD라고 쓰며 두 수의 약수 중 가장 큰것을 일컫는 말이다. 최대공약수를 구하기 위해 가장 많이 쓰는 방법은 유클리드 호제법이다. 두 정수 a,b 그리고 a를 b로 나눈 나머지가 r이라고 할 때 a와 b의 최대공배수는 b와 r의 최대공배수와 같다는 것이다. 즉 이런식으로 동작하며 두 수를 나눈 나머지가 0이 됐을 때 알고리즘이 끝나게 된다. 결과적으로 위의 그림 기준으로는 3이 최대공배수가 된다. 재귀를 사용해 다음의 과정을 코드로 나타내보면 다음과 같다. int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } 재귀없이 보다 직관적으로 코드를 작성해보면 다음과 같다. int gcd(int a, int ..

스택을 이용해서 풀면 꽤 간단한 문제이다. 만약 주어진 문자열의 첫 문자부터 검사하면서 만약 '('가 나온다면 스택에 넣고 ')'가 나온다면 이 문자는 무조건 '('와 대응돼야 하므로 스택을 검사해 만약 스택이 비어있거나 '('가 나오지 않으면 false를 출력시키도록 하면 된다.

문제 링크 : https://www.acmicpc.net/problem/9461 정말 단순하게 규칙만 찾으면 풀 수 있는 문제이다. 길이가 memo배열에 할당시켰다고 했을 때 수를 쭉 나열해서 살펴보면 memo[i] = memo[i-1] + memo[i-5] 임을 알 수 있으며 이를 통해 memo[N]을 구하면 된다. #include #include #include using namespace std; long long memo[101]; int main() { memo[1] = 1; memo[2] = 1; memo[3] = 1; memo[4] = 2; memo[5] = 2; int T;int N; scanf("%d", &T); while (T--) { scanf("%d", &N); for (int i ..

문제링크 : https://www.acmicpc.net/problem/1699 #include #include #include #define SIZE 100001 using namespace std; int memo[SIZE]; int main() { long long N; scanf("%lld", &N); for (int i = 1; i

문제링크 : https://www.acmicpc.net/problem/2579 동적계획법으로 풀면 어렵지 않게 풀 수 있는 문제이다. 먼저 각 계단의 점수를 저장하기 위해 stair[301]을 선언하였고 계단을 올라갈 때 마다 최대 점수를 저장하기 위해 score[301][3]을 선언하였다. 여기서 score[i][0]은 그 전 계단을 밟고 i 번째 것을 안밟는 경우. score[i][1]은 그 전 계단을 밟지 않고 i번째 것을 밟는 경우. score[i][2]는 그 전 계단을 밟고 i번째 계단도 밟는 경우이다. #include #include using namespace std; long long score[301][3]; int stair[301]; int main() { int n; //계단의 수 ..