이진 탐색의 시간 복잡도: O(logN) 정렬되지 않은 길이 N의 리스트에서 M개의 값을 이진 탐색으로 찾을 때 시간 복잡도: O((M+N)*logN) 길이 N의 리스트 정렬하기: O(N*logN) 정렬된 길이 N의 리스트에서 M번 이진 탐색하기: O(M*longN) 1. 재귀 함수로 구현한 이진 탐색 코드 # 이진 탐색 소스코드 구현(재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간접 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid]..

https://leetcode.com/problems/recover-binary-search-tree/ Recover Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 올바른 BST라면 inorder 순회를 했을 때 값들이 오름차순으로 정렬되어야 한다는 사실을 이용해 풀이했습니다. inorder 순회를 하면서 result에 값을 저장하고, 오름차순 정렬이 되지 않는 부분들의 노드를 발견하면 swap에 추가적으로 저장했습니다. 순..

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/ Populating Next Right Pointers in Each Node - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS를 이용해 풀이했습니다. 먼저 root와 root의 depth인 1을 각각 다른 queue에 넣어주고 queue가 빌 때까지 다음을 반복합니다. 각 queue의 맨 첫번째 요소..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 입력을 받아와 인접 리스트로 바꿔주고, 이를 다시 list of list로 변환하는데, 이때 i번째 리스트에는 i번째 컴퓨터와 직접 연결되어 있는 컴퓨터들의 번호가 저장됩니다. 이를 이용해 시작점을 1로 하고 dfs 함수를 수행해줍니다. visited 리스트 중 1번 컴퓨터를 제외한 컴퓨터들의 개수를 sum을 이용해 구한 후 반환합니다. https://codlingual.tistory.com/182 D..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr DFS를 수행하는 함수 dfs를 정의하고, 모든 컴퓨터를 방문할 때까지 dfs를 반복합니다. 우선 0번째 컴퓨터부터 시작해서 이와 직/간접적으로 연결되어 있는 모든 컴퓨터들 방문합니다. 이후에도 아직 방문하지 않은 컴퓨터가 있으면 answer를 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 번호가 가장 작은 것에서부터 시작해 다시 dfs를 호출합니다. 모든 ..

DFS - 스택 - 재귀함수 이용 # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end = '') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) BFS - 큐 from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = de..