보호되어 있는 글입니다.

한곳을 먼저 깊이 탐색하다가 더이상 갈 수 없을때 다른쪽을 탐색 #DFS #전역변수를 사용한 경우 graph = { 'A' : ['B', 'D', 'E'], 'B' : ['A', 'C', 'D'], 'C' : ['B'], 'D' : ['A', 'B'], 'E' : ['A'] } visited = [] def dfs(current): visited.append(current) for k in graph[current]: if k not in visited: dfs(k) return visited ###################################################### #전역변수 사용 안한 경우 def dfs(graph, current, visited=[]): visited.appe..

같은 레벨의 노드부터 먼저 탐색 BFS 구현 from collections import deque #BFS def bfs(graph, start): #시작점 start가 들어간 방문목록 visted로 초기화 visited = [start] queue = deque([start])#방문할 노드 목록 queue에 시작점을 담아준다. while queue:#방문할 목록이 없을때까지 반복한다. current = queue.popleft()#방문할 목록에서 방문할 곳을 하나씩 꺼낸다. for k in graph[current]:#방문할 노드에 연결된 노드를 방문하고 다음 방문할 목록에 추가해준다. if k not in visited:#방문한 곳이 아니면 방문하고 방문할 목록에 추가 visited.append(k)..

정의 - 어떤 자료나 개념을 표현하는 정점(VERTEX)들의 집합 V와 이들을 연결하는 간선(EDGE)들의 집합 E로 구성된 자료구조 - 트리는 계층구조로 한방향(위에서 아래로)으로만 연결되지만 그래프는 제약없이 연결된다. - 위와 같은 이유로 모든 트리는 그래프라고 할 수 있으나 모든 그래프는 트리라고 할 수없다. 종류 - 방향 그래프 VS 무향 그래프(코테에 가장 많이 나옴) 간선에 방향성이 있는지(방향 그래프) 없는지(무향 그래프) - 다중 그래프 VS 단순 그래프 정점과 정점이 연결될 때 간선이 하나인지(단순 그래프) 여러개인지(다중그래프) - 가중치 그래프 => 다익스트라 간선에 수치로 가중치가 있다. 구현방법 - 인접리스트(adjacency list) - 인접행렬(adjacency matrix..

트리 - 서로 연결된 Node 의 계층형 자료구조 - root 와 부모-자식 관계의 subtree로 구성 Tree 관련 개념 - 노드(Node) : 트리를 노드로 구현 - 간선(Edge) : 노드간에 연결된 선 - 루트 노드(Root) : 트리는 항상 루트 노드에서 시작 - 리프 노드(Leaf) :더이상 뻗어나갈 수 없는 마지막 노드 - 자식 노드(Child), 부모노드(Parent), 형제 노드(Sibling) - 차수(degree) : 각 노드가 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다. - 조상(ancestor): 위쪽으로 간선을 따라 올라가면 만나는 모든 노드 - 자손(descendant): 아래쪽으로 간선을 따라가면 만나는 모든 노드 - 높이(height) :..

재귀함수 - 자신을 정의할 때 자기 자신을 재참조하는 함수 ex) def factorial(n) if n ==1 : return 1 return n * factorial(n-1) 구성요소 2가지 -recurrence relation (점화식) ex) 위에 factorial함수는 점화식으로 표현하면 f(n) = n*f(n-1) -base case(더이상 재귀호출을 하지 않아도 계산값을 반환할 수 있는 조건을 말한다. basecase가 있어야 재귀함수의 무한루프를 방지할 수 있다) 시간 복잡도 - 재귀함수 전체 시간복잡도 = 재귀 함수 호출 수 * (재귀 함수 하나당) 시간복잡도