목록백트래킹 (7)

반갑습니다!

[백준] 15663 N과 M (9)

15663번: N과 M (9) boj.kr 풀이 엄청 많은 시리즈가 있는 문제이다. N개의 자연수 중에서 M개를 고르는 것은 백트래킹을 사용해서 어렵지 않게 구현할 수 있다. 하지만 이 문제에는 중복이 발생하기 때문에 중복을 제거해야한다. 아래의 코드에서는 set을 사용해서 중복을 제거했는데, 수열을 string으로 변환해서 set에 넣어주는 방식으로 구현했다. 또한 수열은 사전 순으로 출력해야하므로 맨 처음 입력받은 N개의 자연수를 정렬한 뒤 백트래킹했다. 코드 C++
알고리즘 문제 풀이 2020. 11. 2. 11:28
[프로그래머스] N-Queen

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 n이 12이하의 자연수 이므로 완전탐색으로 해결할 수 있다. 백트래킹을 사용한 완전탐색을 통해 해결했다. 모든 경우를 시도해서 가능한 경우를 카운트해주면 된다. 코드 C++ #include #include using namespace std; int N, ans; vector map; bool check(int x, int y) { // 세로 검사 for (int i = 0; i < N; i++) { if (i == y) continue; if (map[i][x]) return false; } // 가로..
알고리즘 문제 풀이 2020. 9. 3. 23:11
[SWEA] 2383 점심 식사시간

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 보고 BFS라고 생각하기 쉽지만, 백트래킹을 통한 완전탐색 문제이다. 이 문제는 크게 2가지 부분으로 구성된다. i번째 사람이 어느 계단으로 갈지 결정하는 부분 구현 계단을 모두 빠져나가는 부분 구현 1번의 경우 백트래킹을 통해 어렵지 않게 모든 경우를 구할 수 있다. 그렇다면 이제는 2번을 구현해야한다. 어느 계단으로 갈 지 결정했다면, 1번 계단으로 가는 사람들이 계단까지 걸리는 시간과 2번 계단으로 가는 사람들이 계단까지 걸리는 시간을 구할 수 있다. 이를 계산한 뒤, 걸리는 시간을 오름차순으로 정렬한다. 그리고 계단을 queue로 구현하여 계단..
알고리즘 문제 풀이 2020. 5. 7. 01:41
[백준] 14889 스타트와 링크

14889번: 스타트와 링크 www.acmicpc.net 풀이 백트래킹 문제이다. 무작위로 팀을 선정해서 전체 인원 수 / 2 만큼의 인원을 고르면 나머지는 B팀으로 생각하고 능력치를 계산해서 최소값을 구하면 된다. 코드 #include #include using namespace std; int n, ans = 987654321; int s[21][21]; bool a[21]; int get_result() { int sa = 0; int sb = 0; for(int i=1; i
알고리즘 문제 풀이 2020. 5. 6. 21:06
[백준] 14888 연산자 끼워넣기

14888번: 연산자 끼워넣기 www.acmicpc.net 풀이 단순한 백트래킹 문제이다. 연산자의 갯수에 맞춰서 백트래킹을 해주면 쉽게 해결할 수 있다. 코드C++ #include #include using namespace std; #define MAX 10000000000 int n, min_ans = MAX, max_ans = -MAX; int num[100]; int ops[4]; void dfs(int cnt, int result) { if (cnt == n) { min_ans = min(min_ans, result); max_ans = max(max_ans, result); return; } for (int i = 0; i 0) { ops[i]--..
알고리즘 문제 풀이 2020. 5. 6. 20:41
이전 Prev 1 2 Next 다음