728x90 [백준/C++] 2661번: 좋은수열(G4) 문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 모든 경우에 대해 따져주지 않아도 되는 가지치기 문제 풀이 나쁜 수열에는 마지막에 어떤 숫자를 추가하더라도 나쁜 수열이다. 따라서 우리는 좋은 수열들에 대해서만 추가적으로 숫자를 붙여가며 좋은 수열인지 테스트하면 된다. *solve함수 지금까지 만든 수열이 좋은 수열일 때만 .. 2022. 1. 31. [백준/C++] 1182번: 부분수열의 합(S2) 문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 모든 상태에 대해 어떤 조건을 따져주는 문제 풀이 현재 보고있는 원소를 '포함시킨다/포함시키지 않는다' 라는 두가지 경우로 나누어 생각해보면 된다. 소스코드 #include typedef long long ll; using na.. 2022. 1. 30. [백준/C++] 15650번: N과 M (2)(S3) 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 가능한 모든 경우를 단순히 생성하는 문제이다. 재귀로 상태를 전이시켜가며 문제를 풀어보자. 풀이 처음에는 숫자를 넣을 인덱스만 인자로 전달했었다. 그렇게 하면 현재 넣을 숫자가 무엇인지 반복문을 돌면서 알아내야 한다. 따라서 필요한 상태는 현재 넣을 숫자와 현재.. 2022. 1. 30. [백준/C++] 1747번: 소수&팰린드롬(S1) 문제 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 완전 탐색 각각의 경우들을 좀 더 복잡하게 따져주는 문제이다. 보통 각 경우를 나타내는 무언가를 인수로 받아서 그 경우에 대한 테스트를 진행하는 함수를 따로 작성한다. 시간 복잡도 문제를 풀기에 앞서, 이 문제를 완전탐색 알고리즘으로 풀.. 2022. 1. 29. [알고리즘 개념정리] 6. 완전탐색/백트래킹 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 완전 탐색(Brute Force) : 모든 경우를 탐색해 가면서 무언가를 세거나 어떤 조건이 가능한 경우가 있는지 확인하는 방법 ★ 완전 탐색 문제 판별법 하나의 경우마다 따져야 할 게 명확한 경우 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 적은 경우 (N제한이 작을 때!!) ★ 완전 탐색 문제 접근법 모든 경우(상태)를 생성할 수 있는 방법을 생각한다. 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크한다. * 문제에 따라 모든 경우를 따질 필요가 없거나 각 경우에 대해 체크할 조건이 없는 등의 상황도 있다.. 2022. 1. 29. [백준/C++] 6604번: Matrix Chain Multiplication(S4) 문제 https://www.acmicpc.net/problem/6604 6604번: Matrix Chain Multiplication For each expression found in the second part of the input file, print one line containing the word "error" if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multipli www.acmicpc.net 사용한 알고리즘 2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리].. 2022. 1. 27. 이전 1 ··· 5 6 7 8 9 10 11 ··· 13 다음 728x90
