시작이 반

N과 M 5번 문제는 1부터 n까지 숫자가 있는 것이 아니라 입력으로 n개의 숫자를 임의로 받는다. 이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다. 이후는 기존 n과 m의 풀이 방법과 같다. 대신 반복문의 i를 solve 리스트에 append, pop 하는 것이 아닌 오름차순으로 정렬한 리스트의 i번째 값을 append, pop 한다. n, m = map(int, input().split()) my_list = list(map(int, input().split())) my_list.sort() solve = [] visited = [False] * n def Dfs(depth): if depth == m: print(' '.join(map(str, so..

N과 M 3에서 중복을 제거한 문제이다. 반복문에 if depth == 0 or solve[depth - 1]

N과M 3번째 시리즈이다. 이번에는 방문했던 숫자를 다시 방문할 수 있다. visited를 써서 풀었지만 생각해보니 안써도 될 것 같다. visited를 모두 False로 하고 방문을해도 방문처리를 안한다. n, m = map(int, input().split()) visited = [False] * (n + 1) solve = [] def Dfs(depth): if depth == m: for i in range(m): print(solve[i], end=" ") print() # print(' '.join(map(str, solve))) # join을 사용하여 풀 수 도있다. join은 문자열을 합치는 함수이다. # solve에 있는 원소는 int형이기 때문에 map을 사용하여 string형으로 만들..

15649번에서 오름차순을 하고, 중복을 없앤 방식이다. 1. 재귀를 수행할때 반복문을 시작해야할 숫자를 같이 넣어준다. 현재 i 보다 +1 인 값을 건내줘서 반복문이 그 값부터 시작하게 한다. 2. list의 마지막 원소값을 확인하여 그 값보다 i 가 클경우만 재귀를 수행한다. 깊이가 0일땐 무조건 재귀 ** if depth == 0 or visit_number[len(visit_number) - 1] < i: n, m = map(int, input().split()) visit_number = [] def BackT(start, depth): if depth == m: for i in visit_number: print(i, end=' ') print() return for i in range(sta..

백트래킹의 기초 문제이다. 완전탐색을 하게된다. 재귀를 이용하여 풀게되는데 이때 더이상 탐색을 할 필요가 없다면 재귀 탐색을 멈추게된다. 첫 풀이 해당 숫자에 visited를 부여하여 방문을 했는지 계속 체크하고 visited를 deepcopy하여 넘겨주는 식으로 하였다. 이렇게 하면 숫자가 많아질수록 list를 엄청나게 많이 만들게 되고 또한 deepcopy를 하는데에 시간도 길리기 때문에 메모리, 시간 둘다 비효율적이다. ....... 정답 풀이 visited라는 상태 체크를 하는 것이 아니라, 방문한 숫자를 집어넣는 list를 만들어 풀게 된다. 1. 깊이가 출력하는 숫자의 길이가 같을경우 재귀를 멈춘다. 2. i : 1 ~ n 까지 반복을 하여 list에 i에 해당하는 숫자가 없을경우 i를 app..

경우의 수를 탐색해 나가는 도중 찾는 해가 아니면 이전 상태로 되돌아가서 다시 해를 찾는 방법이다. 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해가 되지 않을 것 같다면 그 아래의 탐색은 중지하고 이전 분기점으로 되돌아가는데 탐색 횟수가 줄어들게 된다. 이를 가지치기라고 한다. 즉 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다. 모든 트리를 탐색하게 된다면 해가 없을 것이다. 백트래킹은 기본적으로 완전탐색 카테고리에 있다. 다른 알고리즘 방법으로 해..

미로와 같은 방식으로 풀 수 있지만 벽을 최대 한번 부실 수 있다는 조건이 있다. 처음 생각한 방법은 다음 좌표에 대해서 벽이 있을경우 그 벽을 깨고 그 자리에서 다시 BFS를 수행하는 것이었다. 즉 BFS( BFS ) 이렇게 중첩이 되는데 제출 결과 시간 초과 에러가 나왔다. 시간 복잡도를 보게되면 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색하니까 O(NM)^2)가 된다. 배열의 가로와 세로의 입력이 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000) 이렇게 제한이 되어있는데 N과 M이 1000일경우 NM은 1,000,000이 되고 NM^2은 1,000,000,000,000가 되니.. 시간초과가 뜨는게 당연하다. 3시간이나 붙잡고 풀었는데 참... 정..

수빈이가 다음 장소로 갈 수 있는 경우의 수는 3가지 이다. 3가지 경우의 수를 방문하면서 동생의 위치와 같을 때 까지 탐색을 한다. 현재 인덱스에서 다음 방문할 3개의 경우의 수를 모두 방문하여 동생의 위치와 같은 경우를 찾아야 하기 때문에 BFS를 사용한다. visited = [] 1차원 배열을 사용하여 해결할 수 있다. 처음 수빈이가 있는 인덱스를 방문처리(1로 지정)한다. 현재 노드에서 다음 3가지 인덱스를 방문한다. 여기서 방문처리는 (다음 노드 = 현재 노드 + 1) 로 나타 낼 수 있다. 인덱스가 동생의 위치와 같아질 경우 끝나게 되는데 이때 동생의 인덱스 까지 최소 몇번만에 도달하였는지 동생이 위치한 인덱스의 원소(다음 노드 = 현재 노드 + 1)로 알 수있다. 처음에 수빈이가 있는 인덱스..