전체 글

아직 언제 재귀를 써야 하고, 언제 dfs 를 써야 하고, 언제 백트래킹을 써야 하는지 잘 모르겠다 ㅜㅜ 이 문제는 백트래킹으로 들어간 문제인데 그걸 아는데도 백트래킹이 무엇인지 제대로 몰라서 아주 헤맸다. 먼저 다시 정리해보고자 한다. 백트래킹이란 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어가는 것이다.즉, 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 다시 해를 찾는 것이다. 여기서 중요한 점은 더 이상 탐색할 필요가 없는 상태를 제외하는 것인데 이를 가지치기 라고 한다.백트래킹은 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 ..

먼저 2 차원 배열로 상담 시간과 수익을 저장한다.  현재 작업 중인 i 번째 리스트 인덱스 값에 i 번째 리스트의 값을 더했을 때  보다 작다면, 수익에 해당 값을 재귀 호출한 값과 수익을 더한다. 현재 작업을 수행하지 않고 그냥 다음 작업으로 넘어가는 경우 두 경우 중 더 큰 값을 선택한다. 각 작업은 소요되는 시간이 정해져 있고 주어진 제한된 시간 안에서 최대한 많은 이익을 얻기 위해 어떤 작업을 선택해야 할지 재귀 호출을 통해 고민해 보았다. 1. 주어진 작업을 할지 말지 결정2. 작업이 끝나는 시간을 넘지 않는 범위 내에서 최대 이익을 얻도록 재귀적으로 계산 재귀 -> 각 작업을 선택하거나 선택하지 않는 모든 경우를 탐색n = int(input())list = [list(map(int, inpu..

입력받은 수열을 사용하여 가능한 모든 순열을 생성하고 각 순열에서 인접한 두 숫자의 차이의 절댓값을 더한 값 중 최댓값을 찾는 문제를 해결하고자 했다. 1. 모든 순열 생성 2. 인접한 두 숫자의 차이의 절댓값 더하기 3. 최댓값을 찾기 먼저 새로운 순열을 저장할 배열, 중복을 확인할 배열, 가능한 최댓값을 갱신하기 위한 변수를 설정한다. 가능한 모든 순열을 탐색해야 하기 때문에 백트래킹 (모든 가능한 경우의 수를 탐색하는 알고리즘) 을 사용했다. 방문한 숫자를 되돌리기 위한 visited 배열과 순열을 구성하는 arr 배열을 통해 매번 새로운 순열을 구성한다. base case 인 cur 이 n 이 되었을 때 즉 순열이 완성되면 total 변수를 사용하여 인접한 값들의 차이의 절댓값을 구하고 이를 an..

dp 에 이어 드디어! 브루트포스 문제를 풀게 되다니... 구현/수학 만 하염 없이 풀다가 이렇게 있어 보이는 문제를 풀 땐 마음이 긴장된다.긴장은 둘째 치고... 인생 첫 브루트포스 문제 브론즈 1 임에도 답을 보고 풀다... 브루트포스에 지레 겁 먹어서인지 바보 같은 코드만 짜다가 결국 감을 잡고자 여러 답을 확인해보고 이해하기로 했다. 1. 9 명이라고 제시되어 있다.2. 오름차순으로 출력한다.3. 어떤 7 명인지 찾을 필요는 없다. 핵심은 9 명의 난쟁이 중 2 명을 뺀 후 나머지의 합이 100 이 됨을 확인하는 것이 아니라, 9 명을 모두 합하고 2 명을 빼면 100 이 되는 순간을 확인하는 것이다.  그래서 먼저 list 에 9 명의 키를 모두 담고 flag 를 만든다. flag 는 합이 10..