-
(백준 1182번/1759번/1987번 부분수열의 합/암호만들기/알파벳 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 1PROGRAMMING/알고리즘 2024. 4. 15. 15:32
백트래킹(Backtracking) (수정 2019-10-09)
탐색 중에서는 가장 마지막으로 쓰는 글이 아닐까 싶습니다. 이제 DFS와 BFS도 익혔으니, 백트래킹(b...
blog.naver.com
오늘은 백트레킹에 대해 공부해보았다!
백준 1182번
https://www.acmicpc.net/problem/1182
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
백준 1759번
https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
백준 1987번
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의
www.acmicpc.net
풀이는 라이님 블로그에 있기 때문에 패스!
완전 탐색을 푸는 또 다른 방법이라고 생각이 되는데, 코드가 짧고 간결한데도 직관적으로 딱 이해가 되진 않아서 익히는데 시간이 조금 걸렸다.
'PROGRAMMING > 알고리즘' 카테고리의 다른 글
(백준 9663번 N-Queen C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 3 (0) 2024.04.16 (백준 10597번 순열장난 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 2 (1) 2024.04.15 (백준 7576번 토마토 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 7 (1) 2024.04.10 (백준 6593번 상범빌딩 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 6 (0) 2024.04.10 (백준 5014번 스타트링크 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 5 (0) 2024.04.10