QQ의 다이어리

문제 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이 되어 끝을 가리키는 인덱스가 처음을 가리키..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 입력받은 문자열을 돌다가 1) 여는 괄호를 만나면 stack에 push한다. 2) stack이 비어있지 않은 상태에서 닫는 괄호를 만나면 pop 한다. 3) stack이 비어있는 상태에서 닫는 괄호를 만나면 false 입력받은 문자열을 다 돈 후에도 false 가 되지 않고 stack이 비어있다면 true를 반환한다. 코드 #include #include ..