baaaarking dog 님 알고리즘강의 백트래킹파트를 참고하여 작성한 글입니다. 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 백트래킹이란?? 현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 가지치기처럼 그러셔 모든 경우의 수를 따라 그려볼 수 있다 (상태공간트리 라고도 불린다) arr는 m개 만큼 원소를 담을 배열 isused는 1~N까지의 숫자가 사용되었는지 안되었는지 확인하는 배열 사용 - True..

baaaaarking dog님 알고리즘 강의를 참고한 내용입니당 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 설명 재귀 문제를 풀때 절차지향적 사고로 풀기보단 귀납적 사고로 푸는것이 좋다. (절차지향적 사고로 생각하려다가 머리속이 꼬일 수 있기때문에) 그럼 귀납적 방법이란게 뭐냐?? 1번 도미노가 쓰러진다 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. 이 문제는 b가 최대 21억 가까이 되기때문에 시간초과가 발생할 것이다. 이 사진의 로직을 이용하면 1승을 계산할 수 있다. k승을 계산했으면 2..

문제 https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 코드 #include #include #include #include using namespace std; bool com(string& a, string& b) { int sum_a = 0; int sum_b = 0; if (a.size() != b.size()) //1. 길이가 다르면 짧은것 먼저 return a.size() < b.size(); for (int i = 0; i < ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 설명 이 문제는 DP로 풀 수 있다. 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 이 세가지 과정을 거쳐 문제를 풀 수 있다. 1. 테이블 정의하기 D[i]= i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 D[12] =? D[1]부터 D[11]까지의 값을 다 알고 있다고 가정하면 1, 2, 3, ..., 11을 1로 만들기 위한 최소 횟수를 다 알고 있다고 하면 이런 상황에서 D[12]를 구하는 방법은 12에서 할 수 있는 연산을 생각하면 된다. D[4], D[6..

문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 설명 처음엔 이 문제가 이해가 잘 안갔다. 설명해보자면 만약에 18짜리 중량인 물체가 있다면 버틸수 있는 최대 중량이 6인 로프 3개로 물체를 들 수 있다. 반대로 위에서 말한 6짜리 로프 3개로는 로프 1~3개를 이용하여 6, 12, 18 짜리 중량인 물체를 들수 있는데 그 중에 최대 중량은 18이기 떄문에 답은 18이 된다. 로직을 생각해보면 만약에 버틸 수 있는 최대중량이 1,..