https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 시간도 시간인데 메모리 제한이 8mb이다. 일반적으로 값을 입력받아서 이걸 배열에 저장해서 다른 정렬방법을 사용하면 배열에 저장하고 새로운 배열 만들고 그러는데 메모리가 너무 초과된다. 그러던 중 알아보다가 counting sort, 이번 알분에서 배운 알고리즘을 사용할 수 있는 문제라 사용해보았다. 우선 counting sort는 말 그대로 해당 숫자가 몇 개인지 세는 것이다. 예를 들어 내가 5개를 입력한다 가정..
https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 사고과정1) 브루트포스 알고리즘, 즉 모든 경우의 수를 다 생각해서 코딩했다. 입력 받은 두 수가 같으면, 최대공약수와 최소공배수는 한 수일 것이고 만약 두 수가 서로소라면, 최대공약수는 1이고 최소공배수는 두 수의 곱인 경우를 따로 조건문으로 처리했다. #include using namespace std; int main() { std::cin.tie(NULL); std::ios::sync_with_stdio(false); int a, b; cin >> a >>..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 사고과정) 우선 d(n)을 만드는 과정의 함수를 구현해야한다. 이건 n + n의 각 자리를 더하면 되니 간단함. 문제는 해당 조건에 맞는 셀프넘버를 출력시킬 것인가이다. 생각했던 방법은, d(n)을 n이 1부터 쭉 반복한다. 그러면서 d(n)이 10000이하까지일때까지 반복하면서 해당 d(n)의 값과 대응하는 인덱스의 배열에 값이 있다는 뜻의 '1..
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 자연수 N이 최대려면, 1+2+3+.... 이렇게 가장 작은 수부터 시작해서 더해야한다. 예제가 19여서 생각을 해보니, 1+2+3+....19가 190이다. 저 19를 200에 맞추기 위해 29로 바꿔주면 끝이다. 즉, 이렇게 더하나가다가 N보다 커지면 마지막 수만 바꿔주면 된다. #include using namespace std; int main() { long long S; cin >> S; long long sum = 0; int count = 0; long long i = 1; while (true) {..
https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 사고과정) abca 가 있다고 하면, a의 경우 아까 나왔는데 마지막에 또 나와버려서 그룹단어가 아님 그걸 활용해, 알파벳 수를 담는 배열을 만들고, 한글자씩 옆에랑 서로 비교하면서 다르면 글자수를 더하고 그러다가 글자수가 2 이상이면 중복되었다는 소리이므로 그룹단어가 아님. 문자열을 입력받고 (str[i] != str[i+1]) 이런 식으로 비교를 할텐데, 그렇게..
https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 6과 9를 하나의 숫자로 보는 것이 핵심이다. #include #include using namespace std; int main() { string input; cin >> input; int length = input.length(); char arr[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; int result[10] = { 0, }; for (int i = 0; i < length; i++) { for (int j = 0; j ..
https://www.acmicpc.net/problem/1246 1246번: 온라인 판매 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다. www.acmicpc.net 사고과정) (가격금액 * 구매 가능한 사람수 )가 가장 큰 값을 찾으면 된다. 입력받은 가격들 중 가장 큰 값을 max_element로 찾고, i = 1 ~ max_element까지 반복하면서 구매가능한 사람수를 조건문으로 걸고 곱한 합을 비교하면 된다. 예외사항으로, 사람수가 계란수보다 많으면, 예를 들어 가능한 사람수는 5명이라 count가 5는 되지만, 계란 수는 4라 오류가 난다. 그렇기 ..
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 처음에 무슨 소리인가 싶어서 5분간 예제 보면서 고민하다가 내린 결론은 간단했다. 같은 문자가 쭉 가다가 한번 다른 문자가 나오면 그 횟수를 카운트해서, 가장 적은 횟수를 출력해주면 되는 거였음. #include #include using namespace std; int main() { string input; cin >> input; int zero = 0, one = 0; for (int i..
