컴퓨터 CS (6) 썸네일형 리스트형 실전 DFS, BFS (유형 정리) DFS, BFS 문제를 풀다보니 어려움이 생겨서 유형을 정리하고자 글을 남긴다. 아무래도 머리가 그닥 좋지 않아서 그런지 이해해서 푸는 것은 아직 어렵기에 대표적인 유형 3가지만 정리하려고 한다. 후에 문제를 많이 풀게 될 경우 추가로 정리할 예정이다. 참고로 여기 있는 코드들은 예시의 문제의 정답이 아님을 알린다. 1. 그래프 형태를 직접 쌍으로 받는 문제들 ex) https://www.acmicpc.net/problem/1260 (실버 2) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www... 그리디 알고리즘(Greedy Algorithm) 1. 정의 그리디 알고리즘이랑 당장의 직면한 상황에서 최선의 수를 골라서 진행하는 알고리즘이다. 보통 코딩테스트에서는 그리디 알고리즘 유형이 나올 경우 최선의 수를 골라 진행하면 최적의 해가 산출된다. 2. 활용 사례 1) 거스름돈 문제: n=1260 #거스름돈 count=0 #출력 결과 array=[500,100,50,10] #거스름돈의 종류 for coin in array: count+=n//coin #동전의 개수 세기 n%=coin #동전 개수 세서 제외 후 남은 거스름돈 print(count) 가장 대표적인 그리디 알고리즘 유형이다. 반복문을 이용해서 동전의 종류에 따라 기존 거스름돈에 동전의 개수를 세서 값을 적용 후 남은 거스름돈으로 계속해서 다음 동전의 종류를 이용해 계산하는 방식이다. 2).. BFS-Python(파이썬) BFS 개념 그래프 자료 구조에서 원하는 자료를 찾는 탐색 알고리즘 수평 방향으로 원하는 노드를 탐색하는 알고리즘이다. 그림과 같이 수평 방향으로 노드들을 탐색한다. BFS 구현 원리 BFS의 핵심은 "방문하고자 하는 노드"와 "방문했던 노드"를 나누어서 구성하는 것이 핵심이다. 먼저 시작 노드를 방문했던 노드에 삽입한다 그 후 방문할 노드에 시작 노드의 자식 노드를 삽입한다. 마지막으로 자식 노드 중심으로 1~2단계를 거쳐 탐색한다. BFS 구현 기반 데이터(위의 그림과 같은 그래프이다.) graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E',.. DFS-Python(파이썬) DFS 개념 DFS란 Depth First Search의 약자로 "그래프 자료에서 데이터를 탐색하는 알고리즘" 이다 A부터 J까지 노드가 연결되어 있는 그래프 자료에서 특정 노드를 찾으려고 할 때 위에서 아래로 찾는 방식을 DFS라고 부른다. 위에서 아래로 탐색시 왼쪽으로 가냐 오른쪽으로 가냐는 시간 복잡도에 전혀 상관이 없다. 파이썬은 딕셔너리를 사용하여 그래프를 만든다. 다음 코드는 위 사진과 같은 그래프를 만드는 코드이다. 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'] .. 자료구조-그래프 Python(파이썬) 정의 그래프란 정점과 간선들로 이루어진 집합으로 표현되는 자료구조 트리도 일종의 그래프라고 할 수 있다. 종류 무방향 그래프 : 간선이 방향을 가지지 않음 방향 그래프 : 간선이 방향을 가지고 있음 가중치 그래프 : 각 간선에 가중치 정보가 포함됨. 가중치는 거리, 비용 등으로 표현 할 수 있다. 용어 1. 인접 정점: 어떤 정점에서 에지에 의해 직접 연결된 정점 2. 그래프 차수 2-1) 무방향 그래프: 하나의 정점에 연결된 다른 정점의 수 (=인접 정점의 수) 2-2) 방향 그래프: 진입 차수와 진출 차수로 구분, 진입 차수는 외부에서 오는 간선의 수 진출 차수는 외부에서 들어오는 간선의 수 -> 진입 차수의 합= 진출 차수의 합= 그래프 내 모든 간선의 수 3. 그래프 경로: 특정 정점에서 다른 정.. 자료구조-트리 Python(파이썬) 참고 사이트: https://www.delftstack.com/ko/howto/python/trees-in-python/ Python에서 트리 데이터 구조 구현 이 기사에서는 파이썬에서 트리 데이터 구조를 구현하는 방법을 볼 것입니다. www.delftstack.com 트리란 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리 노드 유형: 1. 부모 노드: 하나 이상의 자식이 있는 노드 2. 자식 노드: 부모 노드가 있는 노드 3. 리프 노드: 자식이 없는 노드 파이썬 트리 구현 내장함수를 이용하지 않고 구현하는 방법이다. 파이썬에서 트리를 생성시 먼저 단일 노드를 나타내는 node 클래스를 .. 이전 1 다음
