MuviSsum

오랜만에 bisect 함수쓰면서 bisect함수랑 이분탐색을 훑어봐야지 하는 생각이 들더라구요. 그래서 문제를 하나 내고 1부터 1000,000,000까지의 값 중 임의값 찾기라는 임시문제를 내고 코드를 만들어 봤습니다. 먼저 파이썬의 bisect 라이브러리입니다. import bisect arr = range(1, 1000000000) idx = bisect.bisect_right(arr, 11) print(arr[idx]) # output: 12 arr = range(1, 1000000000) idx = bisect.bisect(arr, 11) print(arr[idx]) # output: 12 arr = range(1, 1000000000) idx = bisect.bisect_left(arr, 11..

DFS란? 깊이 우선 탐색 자신에게 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다. 이동한 노드에서 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다. 이렇게 계속 내려가다가 자식 노드가 없는 노드를 찾는다. 다시 부모 노드로 이동하여 새로운 자식 노드를 찾는다. 또 자식노드가 없으면 다시 부모노드로 이동하여 위의 순서를 반복한다. 완전탐색 중 한 방법 - 위의 순서를 보면 모든 노드를 체크하는 것을 볼 수 있다. DFS에서 발전된 알고리즘 : 백트레킹 백트레킹은 DFS 방식을 하면서 조건을 추가한다. 한 노드가 조건에 맞지 않으면 밑의 자식노드 또한 조건에 맞지 않으므로 다시 부모노드로 돌아간다. DFS보다 훨씬 시간을 줄일 수 있다. DFS를 이해하기 위해서는 그림을 보면 쉽..