일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 동적계획법
- mst
- Kotlin
- 유니온 파인드
- CS
- 그리디
- swea
- BFS
- 알고리즘
- 문자열
- Network
- 투 포인터
- 완전탐색
- 수학
- 스택
- 백트래킹
- 구현
- 백준
- 시뮬레이션
- 이분탐색
- 후니의 쉽게 쓴 시스코 네트워킹
- 세그먼트 트리
- JUnit 5
- dfs
- 플로이드-와샬
- 위상정렬
- 에라토스테네스의 체
- java
- Effective Java
- 프로그래머스
목록백트래킹 (7)
반갑습니다!
15663번: N과 M (9) boj.kr 풀이 엄청 많은 시리즈가 있는 문제이다. N개의 자연수 중에서 M개를 고르는 것은 백트래킹을 사용해서 어렵지 않게 구현할 수 있다. 하지만 이 문제에는 중복이 발생하기 때문에 중복을 제거해야한다. 아래의 코드에서는 set을 사용해서 중복을 제거했는데, 수열을 string으로 변환해서 set에 넣어주는 방식으로 구현했다. 또한 수열은 사전 순으로 출력해야하므로 맨 처음 입력받은 N개의 자연수를 정렬한 뒤 백트래킹했다. 코드 C++
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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; } // 가로..
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 보고 BFS라고 생각하기 쉽지만, 백트래킹을 통한 완전탐색 문제이다. 이 문제는 크게 2가지 부분으로 구성된다. i번째 사람이 어느 계단으로 갈지 결정하는 부분 구현 계단을 모두 빠져나가는 부분 구현 1번의 경우 백트래킹을 통해 어렵지 않게 모든 경우를 구할 수 있다. 그렇다면 이제는 2번을 구현해야한다. 어느 계단으로 갈 지 결정했다면, 1번 계단으로 가는 사람들이 계단까지 걸리는 시간과 2번 계단으로 가는 사람들이 계단까지 걸리는 시간을 구할 수 있다. 이를 계산한 뒤, 걸리는 시간을 오름차순으로 정렬한다. 그리고 계단을 queue로 구현하여 계단..
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
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]--..