본문 바로가기

분류 전체보기

 (82)
BFS (Breath First Search) 너비우선탐색 Python 인접리스트 활용 너비우선탐색 BFS (Breadth First Search) 큐를 이용하여 그래프를 순회하는 방법 1. 1번부터 접근을 시작한다 가정했을 때 1번의 인접리스트를 큐에 저장 (모든 노드가 자신의 인접리스트를 큐에 저장 단, 이전에 방문한적이 없으며, Queue에 저장이 안되어 있는 경우 Queue에 저장함) 2. 자신의 모든 노드에 대해 Queue 저장 작업이 완료되면 할 일을 다했다. 이제 Queue의 pop연산을 수행하고 pop한 노드 및 정점의 인접리스트에 대해 1번의 과정을 수행한다. 3. 큐가 비어있지 않는 한 위 과정을 반복적으로 수행 1번부터 BFS시 수행되는 순서는 다음과 같다. 1 2 4 3 11 9 5 6 8 7 10 아래의 소스코드를 통해 각 정점 및 노드별 큐의 상태를 확인할 수 있다..
DFS (Depth First Search) 깊이우선탐색 C++, Python 인접리스트 활용 그래프 순회를 하는 방법 2가지 DFS, BFS 그래프라는 자료구조안에 어떠한 값이 있는지 확인하는 용도 깊이우선탐색 DFS (Depth First Search) stack을 이용하여 그래프를 순회하는 방법 나를 먼저 방문하고, 그 다음 (우선순위 기준으로) 인접한 노드를 차례대로 방문 * 단, 방문했던 노드는 방문하지 않는다. (해당 노드에 대한 visited, checked 가 0이 아닌 경우) DFS = 스택사용 = 선행관계 = 재귀호출 = 발자취 인접한 노드가 없거나 혹은 모든 인접노드를 방문을 한 경우 자신을 기준으로 이전 노드로 이동한다.(방문한 적이 없는 노드를 찾고 방문하고 되돌아오는 과정 반복) 재귀!! v = vertex 정점 visited = 해당 노드에 방문한적이 있는지 없는 체크 ..
[자료구조] 인접리스트 Python C++ 인접리스트 인접한 정점에 대한 정보를 리스트 표현 정점이 인접한 정점의 개수에 따라 가변적으로 변할 수 있음 O(deg(V)) 즉, 정점의 차수에 따라 결정됨 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 lists = [] m, e = map(int, input().strip().split()) for i in range(m): temp = [] for j in range(m): temp.append(0) lists.append(temp) for i in range(e): a, b = map(int, input().strip().split()) lists[a - 1][b - 1] = 1 lists[b - 1][a - 1] = ..
[자료구조] 인접행렬 기초 정점 연결관계 Python 인접행렬 *간선의 개수는 정점의 개수 제곱과 같거나 작다. 4c2 -> n(n-1)/2 *모든 정점의 차수의 합은 간선의 2배와 같다. 인접행렬에서 자주 나오는 문제 Q1. x는 y와 인접하는가 O(1) Q2. x와 인접한 리스트를 구하라 장점 - 바로 접근해서 확인가능 단점 - 실제 인접한 정점 수와 관계없이 인접한 정점을 찾는데 O(n)이 걸림. ex) 정점이 5개라면 자신을 제외한 나머지 간선들과의 관계 확인 필요 - 간선의 개수와 관계없이 n2개의 칸을 사용해야 함. (n=정점의 개수) 정점과 간선을 입력받고 연결이 되는 정점끼리의 값을 1, 정점이 연결되어 있지 않다면 0으로 표현하는 코드를 작성 ex) 정점의 개수 5, 간선의 개수 6 1 2 1 3 1 4 2 4 4 5 3 5 1 2 3 4 ..
[자료구조] 그래프 기초 그래프 정점(Node, Vertex): 정점 간선(Edge): 정점에 연결된 선 차수(degree): 각 정점이 가지는 간선의 개수 *간선의 개수는 정점의 제곱보다 작거나 같다 12,13,14 21,23,24 31,32,34 41,42,43 A를 정점의 수 라하고, E를 간선의 수 라 하면 E
[자료구조] 이진트리 Binary Tree - 자식노드를 최대 2개로 가지는 트리 Binary Search Tree - 숫자 기준으로 노드의 왼쪽 자식들은 자신보다 작은 숫자들이 위치하는 것, 반면 우측의 자식들은 자신보다 큰 숫자들이 위치하는 것. - 숫자가 아닌 우선순위를 기준으로 해도 마찬가지 자신보다 우선순위가 높은 것들은 왼쪽으로 자식을 가지고, 자신보다 우선순위가 낮은 것들을 오른쪽 자식으로 가질 수 있음 - 상황과 형태에 따라 알맞게 구성해야 함. Complete Binary Tree 2:1 or 2:0 완전 - 자식을 가지는 노드 중 하나라도 자식을 2개로 가지는 노드가 있으며됨, 동일한 레벨의 노드가 자식을 1개 혹은 2개를 가짐 Full Binary Tree 2:2 or 2:0 풀 - 자식의 노드를 2개 이..
[자료구조] Stack, Queue Stack 데이터의 상태, 값 저장용도 LIFO(Last In First Out) 마지막에 들어온 것이 먼저 나감 개인적인 생각으로 Git의 Commit, Push 등의 로그들이 Stack의 용도로 사용된다고 생각함. 예전 컴퓨터공학과 2학년 수업 중간고사 때 실생활 예로 학생식당에서 사용하는 종이컵으로 사용생각함. 종이컵 박스에서 위에만 뚫려있다면 넣을때 아래부터 위로 쌓아지고 사용하는 사람은 차례대로 위에 뚫린 구멍을 통해 하나씩 빼서 사용하는... stack의 연산 top: stack의 최근 삽입한 데이터, 혹은 위치 push: 데이터 삽입(top+1) pop: 최근에 삽입한 데이터 제거 size: stack의 크기 empty: 비워져있는지 아닌지 C++의 STL로 쉽게 확인 가능함. Queue 전..
[백준] 덩치 7568 브루트포스 Python 덩치 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 10015 5749 5080 60.240% 문제 https://www.acmicpc.net/problem/7568 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 ..

티스토리툴바