분류 전체보기
-
[백준/BOJ] 2164번 카드2 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 01:11
www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 분류는 큐를 이용하는 걸로 되어있는데, 덱을 이용해서 해결했습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, answer; cin >> n; deque dq; for(int i = 1; i 1) { dq.pop_front(); dq.push_back(dq..
-
[백준/BOJ] 4949번 균형잡힌 세상 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 00:41
www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 스택을 이용하는 문제 닫힌 괄호 ')' 혹은 ']'를 만났을 때, 스택이 비어있거나 스택의 top이 짝이 아니라면 무조건 답이 될 수 없으므로 flag 변수를 false로 바꾸고 break 해줘야 합니다. 또한 모든 탐색이 끝나고, 스택에 원소가 남아있으면 이것 역시 답이 될 수 없으므로 flag를 flase로 바꿔주는 것을 주의해야합니다. #include #include using namespa..
-
[백준/BOJ] 10773번 제로 (C++)알고리즘 문제풀이/백준 2021. 1. 7. 23:37
www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 기초 스택 문제 #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int k; cin >> k; stack s; while(k--) { int n; cin >> n; if(!s.empty() && n == 0) s.pop(); else s.push..
-
[백준/BOJ] 3273번 두 수의 합 (C++)알고리즘 문제풀이/백준 2021. 1. 7. 23:12
www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 정렬 + 투포인터 유형의 문제 수열을 입력받아 정렬한 후, 두개의 포인터를 각각 인덱스 0번과 n - 1번에 가리키게 한 후 다음과 같이 분기를 둡니다. 1. 둘의 합을 x와 비교하여 같으면 head와 tail 모두 1씩 증가 후, answer 1 증가 2. 둘의 합이 x보다 크면 tail 1 감소 3. 둘의 합이 x보다 작으면 head를 1 증가 #inc..
-
[백준/BOJ] 14225번 부분수열의 합 (C++)알고리즘 문제풀이/백준 2021. 1. 5. 23:58
www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 1182번 문제에서 조금 심화된 브루트 포스(완전 탐색) 문제입니다. DFS를 이용해 만들어 낼 수 있는 부분수열의 합을 모두 구하고 이를 배열에 체크합니다. 모든 탐색이 끝난 후, 체크 배열에서 false인 첫 인덱스를 출력하고 종료합니다. 이때, 배열 범위안에 false인 인덱스가 없다면, 가장 큰 인덱스에서 +1을 한 값을 출력하면 됩니다..
-
-
[백준/BOJ] 2003번 수 들의 합 2 (C++)알고리즘 문제풀이/백준 2021. 1. 4. 13:10
www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터를 이용해 해결할 수 있는 문제입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, answer = 0; cin >> n >> m; vector v(n); for(int i = 0; i < n; i++) { ..
-
[백준/BOJ] 1644번 소수의 연속합알고리즘 문제풀이/백준 2021. 1. 4. 13:04
www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학 + 투 포인터 문제였습니다. 새롭게 알게된 점 연속된 값들을 이용하여 풀어나가는 문제에서 한 배열에 포인터 변수 2개를 두어 탐색하는 투 포인트 알고리즘을 쓸 수 있다. 이때 투 포인트 알고리즘의 시간복잡도는 O(N)이다. 에라토스네스의 체 알고리즘을 이용하여 소수를 모두 구해 prime 벡터에 값을 넣어 준 후, prime 벡터에 head와 tail 2개의 포인터 변수를 둬서 투 포인터 탐색을 통해 n을 만들 수 있는 경우를 모두 구하면 됩니다. #include #include using namespace std; void..