Baekjoon Review

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제는 괄호의 쌍이 맞는지 확인해야한다. 이를 위해 자료구조인 스택을 사용하였다. 먼저 입력된 문자들을 스택에 집어 넣는다. 그후 스택의 top을 꺼내서 열림 괄호인지 닫힘 괄호인지 확인한다. 스택을 사용했으므로 닫힘 괄호가 먼져 있는지 확인해야한다. 이를 위해 배열에 닫힘 괄호가 있다면 요소를 채운다. 열림 괄호가 스택에서 나온다면 배열에 닫힘 괄호가 들어와 있..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 처음 문제를 보고나서 배열 탐색을 위한 알고리즘을 생각 하였다. 우선 간단하게 배열의 요소를 하나씩 순회하기 위한 반복문을 작성하였다. 이때 3개의 요소를 뽑아서 합을 구해야하기 떄문에 순회는 3개의 변수를 이용해야 한다. 블랙잭의 결과가 M에 가깝게 나와야하기 때문에 최소 값을 담을 수 있는 변수를 생성하였다. M과 현재 합의 차가 최소 값 보다 작으면 블랙잭의 ..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 이 문제는 STL의 queue를 사용하여 해결하였다. 문제에서 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 라는 힌트가 있었고, 입력 값인 N = 4인 경우 자료구조에 위에서부터 1, 2, 3, 4 순으로 들어와야한다. 1을 버리고 2를 자료구조의 가장 뒤에 넣기 위해서 queue를 사용하였다. 반복은 queue의 크기가 ..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 처음 풀었을 때 최빈 값에 대한 알고리즘이 틀렸었다. 왜 그런가 하니 두번째로 작은 값을 잘못 구한 것이였다. 최빈 값을 구할 때 만약 나온 횟수가 같으면 두번째로 작은 수를 출력하라고 하였으므로, not_first라는 bool형 플래그값을 줘서 만약 나온 횟수가 같다면 두번째로 작은 값이 저장되도록 한다. 또한 문제 풀이 과정 중 모든 테스트 케이스가 맞는데도 틀린 현상이 일어났다. 계속해서 고민과 주변인에게..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이 문제는 배열에 입력 값을 삽입한 후, sort 함수를 통해 오름차순으로 정렬한다. 이후 반복문에서 배열의 값을 출력한다. #include #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin>>N; vector arr; ..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 이 문제는 큐를 사용하였다. 이때, 배열에 우선순위를 넣고, 입력이 끝나면 정렬하여 앞에서부터 꺼내 사용했다. 큐에 넣을 요소는 구조체를 생성하여 우선 순위와 입력 순서를 저장할 수 있도록 하였다. 알고리즘으로는 큐의 앞에서부터 꺼내되, 요소의 우선순위가 배열에서 꺼낸 max 값보다 낮으면 다시 삽입하고 max값에 해당하면 max 값을 그 다음 순위로 갱신하고, 배열의 범위를 벗어나지 않는 조건하에 ..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 이 문제는 시간 제한으로 인해 어려웠던 문제이다. 처음 해결 시 소수를 구하는 함수인 isPrime(int n)을 생성하여 구하려고 하였다. 이 방법은 최대 숫자인 1000000인 경우 시간이 오래 걸리기 때문에 제한 시간을 초과하는 상황이 발생하였다. 해결 방법으로는 에라토스테네스의 체를 사용하였다. 이 방법은 배열에 2부터 N까지의 값을 넣어놓고 2의 배수나 3의 배수를 소거하는 방식이다. 예를 들어 i = 2부터 i * i..

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 이 문제는 N크기의 배열을 생성하고, 생성한 배열에 N개의 값을 집어 넣는다. 그후, M개의 수가 N크기의 배열 안에 있는지 확인하는 문제이다. 이 문제를 해결하기 위해 map을 사용하였다. map에 N개의 값을 삽입한다. 이때 value는 아무 값이나 사용해도 된다. 즉, key만 사용해서 해결하였다. M개의 입력이 map에 있는지 확인하기 위해 ..