본문 바로가기

백트래킹14

[백준 16987] 계란으로 계란치기 www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net n의 범위가 1부터 8까지이기 때문에 브루트 포스 & 백트래킹을 하면 풀리는 문제이다. 주의할 점: hand== n인 기저조건까지 도달하기 위해 모든 조건에서 backtracking함수를 실행시켜야 한다는 것이다. ' ++괜히 경우의 수를 출력한다고 했다가 너무 많은 경우의 수라서 무한 루프 도는 것처럼 보였다... #include #include #define MAX 8 //n=8이기 때문에 다.. 2020. 11. 12.
[leetcode 39] Combination Sum Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. It is gu.. 2020. 10. 25.
[leetcode 78] Subsets Given a set of distinct integers, nums, return all possible subsets (the power set). 가능한 모든 부분집합을 구하라. Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 풀이: 전형적인 백트래킹 문제이다. cnt가 nums길이와 같아지면 종료하지만 그 전에 만들어지는 모든 경우의 수 역시 정답에 저장한다. class Solution { public: vector result; void BackTracking(int cnt, i.. 2020. 10. 24.
[leetcode 79] Word Search Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true Example 2: Input: board = [.. 2020. 10. 22.