본문 바로가기

알고리즘 공부 및 문제 풀이

 (317)
[c++] 백준 1874 스택 수열 백준 단계별로 풀어보기 [스택] 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net [풀이] 1부터 n까지의 수를 스택에 push 하고, push 할 때마다 '+'를 부호 배열에 저장한다. 처음 수열을 입력받은 배열의 수와 스택의 top이 일치하는 동안(또한 스택이 empty가 아닌 동안) 스택을 pop하고 '-'를 부호 배열에 저장한 후 수열 배열 인덱스..
[c++] 백준 10773 제로 백준 단계별로 풀어보기 [스택] 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net [풀이] 0이 입력되면 스택에서 pop을 하고, 그 외의 수는 스택에 push를 한다. 입력이 끝나면 스택에 있는 수를 모두 더해준 뒤 출력한다. [코드] #include #include #include #include int main() { int k, num, sum = 0; std::stack s; std::cin >> ..
[c++] 백준 2609, 1934 최대공약수와 최소공배수, 최소공배수 백준 단계별로 풀어보기 [정수론 및 집합론] 최대공약수와 최소공배수, 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net [풀이] 처음 문제는 num을 증가시켜가며 주어진 두 ..
[c++] 백준 1541 잃어버린 괄호 백준 단계별로 풀어보기 [그리디 알고리즘] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net [풀이] 수식에 -가 등장하면 그 다음부터 괄호를 쳐서 계속 뺄셈을 만드는 것이 결과값을 최소로 만드는 방식이다. 따라서 flag를 두어 - 가 등장하면 flag를 true로 바꾸어 값의 뺄셈을 하도록 하고, 그렇지않으면 값을 더하도록 한다. 계속 숫자가 나오면 자릿수를 키워야하므로 10을 곱해 누적시킨다. [코드] #include #..
[알고리즘] 동적프로그래밍(Dynamic programming) 1. 동적프로그래밍(Dynamic programming) : 큰 문제를 작은 부문제로 나누어서 풀어나가되, 이미 계산했던 연산이라면 다시 하지 않고 기록되어 있는 값을 가져와서 진행하도록 하는 방식이다. 예를 들어, 피보나치 수열을 재귀를 이용해서 풀면 다음과 같다. #include int fibo(int num) { if(num == 1) return 1; else if( num ==2 ) return 1; else return fibo(num-1)+fibo(num-2); } int main() { int num; std::cin >>num; std::cout 원점 -> 목표점) 성능 : 동적프로그래밍은 단방향적 특성으로 인해 효율적임 / 분할통치는 분할 회수 및 중복 연산의 수행이 요구됨. 4. 예제..
[c++] 백준 1037 약수 백준 단계별로 풀어보기 [정수론 및 집합론] 약수 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net [풀이] 1과 자기 자신을 제외한 어떤 수 n의 진짜 약수가 주어졌을 때 n의 값을 구하는 문제이다. 배열에 약수를 모두 입력 받은 후 오름차순으로 정렬하면, 가장 첫번째와 마지막 수의 곱이 n이 된다. [코드] #include #include int main() { int num; //약수 개수 std::cin >> num; int* ar..
[c++] 백준 5086 배수와 약수 백준 단계별로 풀어보기 [정수론 및 집합론] 배수와 약수 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net [풀이] m % n == 0이면 n이 m의 약수이다. 반대로 n % m == 0이면 n이 m의 배수이다. [코드] #include #include int main() { int n, m; while (true) { std::cin >> n >> m; if (n == 0 && m == 0) return 0; if (m % n == 0) std::cout
[c++] 백준 15650, 15651, 15652 N과 M (2), (3), (4) 백준 단계별로 풀어보기 [백트래킹] N과 M (2), (3), (4) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https:/..

티스토리툴바