문제요약 나의 코드 및 설명 이전까지 풀어본 백트래킹 문제와 크게 다르지 않다. 다만 주의할 점은, 수열의 합(s)이 0이 되는 경우의 수를 구할 때, 빈 리스트의 경우는 제외시켜주어야 한다. len(temp_list) != 0 으로 간단하게 제외시켜줄 수 있었다. def dfs(count, start, temp_list): global ans if len(temp_list) != 0 and sum(temp_list) == s: ans += 1 if count == n: return for i in range(start, n): dfs(count+1, i+1, temp_list+[num_list[i]]) n, s = map(int,input().split()) num_list = list(map(int,..
문제요약 나의 코드 및 설명 모음과 자음 리스트를 만들어 놓고, dfs를 통해 l의 길이를 갖는 temp_list가 호출이 되었을 때, 모음 개수와 자음 개수를 체크하여 조건에 맞다면 ans에 추가한다. def dfs(count, start, temp_list): if len(temp_list) == l: #temp_list 길이가 l에 도달한다면 mo_cnt = 0 za_cnt = 0 for i in temp_list: if i in mo: #모음 개수 체크 mo_cnt += 1 if i in za: #자음 개수 체크 za_cnt += 1 if mo_cnt >= 1 and za_cnt >= 2: ans.append(temp_list) #조건에 맞다면 ans에 추가 if count == c: return..
문제요약 나의 코드 및 설명 문제를 해결하기 위해 규칙을 먼저 찾아야 한다. y축을 i, x축을 j 라고 했을 때, 대각선 위로 향하는 좌표들의 i,j 값을 빼보면 모두 같다는 것을 알 수 있다. 또 대각선 아래로 향하는 좌표들의 i,j 값을 더해보면 값이 모두 같다는 것을 알 수 있다. 이 규칙을 활용하여, v[i+j], v[i-j] 의 값을 저장해주기 위한 룩업테이블을 만든다. 예를들어 i-j = -1 이라면, v[-1] 에 1을 저장한다. 이렇게되면, 오른쪽 위로 향하는 대각선의 좌표들은 모두 방문처리가 된다. 현재 좌표의 방문 처리를 위한 v1 리스트, 오른쪽 대각선 아래(\)로 향하는 좌표들의 방문 처리를 위한 v2 리스트, 오른쪽 대각선 위(/)로 향하는 좌표들의 방문 처리를 위한 v3 리스트..
문제요약 나의 코드 및 설명 문제의 조건에서 수열은 '비내림차순'이어야 하고, '중복되는 수열을 여러 번 출력하면 안된다.'고 한다. 비내림차순의 조건을 충족시키기 위해, 함수의 변수로 for문의 시작점 위치를 갖는다. 따라서 방문처리도 따로 안해줘도 된다. 중복되는 수열을 여러 번 출력하면 안된다는 조건을 충족시키기 위해, flag 방식을 활용하였다. 각 함수를 호출하고 for문을 돌기 전 prev를 0으로 초기화 한다. 그 후, 만약 prev가 입력으로 주어진 숫자와 같지 않다면, prev를 입력으로 주어진 숫자로 갱신하고 하위 함수를 호출한다. def dfs(count, start, temp_list): if count == m: ans.append(temp_list) return if count ..
문제요약 나의 코드 및 설명 (실패코드 : 빈 리스트가 출력) 처음에는 temp_list에 숫자를 담고 temp_list의 길이(수열의 길이)가 m이 될 때, ans 리스트에 저장된 수열 중 현재의 temp_list의 수열이 없다면 ans에 추가하는 식으로 문제를 풀려고 했다. 그러나 생각과는 다르게 리스트에 아무것도 담기지 않았다. 그 이유를 몰랐었는데, 파이썬 튜터라는 사이트를 통해 확인할 수 있었다. temp_list의 길이가 m일 때 정상적으로 ans에 append되기는 한다. 그러나 리턴하고 나서 temp_list의 마지막 요소를 pop하면서 방금 전에 ans에 담아놓은 마지막 요소까지 같이 pop된다. 이유는 잘 모르겠다.ㅠ >> 이유를 찾았다. 바로 shallow copy로 인한 문제이다. ..
문제요약 나의 코드 및 설명 def dfs(count, start_idx): if count == m: print(" ".join(map(str, ans))) return if count == n: return for i in range(start_idx,n): ans.append(num_list[i]) dfs(count+1, i) ans.pop() n, m = map(int, input().split()) num_list = list(map(int, input().split())) num_list.sort() ans = [] dfs(0,0)
문제요약 나의 코드 및 설명 def dfs(count): if count == m: print(" ".join(map(str, ans))) return if count == n: return for i in range(n): ans.append(num_list[i]) dfs(count+1) ans.pop() n, m = map(int, input().split()) num_list = list(map(int, input().split())) num_list.sort() ans = [] dfs(0)
문제요약 나의 코드 및 설명 - 방문처리 빠짐 고른 숫자들이 오름차순으로 정렬되기 위해 for문의 시작점을 start로 설정해두고, 하위 함수를 호출할 때 시작점을 변수로 받는다. def dfs(count, start = 0): if count == m: print(" ".join(map(str, ans))) return if count == n: return for i in range(start, n): ans.append(num_list[i]) dfs(count+1, i+1) ans.pop() n, m = map(int, input().split()) num_list = list(map(int, input().split())) num_list.sort() ans = [] dfs(0) 나의 코드 및 설..
