[패스트캠퍼스 :: 코딩테스트 인강] 8주차 ② 순차 탐색, 그래프

IT 개발/Algorithm 알고리즘

[패스트캠퍼스 :: 코딩테스트 인강] 8주차 ② 순차 탐색, 그래프

Euniverse 2021. 4. 11. 22:57

알고리즘/기술면접 완전 정복 올인원 패키지 Online

탐색 알고리즘 - 04. 순차 탐색

그래프 이해와 자료 구조 - 01. 그래프 이해와 자료 구조

그래프 이해와 자료 구조 - 02. 그래프 종류와 자료 구조

순차 탐색 (Sequential Search) 이란?

탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

from random import *

rand_data_list = list()
for num in range(10):
    rand_data_list.append(randint(1, 100))

def sequencial(data_list, search_data):
    for index in range(len(data_list)):
        if data_list[index] == search_data:
            return index
    return -1

그래프 (Graph) 란?

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)으로 표현하기 위해 사용

그래프 (Graph) 관련 용어

노드 (Node): 위치를 말함, 정점(Vertex)라고도 함
간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch라고도 함)
인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드)
참고 용어
- 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수
- 경로 길이 (Path Length): 경로를 구성하기 위해 사용된 간선의 수
- 단순 경로 (Simple Path): 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로
- 사이클 (Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우