본문 바로가기

분류 전체보기

 (386)
[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:/..
[c++] 백준 15649 N과 M (1) 백준 단계별로 풀어보기 [백트래킹] N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [풀이] dfs 완전 탐색 기법을 이용해서 풀 수 있는 백트래킹 문제이다. 1~n 까지의 자연수 중에서 길이가 m인 수열을 모두 구해 출력해야 하는데, visited[] bool 배열을 선언해 방문했는지 여부를 체크하고 방문하지 않았으면 list 배열에 해당 숫자를 저장한다. count가 m과 같아지면 m 길이의 수열을 만족하는 것이므로 출력을..
[c++] 백준 11047 동전 0 백준 단계별로 풀어보기 [그리디 알고리즘] 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net [풀이] n개의 종류의 동전을 적절히 이용해서 가치의 합이 k가 되게하는 최소 동전의 개수를 구하는 문제이다. 오름차순으로 동전의 가치값을 입력했고, 최소 개수를 구하기 위해서는 가장 큰 가치값부터 시작해서 k를 채워나가면 된다. 따라서 그리디 알고리즘에 해당하고, k / val[n..
[c++] 백준 11399 ATM 백준 단계별로 풀어보기 [그리디 알고리즘] ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net [풀이] 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값은 Pi가 가장 작은 사람 순으로 돈을 인출할 때 구할 수 있다. 따라서 그리디 알고리즘이 적용되는 문제이므로 입력받은 Pi를 오름차순으로 정렬 후 누적합을 구하여 구할 수 있다. [코드] #include #include int main() { int num; std::cin >> num; int* wait_time ..

티스토리툴바