QQ의 다이어리

문제 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 풀이 브루트포스 알고리즘으로 푸는 문제로, 1부터 10000까지를 돌면서 변수 res에 각 자릿수를 더해준다. 어떤 수에 %10 연산을 해주면, 일의 자리수를 구할 수 있으므로, 해당 수가 0이 될 때까지 모듈러 연산을 반복한다. 그렇게 해서 나온 결과를 배열에 넣어주면 배열에는 셀프 넘버를 제외한 수들은 true, 셀프 넘버는 false 값..

문제 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 입력받은 수의 한 자리씩 살펴보기 위해 %10 연산을 하며 각 자릿수를 배열에 저장한다. 이때 9와 6은 동일하다고 본다. 따라서 입력 받은 수의 모든 자릿수를 확인한 후에 6의 개수는 2로 나누어준다. 마지막으로 for 문을 돌면서 count 된 수 중 가장 큰 수를 변수에 저장해서 출력한다. 코드 #include using namespace std; int max(int a, int b) { return (a>=b)?a:b; } int n; int cnt[9]; int main()..

문제 https://www.acmicpc.net/problem/13015 13015번: 별 찍기 - 23 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 풀이 단순 구현 문제로, 가운데 줄을 제외한 부분이 반복됨을 이용해서 반복되는 부분을 함수로 구현했다. 규칙은 직관적으로(하드코딩ㅎ) 찾아냈고 숫자를 입력해보며 조건들을 추가했다. 각 줄마다 공백 - 별 - 공백 - 별의 구조이므로 각 부분을 for문을 돌면서 출력한다. 코드 #include using namespace std; int n; void printstar(int i) { for(int a=0;a

문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 에라토스테네스의 체를 이용하여 소수를 찾는다. 2부터 시작해서 소수들의 배수는 소수가 아니기 때문에 2의 배수를 모두 false로 만들고, 3의 배수를 false로 만드는 과정을 반복하며 소수만 true로 남긴다. 주의할 점은 소수가 아닌 수들을 false로 처리해야 하므로, 처음에는 모든 수를 true로 초기화해야 한다. 코드 #include using namespace std; void Eratos(int m, i..

문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 key 값이 오름차순으로 자동 정렬되는 map을 사용했다. 일반 map의 경우 중복이 제거되므로, 중복이 제거되지 않는 multimap으로 문제를 해결했다. map이 비어있지 않고, 0이 입력되면 map의 맨 처음에 있는 값을 출력한 후, 그 값을 지우고, map이 비어있는데 0이 입력되면 0을 출력한다. 입력값이 0이 아니라면 map에 입력받은 수를 추가한다. 코드..

문제 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 브루트포스로 풀면 되는 문제. 입력받은 수가 100 이하, 즉 2자리수라면 어떤 수든 한수이므로 n을 리턴해주면 되고, 100 이상인 수는 각 자리수를 변수에 저장한 후, 그 차이가 같으면 결과 변수를 증가한다. 코드 #include using namespace std; int func(int n) { int res = 99; for(int i=110; i>n; int res = 0; if(n

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 1~n까지의 수가 담긴 큐에서 k번째의 수를 반복적으로 제거하면 된다. 하지만 중간에 있는 값을 제거하는 것은 쉽지 않으니 큐를 사용한다. 1) k-1번을 반복하며 앞의 수를 빼서 맨 뒤에 넣는다. 2) 그 후에 k번째의 수를 제거한다. 이 과정을 큐에 남은 수가 없을 때까지 반복한다. 코드 #include #include using namespace std; int main() { queue q; int a,b; cin>>a>>b; for(int i=1; i

문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 풀이 백준 9012번 문제와 유사하지만 이 문제는 (), [] 2개의 괄호가 있고, 각 괄호가 감싸는 문자열 또한 짝이 맞아야 한다. ([abc)]와 같은 경우는 안 된다. 따라서 현재 스택의 맨 위에 있는 괄호가 ( 인지 [ 인지 확인하는 것이 필요하다. 1) 괄호를 입력받으면 스택에 추가한다. 2) 닫는 괄호이면서, 스택이 비어있지 않고, '입력받은 괄호 == 스택의..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 탐색하려는 배열에 중복이 있다면 target이 되는 수를 찾아내도, 이 수가 몇개 있는지는 알아낼 수 없다. 따라서 algorithm 헤더의 upper/lower_bound를 사용하면 target이 되는 수들의 마지막 주소와 시작 주소를 얻을 수 있다. 따라서 upper_bound - lower_bound를 계산하면 총 개수도 계산할 수 있다. 코드 #..

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이분탐색을 이용하여 수를 찾는 문제이다. 탐색하려는 배열을 정렬한 후, 찾으려는 수가 배열의 중간값보다 크면 중간값 이전 값들은 고려하지 않고, 배열의 중간값보다 작다면 중간값 이후의 값들은 고려하지 않는다. 계속 범위를 줄여가다가 1) 중간값과 찾으려는 수가 일치하거나, 2) 배열의 크기가 0이 되어 끝을 가리키는 인덱스가 처음을 가리키..