백준 연산자끼워넣기2 15658
연산자끼워넣기(2)15658 1. 컴퓨팅 스킬 DFS 재귀호출로 백트래킹으로 구해줍니다. 연산자끼워넣기 1번문제와 같은 원리입니다. 정답 또한 같습니다. 2. 컴퓨팅 사고 DFS 백트래킹 맨처음 dfs(v,1,v[0],plus,minus,multi,div); 호출할 때 왜 idx = 1로 시작하고, sum의 값을 v[0]의 값을 넘겨주는가에
아카이브: 2019
백준 퇴사 14501
1. 백준퇴사14501 2. 컴퓨팅 스킬 백트래킹 재귀호출 3. 컴퓨팅 사고 맨 처음에 조합으로 next_permutation을 사용해서 해당 T[i]만큼 false를 만들면서 오는 경우를 찾으면 어떨까 라고 생각하였지만, 직감적으로 쉽지않다는것을 느꼈습니다. 그래서 재귀함수로 풀어보자 라는 생각으로 풀게되었습니다. 이 부분이 가장 중요한 부분입
백준 부분수열의합 1182
1. 백준 부분수열의합 1182 2. 컴퓨팅적 스킬 재귀호출 사용, 조합 사용 3. 컴퓨팅적 사고 next_permutation을 사용한 조합을 이용한 풀이 방법 1 순열과 조합중 조합을 사용하여 각각의 부분집합의 경우를 모두 구해준다. 하나씩 check변수에 모든 값을 true로 바꾸어준 후, 맨 앞에 있는 값들을 false로 바꾸면서 모든
백준 암호만들기 1759
1. 백준암호만들기1759 2. 컴퓨팅 스킬 Recursive를 활용한 풀이 백트래킹 두가지 방법으로 풀겠습니다. include헤더에 sort함수를 사용하겠습니다. 그 이유는 사전식으로 가능성 있는 암호를 모두 출력한다. 라는 조건이 있기 때문입니다. 3. 컴퓨팅 사고 조합의 방식으로 풀어야합니다. 어떻게 조합으로 풀어야된다는 생각을 하였을까요
백준 연산자끼워넣기 14888
1. 연산자끼워넣기14888 2. 컴퓨팅 스킬 next_permutation 값을 저장 시킬 vector v; 연산자의 개수를 1,2,3,4 의 값으로 넣을 vector cal; #include헤더에 minmax_element으로 최대값과 최소값 구해줍니다. DFS 재귀호출로 백트래킹으로 구해줍니다. 3. 컴퓨팅 사고 next_per
백준 로또 6603
1. 로또6603 2. 컴퓨팅 스킬 vector check 변수에 6개를 뽑는 경우의 수 이므로, k-6개만큼은 0을 푸쉬백 해주고, 6개까지에 1을 넣어줍니다. check배열로 next_permutation을 수행합니다. true인경우가 조합을 구하는 경우의 수입니다. 테스트케이스를 돌면서 vectorv, vector check의 값의 초기화값을 잘
백준 외원판순회2 10971
1. 백준외원판순회2 10971 2. 컴퓨팅 스킬 W[i][j]는 도시 i에서 도시 j로 가기 위한 비용이므로 모든 경우의 수 완전탐색을 수행합니다. N까지의 값을 vector에 넣어서 next_permutation을 수행합니다. next_permutation을 수행하는이유는 예를 들어 N이 4라고 하였을 경우 0,1,2,3까지의 값들을 vector에
백준 123더하기 9095
1. 백준 1,2,3더하기 9095 2. 컴퓨팅적 스킬 DFS 재귀함수 이용 vector에 테스트케이스 개수만큼의 값들을 넣어준 후, 반복문을 통해 각 경우에 대한 dfs를 호출하여 최종적으로 리턴되는값은 1,2,3으로 만들 수 있는 n에 대한 경우의 수입니다. dfs를 이해하기에 가장 좋은 예중 하나는 n과m문제입니다. 순열과 조합에 대표적인 문제입
백준 차이를최대로 10819
1. 백준 차이를최대로 10819 2. 컴퓨팅 스킬 #include헤더에 있는 next_permutation()함수를 호출하여 순열과조합을 구현합니다. next_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면)
백준 일곱난쟁이 2309
1. 백준 일곱난쟁이 2309 2. 컴퓨팅적 스킬 do while ~ (next_permutation)으로 계속해서 다음 조합의 경우의 수를 찾는다. vector v, check변수를 선언하여 permutation을 수행한다. 9명중 7명을 뽑아야하므로 7명만큼 check=true로 변경해서 수행한다. next_permutation을 수행하면서 값들이