Base Line/알고리즘
-
DFS 업데이트Base Line/알고리즘 2022. 10. 25. 14:42
# dfs 기본 원칙 # 앞으로 찾아 가야할 노드와 이미 방문한 노드 기준으로 탐색 # 앞으로 찾아 가야할 노드면 계속 검색 # 이미 방문한 노드이면 무시하거나 따로 저장 # 구현 방식은 "스택/큐" or "재귀함수를 통해 구현" graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] def dfs (graph, start_no..
-
이진 탐색Base Line/알고리즘 2022. 2. 22. 15:23
출처 : 이코테 순차탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 def sequential_search(n,target,array): for i in range(n): if array[i]== target: return i + 1 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(input_data[0]) target = input_data[1] array = input().split() print(sequential_search(n,target,array)) 이진 탐색 반으로 쪼개면서 탐색하기 변수 3개 사용 시작점, 끝점, 중간점 찾으려는 ..
-
DFS/BFSBase Line/알고리즘 2022. 2. 14. 18:10
#방문처리 def dfs(graph,v,visited): visited[v] = True print(v,end=" ") for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드들을 방문처리 하면서 깊이 탐색 진행 graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #그래프에 8개의 노드가 있으므로 처음 자리 0이므로 9개생성 visited = [False]*9 dfs(graph,1,visited) #BFS : 너비 우선 탐색 => 가까운 노드부터 탐색하는 알고리즘 from collections import deque def bfs(graph,start,visited..