목록완전탐색 (14)

반갑습니다!

[프로그래머스] 단체사진 찍기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 경우의 수를 수학으로 계산하려 했는데 숫자가 작아 직접 세어도 될 것 같다는 생각이 들었다. 그래서 완전탐색으로 모든 경우에 조건을 검사하였다. 코드 #include #include #include using namespace std; // 조건 확인 bool check_rule(vector& friends, string rule) { char a = rule[0]; char b = rule[2]; char op = rule[3]; int dist = rule[4]-'0'; for (int i = 0; ..
알고리즘 문제 풀이 2020. 4. 29. 16:39
[백준] 16985 Maaaaaaaaaze

16985번: Maaaaaaaaaze www.acmicpc.net 풀이 구현이 까다로운 문제이다. 이 문제는 완전탐색으로 해결하였다. 이 문제는 크게 세가지의 구현을 해내면 풀 수 있다. 1. 5x5 크기의 판 쌓기 (Permutation) 2. 5x5 크기의 판 돌리기 3. 3차원 최단 경로 찾기 (BFS) 우선 5x5 크기의 판 쌓기는 순열을 사용해서 간단히 구현할 수 있다. 각 판의높이를 나타내는 숫자 배열 h = \[0, 1, 2, 3, 4\]가 있다고 하자. h 배열의 숫자를 정렬하는 방법은 [0, 1, 2, 3, 4]부터 [4, 3, 2, 1, 0]까지 총 120가지의 경우가 나온다. 따라서 이를 이용하면 판을 쌓는 모든 경우를 쉽게 구현할 수 있다. 이번엔 5x5 크기의 판 돌리기를 알아보자..
알고리즘 문제 풀이 2020. 4. 29. 03:13
[SWEA] 1486 장훈이의 높은 선반

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 N이 최대 20이므로 완전탐색으로 해결할 수 있다. 탐색을 하면서 값을 갱신하여 가지치기를 하여 최적화했다. 코드 #include #include using namespace std; int n, b, ans; int h[20]; void dfs(int idx, int sum) { // 탐색 중에 나온 합계가 기존에 구한 값보다 크면 종료 if (sum > ans) return; if (sum >= b) { ans = min(ans, sum); return; } for (int i = idx + 1; i < n; i++) dfs(i, sum + h[i]); ..
알고리즘 문제 풀이 2020. 4. 21. 23:20
[프로그래머스] N으로 표현

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 동적계획법으로 분류되어있지만 당장 생각나지 않고 N의 값이 작아서 완전 탐색으로 해결하였다. 풀이 DFS를 통해 N ~ NNNNNNNN 까지 생성하여 사칙연산을 반복하여 number가 될 떄까지 탐색한다. 코드 #include #include #include using namespace std; int num, ans = 9; void dfs(int N, int cnt, int cur){ if(cnt >= 9) return; if(num == cur){ ans = min(ans, cnt); return; } ..
알고리즘 문제 풀이 2020. 4. 2. 16:33
이전 Prev 1 2 3 Next 다음