# data[].attributes.headline
그래프 분석 라이브러리

# data[].attributes.subject
그래프 분석 라이브러리

# data[].attributes.body
1. NetworkX

파이썬으로 작성된 간단한 인터페이스의 그래프 분석 라이브러리

사용이 매우 쉬움

큰 규모의 네트워크에서는 성능이 떨어짐

2. SNAP

대규모 네트워크 분석에 최적화된 C++ 기반 라이브러리이며 고속 처리 성능을 제공함

파이썬 인터페이스가 제한적이고 복잡함

3. iGraph

큰 규모의 그래프를 빠르게 처리 가능하고 다양한 네트워크 알고리즘을 제공함

문서화가 부족하고 복잡함

4. Graph-tool

C++로 구현된 고성능 그래프 분석 라이브러리로 메모리와 성능이 최적화되어있음

설치가 복잡하고 사용법이 까다로움

5. Networkit

대규모 네트워크의 효율적 분석을 목표로 한 C++ 기반 라이브러리로 파이썬 바인딩을 제공함

기능이 다른 라이브러리들에 비해 제한적임

# data[].attributes.attachment_link.title
[그래프 ML] 그래프 분석 라이브러리 - 파이썬 NetworkX, SNAP, igraph, graph-tool, NetworKit

# data[].attributes.attachment_link.description
HTML 삽입 미리보기할 수 없는 소스 ※ 이전 글 참고 [그래프 ML] 파이썬 networkx 시작하기 ※ 출처 : 그래프 머신러닝 (클라우디오 스타밀레 외, 김기성·장기식 옮김) 1. 그래프(Graph) 뜻 * 개체 간의 관계를 설명하는 데 사용되는 수학적 구조 * 소셜 네트워크(팔로우), 지도(길로 이어진 data-science-note.tistory.com ☆★ 요약 ★☆ 작업 규모 및 목적 적절한 라이브러리 소규모 네트워크 분석 NetworkX 대규모 네트워크 및 고성능 분석 SNAP, igraph, graph-tool, NetworKit 시각화 기능 graph-tool, NetworKit 신규 알고리즘 생성 NetworKit 라이브러리 주요 특징 장점 단점 NetworkX - 표준 그래프 이론…

# data[].attributes.body
데이터 분석 기법 및 그래프 이론을 통한 단일 운송수단에서의 상품 유통망 최적화

# data[].attributes.body
산업공학과

# data[].attributes.headline
왜 그 학과에 가고 싶은지

# data[].attributes.subject
왜 그 학과에 가고 싶은지

# data[].attributes.body
저 같은 경우, 사실 이과와 문과적 성향이 둘 다 있어서 계속 학과를 찾아봐도 뭔가 저랑 잘 맞는 학과를 찾기가 힘들었습니다. 그러다 도서관에서 사회과학 코너를 돌다가 산업공학이라는 분야를 알게되었습니다. 공학인데 또 산업 (경영)이 합쳐져있다는점이 흥미로워 산업공학과에 대해 더 조사해봤고, 정말 제가 원하던 느낌의 학과라고 느꼈습니다. 특정 분야에만 치중되어있지않고 전 분야와 어우러지는 학과라는 점이 가장 매력적으로 다가왔습니다. 시대 특성상 계속해서 지식도 직업도 모두 세분화되다보니 전문성이 높아졌지만 한편으로 직업의 범용성과 연계성은 많이 떨어진다는 점이 개인적으로는 딱히 좋지않게 다가왔습니다. 그런데 세분화된 그런 직업들을 하나로 묶어줄수있는 학과가 바로 산업공학과더라고요. 단순히 공학만 배우고 경영만 배우고 그러는게 아니라 공학적 사고를 바탕으로 한 경영을 배우기에 그 내용을 다른 직업들과 연결할 수 있는 점이 정말 매력적이기에 산업공학과에 가고싶습니다.

# data[].attributes.headline
어떤 사람이 되고 싶은지

# data[].attributes.subject
어떤 사람이 되고 싶은지

# data[].attributes.body
약간 비유적으로 말해보자면, '차가움 속에서 따뜻함을 설계하는 사람'이 되고 싶습니다. 최근 몇년간 뉴스에서 노동 사고, 노동 인권 문제, 산업활동으로 인한 과도한 환경 파괴 등등의 이슈가 많이 나왔습니다. 이게 한두번도 아니고 비슷한 일이 계속 반복되어 뉴스거리가 되다보니 문득 이런 의문이 들었습니다. '분명히 기업에서는 이러한 문제점들이 있다는 사실을 알고있고 고칠수있음에도 그렇게 하지 않는걸까..?'

저는 그 이유가 그냥 근본적인 산업 시스템에 어떤 결함이 있기 때문이라 생각합니다. 원래 산업 시스템은 시장의 구성원들이 모두 만족할 수 있는 시장을 만들기 위해 구성된것인데 요즘의 산업 시스템은 너무 차갑습니다. 시장의 목적이 시장 구성원들의 만족의 달성이라면 구성원들의 정신적 상태까지 산업 시스템의 변수로 넣어야하는게 맞지않나요? 그런데 4차산업혁명 때문인진몰라도 기계처럼 효율만을 따지는 세계관이 형성됨에 따라 인간의 욕구 (만족) 충족이라는 시장과 산업 시스템의 본목적이 잊혀지고있는듯합니다. 그래서 기업들도 환경파괴, 인권문제와 같은 이윤 추구와 직접적인 관련이 없는그러한 문제는 고려하지않은채로 자본주의의 부정적인 면만을 수용해가고있다는게 저의 생각입니다.

현대인들에게 감성은 어쩌면 쓸모없다고 여겨질 수도 있지만, 저는 감성이 사실은 무엇보다 중요하다고 생각합니다. 이렇게 차가운 사회 안에서 감성적인, 친환경, 친인간적 산업 시스템을 설계하는 따뜻한 인간이 되는 것이 저의 목표입니다.

# data[].attributes.body
1. 선형대수학

2. 공학 (유체역학 등등)

3. 데이터 분석

4. 상품 유통망 설계

# data[].attributes.headline
관련 지식 (체인지 메이커 외의 것도)

# data[].attributes.subject
관련 지식 (체인지 메이커 외의 것도)

# data[].attributes.body
1. 행렬

수학 - 그래프 이론

2. 네트워크 이론

수학 - 그래프 이론

3. 유체역학

과학 - 배관 시스템

4. 빅데이터 분석 기법

정보- 파이썬

# data[].attributes.body
직접 최적 유통망을 설계하며 산업공학의 기본 내용을 익혀보고싶어서 선정함. 이 주제로부터 또 다른 주제로 뻗어나갈수있는 경우의 수가 많다고 생각하기에 범용성도 나쁘지 않은듯함. 무엇보다, 지금까지 해온 활동들을 녹여내기에 좋은 주제라 생각함.

과학 기술 발전하여 교통, 산업 발달

-> 교통의 발달로 상대적 거리의 축소, 상품의 유통 거리는 증가

-> 그에 따라 유통 과정에서도 적지않은 환경오염 발생

-> 만약 유통망이 최적화된다면 환경 오염도 완화되지않을까?

-> 수학 탐구와 정보에서 익힌 그래프 이론과 파이썬을 심화학습하고, 그 내용에 빅데이터 이론을 추가한다면 유통망의 최적경로를 만들 수 있을거로 생각함. (여기서 최적화란 연료 소비량과 거리를 고려한 경로를 의미)

# data[].attributes.headline
활동 절차 (관련지식 공부 후)

# data[].attributes.subject
활동 절차 (관련지식 공부 후)

# data[].attributes.body
1. 그래프 모델링

노드 : 창고, 배송센터, 구매자

엣지 : 노드를 이은 경로 (일종의 도로)

가중치 : 연료 소비량, 거리

2. 데이터 수집

위치 데이터 수집

배송 데이터 수집

3. 데이터 전처리

데이터 정제

데이터 통합 (데이터 웨어하우스 등)

데이터 변환 (알고리즘에 맞는 규격으로)

4. 그래프에 데이터 대입

파이썬 Dijkstra 등의 노드 간의 최적 경로 계산해주는 알고리즘 사용 -> 최적 경로 분석

5. 그래프 시각화

최적 경로 계산 후 그 경로 강조하여 시각화

6. 지도 생성

최적 경로를 지도에 시각화

Folium 라이브러리 사용

# data[].attributes.headline
어떻게 생기부에 녹여낼지

# data[].attributes.subject
어떻게 생기부에 녹여낼지

# data[].attributes.headline
지금까지 한 활동 (수행 등)

# data[].attributes.subject
지금까지 한 활동 (수행 등)

# data[].attributes.body
1. 수학 탐구 수행

'그래프 이론에 대한 기본 탐구 (및 케빈 베이컨의 6단계 분리 법칙 증명)'. 6단계 분리 법칙은 대충 6번의 단계를 거치면 자신이 전혀 모르는 사람과도 연결될 수 있다는 내용의 법칙인데 이게 수학과도 깊은 관련이 있다는 사실에 흥미를 느끼고 탐구를 시작함. 집합과 관련되어있는 내용을 중심으로 어찌저찌 탐구를 진행하고있었는데 갑자기 교과과정에서 빠진 행렬이 나와서 가중치 그래프라는 곳에서 막혔음. 그래서 1학기 활동에 이어서 2학기 에 추가적으로 행렬까지 공부하고 간단하게 6단계 분리 법칙을 증명해볼 계획.

2. 과학 탐구 수행

'이산화탄소 농도와 졸음의 상관관계의 과학적 추론'. 보어 효과와 홀데인 효과로 왜 밀폐된 공간에 있으면 정신이 흐려지는지를 설명함. 딱히 질 좋은 내용은 아니라 2학기 때 다른 탐구를 진행해볼 예정.

3. 챌린저 트랙 (과학탐구대회)

'유체역학을 통한 파이프 내 유체의 흐름 분석 및 산업 배관 시스템의 최적화'. 과학 탐구 실험 시간에 샴푸와 스프레이의 작동 원리를 분석하고 베르누이 효과를 학습하고, 과학 탐구 수행에선 이산화탄소 농도와 졸음의 관계를 추론해보며 기체가 움직이는 방식에 흥미를 느낌. 이에, 관련 서적과 인터넷 자료를 통해 유체역학의 기초를 학습하고, 이 지식을 활용하여 산업 배관 시스템에서 유체의 흐름을 분석하고 최적화하는 방법을 모색하고자 했음. 그러나 유체역학을 배우는데 걸리는 시간이 예상보다 길었고, 실험에도 좀 오류가 생겨서 리포트를 작성하진 못함. 추후 기회가 있다면 다시 시도해볼 생각이 있음.

4. 2학기 창독

'데이터 과학 기반의 파이썬 빅데이터 분석'이라는 책을 선정하여 읽고있는 중. 책을 읽으면서 빅데이터의 전문적인 내용과 그를 적용시킬수있는 코딩방식을 학습하고있음. 잘 모르겠는 부분이나 궁금한 내용은 인터넷으로 따로 찾아볼 계획.

# data[].attributes.headline
고등학교 활동과의 연결점

# data[].attributes.subject
고등학교 활동과의 연결점

# data[].attributes.body
1. '선형대수학'

1학기 수학 탐구 주제였던 '그래프 이론' 더 학습. 2학기 수학 탐구 주제는 그래프 이론 + 행렬로 정할 계획. 이를 바탕으로 산업공학에서 필수적인 수학 이론인 선형대수학을 미리 공부할 수 했다는 것을 강조할 수 있음.

2. '유체역학'

챌린저 트랙 과학탐구대회에서 '유체역학을 통한 파이프 내 유체의 흐름 분석 및 산업 배관 시스템의 최적화' 진행하려했으나 일단 실패. 추후 다른 내용을 좀 섞든지해서 다시 시도해보고 성공 시 그 내용을 활용할 수 있음.

3. '데이터 분석'

창독 시간에 '빅데이터 분석'과 관련된 서적 읽고있음. 빅데이터의 전반적인 내용을 학습하고 파이썬을 통해 스스로 빅데이터 분석해볼 계획. 데이터 과학자의 인재상을 지니고 있다는 점 부각할 수 있음.

4. '상품 유통망 설계'

아마 체인지 메이커에서 이 내용을 핵심으로 다룰 듯함. 그래프 이론과 그래프 분석 기법을 바탕으로 파이썬을 사용해 최적 상품 유통망을 설계해보고픔. 따로따로 탐구, 학습했던 내용들을 여기서 하나로 합치는 느낌.

# data[].attributes.body
~ 9/22 : 필요한 공부 모두 끝내기

그래프 이론

파이썬

빅데이터 분석 기법

9/23 ~ 9/29 : 모델링 및 데이터 수집

데이터 수집 과정이 꽤 복잡

-> 인터넷과 서적 참고하여 배송 및 위치 데이터 수집

9/30 ~ 10/6 : 데이터 전처리

이 부분이 가장 힘든 부분

-> 할 수 있는 만큼 해보고 계속 해결이 안되면 정보 선생님께 질문 후 다시 해보기

10/23 ~ 10/25 : 데이터 대입 및 시각화

그냥 알고리즘에 대입하는 절차

유통망 최적화는 대충 여기서 마무리됨

10/26 ~ 10/27 : 지도 생성

위도와 경도 값을 기준으로 Folium 지도 생성

노드 마커 추가하여 경유지 표시

웹 브라우저에서 시각화 가능

10/28 ~ : 리포트 작성

그 전부터 금요일마다 계속 선생님과 대화 나누며 활동 완성시키기

글 쓰기에 너무 시간 오래 쓰지 말기

# data[].attributes.body
1. 행렬

괜찮은 블로그 찾아놓음. 하루에 두 포스트씩 완벽하게 학습한다는 느낌으로 꾸준히 공부. 정모르겠으면 따로 강의 영상을 보는 방법도 있음.

2. 네트워크 이론

사실 구글에 검색해도 어려운 내용밖에 없어서 어떻게 공부할지 좀 더 생각해볼 필요가 있음.

3. 유체역학

관련 전문 서적 읽으면서 핵심 개념 이해하기. 방학 때 어느정도 이해한 내용들이 있기에 비교적 수월할거라 생각함.

4. 데이터 분석 기법

창독 시간에 선정한 책 읽으면서 공부. 구글에 파이썬 강의는 널렸으니 딱히 문제될부분은 없을듯함.

# data[].attributes.body
그래프 이론을 파이썬에 적용시켜주는 라이브러리 (일종의 툴)

# data[].attributes.attachment_link.readable_text
NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

Software for complex networks

Data structures for graphs, digraphs, and multigraphs

Many standard graph algorithms

Network structure and analysis measures

Generators for classic graphs, random graphs, and synthetic networks

Nodes can be "anything" (e.g., text, images, XML records)

Edges can hold arbitrary data (e.g., weights, time-series)

Open source 3-clause BSD license

Well tested with over 90% code coverage

Additional benefits from Python include fast prototyping, easy to teach, and multi-platform

# data[].attributes.attachment_link.description
NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

# data[].attributes.body
그래프

노드와 그 사이를 잇는 간선으로 이루어진 구조

수학적으로 그래프 G는 노드집합 V와 간선 집합 E로 구성됨

유향 그래프 / 무향 그래프

간선 (a, b)와 (b, a)가 같다고 보는 그래프는 무향 그래프고 다르다고 보는 그래프는 무향 그래프임

방향이 있다 없다는 의미에서 방향성 그래프와 비방향성 그래프라 부르기도함

NetworkX

다루기 쉽다는게 큰 장점

-> 이 라이브러리를 사용하여 코딩할 계획

그래프를 만드는 클래스인 Graph, DiGraph를 제공함

-> Graph 클래스 : 비방향성 그래프 담당

-> DiGraph 클래스 : 방향성 그래프 담당

메서드

노드 추가 : add_node

간선 추가 : add_edge

노드 개수 카운팅

노드의 개수 (즉 그래프의 크기) : |G| 또는 |V|

간선의 개수 : |E|

카운팅 : len 명령 -> len(g1)

number_of_nodes -> g1.number_of_nodes()

number_of_edges -> g1.number_of_edges()

노드의 인접성

간선 (a,b)가 E 안에 존재할 때 두 노드는 인접

인접한 두 노드는 서로 이웃이라고 함

인접성 확인 : Graph 클래스의 neighbors 메서드로 인수로 받은 노드에 인접한 노드 생성하여 확인 가능함

셀프 루프

노드에서 출발하여 자기 자신으로 바로 돌아오는 간선 (약간 합성함수 느낌인듯)

Graphviz로만 시각화 가능함

그래프 시각화

Graphviz : 복잡한 네트워크나 구조를 시각화할 때 유용함

DOT 언어를 사용하여 그래프 정의 후 다양한 포맷으로 출력할 수 있음

Pydot : Graphiz의 DOT 언어를 처리할 수 있게 해주는 라이브러리로 그래프 시각화에 필수적임

DOT 언어 : 그래프 구조를 정의하기 위해 Graphviz에서 사용하는 언어

워크, 패스, 사이클, 트레일

워크 : 어떤 노드를 출발해서 다른 노드로 도달하기 위한 인접한 노드의 순서열

패스 : 워크 중에서 시작과 끝을 제외한 다른 노드에 대해서 동일한 노드를 두 번 이상 지나지 않는 워크

사이클 : 패스 중에서 시작점과 끝점이 동일한 패스 (사이클이 없는 패스는 어사이클릭 그래프라 함)

트레일 : 어떠한 노드든 동일한 노드를 두 번 이상 지나지 않는 워크

최단 패스

has_path 명령 : 두 노드간에 패스가 존재하는지 분석

shortest_path 명령 : 최단 패스 출력

클리크

클리크 : 무방향성 그래프에서 모든 노드끼리 간선이 존재하는 노드 집합

최대 클리크 : 클리크에 포함된 노드에 인접한 다른 노드를 추가하면 클리크가 아니게 되는 것

# data[].attributes.attachment_link.title
그래프 이론 기초 — 데이터 사이언스 스쿨

# data[].attributes.attachment_link.description
그래프(graph)는 다음 그림처럼 노드(node, vertex)와 그 사이를 잇는 간선(edge)으로 이루어진 구조를 말한다.

# data[].attributes.body
다익스트라 알고리즘

하나의 출발점에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘

주로 가중치가 양수인 그래프에서 사용

작동 원리 (간단하게만)

출발 노드에서 시작하여 최단 거리가 가장 짧은 노드를 반복적으로 선택해 가며 그 노드를 거쳐 다른 노드로 가는 경로를 계산하여 더 짧은 경로가 발견되면 갱신하는 방식

1. 먼저 출발 노드의 거리를 0으로 설정하고 나머지 노드의 거리는 무한대로 설정

2. 출발 노드와 인접한 노드들의 최단거리 테이블을 업데이트

3. 가장 가중치가 작은 노드로 이동 후 그 노드의 이웃 노드들의 최단거리 테이블을 업데이트

4. 업데이트를 반복하다 목표 노드에 도달하게되면 종료 (모든 노드에 방문하면 끝)

순차 탐색 (탐욕법)

그냥 위에서 설명한 내용과 똑같음

'방문하지 않은 노드 중 거리값이 가장 작은 노드'를 선택해 다음 탐색 노드로 삼는 방식

노드의 개수만큼 순차 탐색을 진행해야하기에 시간이 많이 걸릴 수 있음

우선순위 큐

큐에 삽입되는 형태 : <거리, 노드> 꼴

순차 탐색을 쓰는 구현과 달리 방문여부를 기록한 배열이 없어도 됨

(우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하고 기존 최단 거리보다 크면 무시)

만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣음 (업데이트)

거리값이 가장 작은 노드를 계속해서 큐에서 추출하고 처리

모든 노드가 처리됐을때 (큐가 빌때) 종료

코드 구현

'시작 노드, 끝 노드, 사이 간선의 가중치'를 인접 행렬 그래프에 넣어 표현

-> 인접 행렬도 가볍게 공부하기

# data[].attributes.attachment_link.readable_text
1-1. 개요

다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.

1-2. 동작 단계

① 출발 노드와 도착 노드를 설정한다.
② '최단 거리 테이블'을 초기화한다.
③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
④ 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.
⑤ ③~④의 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False 로 초기화하여 방문하지 않았음을 명시한다.

1-3. 동작 예

출발 노드는 1번, 도착 노드는 6번이라 하고 거리 테이블을 전부 큰 값, 여기서는 inf(무한대)로 초기화했다. 각 노드들을 잇는 간선의 가중치 역시 표시했다.

출발 노드를 먼저 선택하고 거리를 0으로 한다.

1번 노드와 연결된 인접 노드는 2, 4이다. 그곳까지 가는 거리를 각각 기존의 거리값과 비교해 최솟값으로 업데이트한다. 가령 2의 경우 inf와 2 중 작은 값인 2를 택해 할당한다.
또한 인접 노드까지의 거리를 모두 업데이트한 1번 노드는 방문 표시를 한다.
최근 갱신한 테이블 기준, 방문하지 않는 노드 중 가장 거리값이 작은 번호를 다음 노드로 택한다. 위 상태에서는 4번 노드이다.

4번 노드에서 같은 작업을 수행한다. 4번과 연결된 2, 5번까지 오는 거리를 계산한다. 가령 5의 경우엔 4번까지 오는 데 필요한 거리 + 4->5 간선의 가중치 값인 2와 기존의 값인 inf 중 최솟값을 계산하고, 2번 노드의 경우엔 기존 값인 2와 4번을 거쳐가는 값인 1+2 = 3을 비교한다. 그렇다면 2번 노드는 기존 값이 더 크므로 업데이트하지 않는다. 즉, 1번에서 바로 2번으로 가는 것이 1->4를 거쳐 2번으로 가는 길보다 더 적게 걸린단 뜻이다.
다음으로 선택될 노드는 아직 방문하지 않은 노드 2, 3, 5, 6 중 거리값이 가장 작은 노드이므로 2 또는 5이다. 거리 값이 같다면 일단 인덱스가 작은 노드를 택한다고 하고 2번으로 가보자.

2번 노드와 연결된 3, 4번 노드에 대해 같은 과정을 반복한다.
그 다음 노드는 3, 5, 6번 중 가장 거리값이 작은 5번 노드가 되겠다.

5번 노드와 연결된 6번 노드에 같은 과정을 반복한다.
다음 노드를 선택해야 하는데, 아직 방문하지 않은 3번과 6번 중 거리값이 작은 것은 6번이다. 그런데 6번은 더 이어지는 노드도 없는데다 도착 노드이다. 따라서 알고리즘을 종료한다.

최종적으로는 1번에서 6번까지 오는 데 1 - 4 - 5 - 6의 경로를 거치고 최소 거리는 4가 된다.

1-4. 특징

위 동작 예시에서 볼 수 있듯이, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.
또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.
도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다.

다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다는 중요한 특징이 있다.

위 그림의 상황에서 1 → 4의 경로가 최단경로이려면 3+k가 1보다 커야 한다. 즉, k > -2가 성립해야 한다. 반대로 k가 -5라고 한다면 오히려 1 → 2 → 4 경로가 더 최단 경로가 된다. 그 말인 즉, 1번에서 연결된 노드 중 4번이 가중치가 적다는 이유로 최단 거리를 1이라 할 수는 없다는 이야기이다.
따라서 다익스트라 알고리즘을 사용하기 위해서는 정점 사이를 잇는 간선의 가중치가 양수여야 한다. 그래야 한 번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 되는 것이다.

1-5. 구현 방법

다익스트라 알고리즘을 구현하는 방법에는 '방문하지 않은 노드'를 다루는 방식에서 '순차 탐색'을 할 것이나 '우선순위 큐'를 쓸 것이냐로 나뉜다. 자세한 방식은 아래에서 계속한다.

'방문하지 않은 노드 중 거리값이 가장 작은 노드'를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이 된다. 즉 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행해야 한다. 따라서 노드 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 의 시간이 걸린다.

아래 코드에서 dist[]는 각 노드까지의 최소 거리를 저저장하고, visited[]는 방문 여부를, map[][] 은 한 노드에서 다른 노드로의 거리를 저장하고 있다.

파이썬으로 구현한 코드는 아래 링크를 참고한다.
💎[Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘

3-1. 특징

순차 탐색을 사용할 경우 노드 개수에 따라 탐색 시간이 매우 오래 걸릴 수 있다. 이를 개선하기 위해 우선순위 큐를 도입하기도 한다.
거리 값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.
파이썬의 경우 PriorityQueue나 heapq 라이브러리로 우선순위 큐, 최소 힙이 지원되며, C++의 경우 <queue> 라이브러리에서 최대 힙을 지원하는 priority_queue 를 사용할 수 있다. 최대 힙을 최소 힙으로 쓰려면 저장되는 값에 - 를 붙여 음수로 만들면 된다.

우선순위 큐에서 사용할 '우선순위'의 기준은 '시작 노드로부터 가장 가까운 노드'가 된다. 따라서 큐의 정렬은 최단 거리인 노드를 기준으로 최단 거리를 가지는 노드를 앞에 배치한다.

위의 순차 탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문 여부를 기록할 배열은 없어도 된다. 우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하므로 기존 최단 거리보다 크다면 무시하면 그만이다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다. 우선순위 큐에 삽입되는 형태는 <거리, 노드> 꼴이다.

3-2. 동작 예시

출발 노드인 1번의 거리를 업데이트하고 우선순위 큐에 넣는다.

큐에서 맨 앞 노드인 <거리 0, 노드 1>을 꺼내 그 인접 노드를 조사한다. 거리값이 업데이트 되는 노드만, 즉 최소 거리로 업데이트 되는 노드만 큐에 넣는다. 큐는 거리값이 작은 순서대로 정렬된다.

<거리 1, 노드 4>를 꺼내 그 인접 노드를 조사한다. 최소 거리로 거리가 업데이트 된 5번을 큐에 넣는다. 2번의 경우 기존의 거리값인 2보다 1 + 2 = 3이 더 크므로 2번은 큐에 넣지 않는다.

같은 과정의 반복으로 <거리 2, 노드 2>의 인접 노드를 조사하고 거리값이 갱신된 노드만 큐에 넣는다. 3번이 큐에 들어간다.

큐가 빌 때까지 해당 과정을 반복한다.

최종적으로 도착 노드의 거리 값이 최소 거리가 된다.

3-3. 코드 구현

그래프의 형태는 '시작 노드 / 끝 노드 / 그 사이 간선의 가중치'를 입력 받아 인접 행렬 graph[][] 에 넣어 표현한다.

파이썬으로 구현한 코드는 아래 링크를 참고한다.
💎 Python으로 다익스트라(dijkstra) 알고리즘 구현하기
💎[Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘

3-4. 시간 복잡도

YounghunJo, "
[Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘," Tistory - 앎의 공간

해피니s, "[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현," Tistory - code_lab

Min Jae Park, "Python으로 다익스트라(dijkstra) 알고리즘 구현하기," justkode

YounghunJo, "[Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘," Tistory - 앏의 공간

얍문, "[ 다익스트라 알고리즘 ] 개념과 구현방법 (C++)," Tistory - 얍문's Coding World

공부하는 식빵맘, "Chapter 4-5. 다익스트라 최단 경로 알고리즘," GitHub blog - 평생 공부 블로그 : Today I Learned

# data[].attributes.attachment_link.description
다익스트라 알고리즘과 구현 방식, 예시 문제

# data[].attributes.headline
파이썬에서 다익스트라 사용

# data[].attributes.subject
파이썬에서 다익스트라 사용

# data[].attributes.body
while문을 기본으로 사용

(완벽하게 이해하진 못해서 그냥 계속 인터넷 참고하며 코드 짜면 될듯)

# data[].attributes.attachment_link.title
파이썬 다익스트라 알고리즘 사용하기

# data[].attributes.attachment_link.description
다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 ‘에츠허르 데이크스트라’라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0,…

# data[].attributes.body
티스토리에 행렬 자료 매우 많으니까 편하게 참고

# data[].attributes.attachment_link.description
행렬은 대학교에서 자주 사용하지만 고등학교에서는 배우지 않은 부분입니다. 하지만 행렬은 다양한 분야에서 사용되기 때문에 반드시 알아야 하는 부분입니다. 공학에서는 선형연립방정식의 풀이를 간편하게 하기 위해서 사용이 되고, 이론적인 n차원 공간을 표현하기 위해서 행렬을 이용하기도 합니다. 목차 1. 행렬의 정의와 성질 2. 행렬의 덧셈 3. 행렬의 곱셈 1. 행렬의 정의와 성질 행렬은 수로 된 직각 배열을 의미합니다. 간단히 말해서, 수, 문자를 직사각형으로 나열한 것을 의미합니다. $$A=\begin {bmatrix} a_{11} &a_{12} & \dots & a_{1n} \\ a_{21}&a_{22} & \dots & a_{2n} \\ \dots & \dots & \dots & \dots \\ a_{…

# data[].attributes.attachment_link.description
📌 큐 (Queue)스택(stack)과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조FIFO(First In First Out) 구조이다. ✔ 큐 사용을 위해 필요한 주요 연산```createQueue() : 공백 큐 생성enQueue(A) : 원소 A를 삽입enQueue(B) : 원소 B를 삽입deQueue(): 원소 반환/삭제enQueue(C) : 원소 C 삽입deQueue(): 원소 반환/삭제deQueue(): 원소 반환/삭제``` 🚀 클래스로 구현한 큐# 요소의 정보를 저장하기 위한 클래스class Node: # 데이터를 저장할 변수 # 다음 요소를 가리키기 위한 변수 def __init__(self, value): self.value = value…

# data[].attributes.body
우선순위 큐를 포함해서 여러가지 큐의 종류를 설명해놓은 자료

막 자세하기 읽을 필요는 없음

# data[].attributes.attachment_link.readable_text
목차

💬 큐(Queue)란?

💬 선형 큐

💬 연결 큐

💬 우선순위 큐(Priority Queue)

💬 큐의 활용: 버퍼(Buffer)

💬 BFS (Breadth First Search)

💬 덱 (deque)

📑 연습문제

💬 큐 (Queue)란?

[자료구조🧬] 큐 (Queue)

큐 (Queue)스택(stack)과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조FIFO(First In First Out) 구조이다. ✔ 큐 사용을 위해 필요한 주요 연산```createQueue() : 공백 큐 생성enQueue(A) : 원소 A를 삽입en

dionysaurus.tistory.com

💬 선형 큐

더보기

1차원 배열을 이용한 큐(Queue)

큐의 크기 = 배열의 크기

front: 저장된 첫 번째 원소의 인덱스

rear: 저장된 마지막 원소의 인덱스

초기 공백 큐를 생성하려면 크기가 n인 1차원 배열을 생성하고 front = rear = -1 로 초기화하면 됨

✔ 상태 표현

초기 상태: front = rear = -1

공백 상태: front == rear

포화 상태: rear == n - 1 (n: 배열의 크기)

✔ 선형 큐의 연산

1. 삽입: enQueue(item)

마지막 원소 뒤에 새로운 원소 삽입

def enQueue(item): global rear if isFull(): print("Queue_Full") else: rear += 1 Q[rear] = item

2. 삭제 deQueue()

가장 앞에 있는 원소 삭제

deQueue(): if isEmpty() then Queue_Empty() else: front += 1 return Q[front]​

💡 공백상태 및 포화 상태 검사: isEmpty(), isFull()

def isEmpty(): return front == rear def isFull(): return rear == len(Q) - 1

3. 검색 Qpeek()

가장 앞에 있는 원소를 검색하여 반환
(현재 front의 한자리 뒤에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환함)

def Qpeek(): if isEmpty(): print("Queue_Empty") else: return Q[front + 1]​

💬 원형 큐

더보기

💡 선형 큐의 문제점을 해결하기 위해 등장한 자료구조

선형 큐를 이용하여 원소의 삽입/삭제를 반복하는 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 rear = n-1인 상태 즉, 포화상태로 인식하여 더이상의 데이터 삽입을 수행하지 않게 된다.

✔ 해결방법 1
매 연산(삽입/삭제)이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시키는 방법
But, 원소 이동에 많은 시간이 소요되어 큐의 효율성이 매우 떨어짐

✔ 해결방법 2
1차원 배열에 대해 논리적으로는 배열의 처음과 끝이 연결된 원형 형태의 큐를 이룬다고 가정하여 사용하는 방법

원형 큐의 논리적 구조

💡 원형 큐의 특징

초기 공백 상태 : front = rear = 0

Index의 순환
front와 rear의 위치가 배열의 마지막 인덱스(n - 1)를 가리킨 후, 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동 -> 이를 구현하기 위해 나머지 연산자(mod)를 사용

공백 상태와 포화 상태 구분을 위해 front가 있는 자리는 항상 사용하지 않고 빈자리로 둠

✔ 선형 큐와 원형 큐의 삽입/삭제 위치

✔ 원형 큐의 연산

1. 생성: create Queue

2. 삽입: enQueue(A)

def enQueue(item): global rear if isFull(): print("Queue_Full") else: # rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련 rear = (rear + 1) % len(cQ) # 그 인덱스에 해당하는 배열원소 cQ[rear]에 item 저장 cQ[rear] = item # 포화상태: 삽입할 rear의 다음 위치 == 현재 front def isFull(): # (rear + 1) mod n == front return (rear + 1) % len(cQ) == front

3. 삭제: deQueue()

def deQueue(): global front if isEmpty(): print("Queue_Empty") else: # front 값을 조정하여 삭제할 자리를 준비 front = (front + 1) % len(cQ) # 새로운 front 원소를 리턴하여 삭제와 동일한 기능 동작 return cQ[front] # 공백상태: front == rear def isEmpty(): return front == rear

🧐 공백상태 및 포화상태 검사: isEmpty(), isFull()

# 공백상태: front == rear def isEmpty(): return front == rear # 포화상태: 삽입할 rear의 다음 위치 == 현재 front def isFull(): # (rear + 1) mod n == front return (rear + 1) % len(cQ) == front

💬 연결 큐

더보기

단순 연결 리스트(Linked List)를 이용한 큐

큐의 원소: 단순 연결 리스트의 노드

큐의 원소 순서: 노드의 연결 순서로, 링크로 연결되어 있음

front: 첫 번째 노드를 가리키는 링크

rear: 마지막 노드를 가리키는 링크

✔ 상태 표현

초기 상태: front = rear = null

공백 상태: front = rear = null

✔ 연결 큐의 연산

# 1. 공백 큐 생성 (front = rear = 0) createLinkedQueue() # 2. 원소 A 삽입 enQueue(A) # 3. 원소 B 삽입 enQueue(B) # 4. 원소 삭제 deQueue() # 5. 원소 삭제 deQueue() # front = rear = 0 이 됨​

💬 우선순위 큐 (Priority Queue)

더보기

우선순위를 가진 항목들을 저장하는 큐로, FIFO 순서를 따르지 않고 우선순위가 높은 순서대로 먼저 출력됨

<details>
<summary>우선순위 큐 적용 분야</summary>
- 시뮬레이션 시스템

- 네트워크 트래픽 제어 (네트워크에서 패킷에 우선순위를 두는 것을 우선순위 큐로 구현함)

- 운영체제의 테스크 스케줄링</details>

✔ 우선순위 큐의 구현 방법

그래프나 트리 형태로 구현해야 하며, 일반적인 배열 형태로는 구현하기 어려움

1. 배열 이용

배열을 이용하여 자료를 저장하며, 원소 삽입 과정에서 우선순위를 비교하여 적절한 위치에 삽입함

문제점
배열을 사용하므로, 삽입/삭제 연산이 일어날 때 원소의 재배치 발생 -> 이에 시간 및 메모리 낭비 발생

2. 리스트(List) 이용

💬 큐의 활용: 버퍼(Buffer)

더보기

💡 버퍼(Buffer) 란?

데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역

→ 데이터의 입출력에 가장 많은 리소스가 사용되므로, 이를 해결하기 위해 한 번에 많은 데이터를 입출력하도록 구현하는 것이 유리하다. 이 과정에서 버퍼링이 발생한다.
( 버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미)

✔ 버퍼의 자료 구조

버퍼는 일반적으로 입출력 및 네트워크 관련 기능에 활용된다. 따라서 순서대로 입력/출력/전달되어야 하므로 FIFO(First In First Out) 방식의 자료구조인 큐(Queue)가 활용된다.

💬 BFS (Breadth First Search, 너비 우선 탐색)

더보기

탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점들을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 (인접한 정점들에 대해 탐색한 후, 차례로 다시 너비우선탐색(BFS)을 진행해야 하므로, 선입선출(FIFO) 형태의 자료구조인 큐(Queue)를 활용함)

인접한 정점을 순차적으로 방문할 때에는, 데이터 값에 대해 내림차순으로 방문한다.

완전 탐색이 가능하긴 하지만, 일반적으로 DFS와 달리 완전 탐색을 실행하지 않는다는 특징을 가진다.

📌 최소 몇 번의 연산을 해야하는가에 대한 문제를 해결할 땐 항상 DFS보단 BFS가 더 적합하다!
(DFS는 가지치기에 유리함)

✔ BFS의 장점

정해진 개수만큼 큐를 생성해도 충분하다.

재귀 호출에서의 장점을 가짐(강의 다시 보기..)

# G: 그래프, v: 탐색 시작점, n: 정점의 개수 def bfs(G, v, n): visited = [0] * (n + 1) # 큐 생성 queue = [] # 시작점 v를 큐에 삽입 queue.append(v) # 큐가 비어있지 않는 동안 while queue: # 큐의 첫 번째 원소를 반환 -> dequeue() t = queue.pop(0) # 방문하지 않은 곳인 경우, if not visited[t]: # 방문한 곳으로 표시해둠 visited[t] = True # 정점 t에서 할 일 수행 visit(t) # t와 연결된 모든 정점에 대해 for i in G[t]: # 방문되지 않은 곳이라면 if not visited[i]: # 큐에 넣기 queue.append(i) def visit(n): ...

① 초기 상태

Visited 배열 초기화

Q (큐) 생성

enqueue(A)

② A 점부터 시작

dequeue()

A 점을 방문한 것으로 표시

A의 인접점을 euqueue()

③ 탐색 진행

dequeue()

B점 방문한 것으로 표시

B의 인접점을 enqueue()

dequeue()

C점 방문한 것으로 표시

C의 인접점을 enqueue()

dequeue()

D점 방문한 것으로 표시

D의 인접점을 enqueue()

이후 Q에 대해 dequeue()를 반복하며 내보내진 점을 방문한 것으로 표시하고, 해당 점의 인접점을 enqueue() 함

④ Q가 비면 탐색 종료

🎯 BFS 예제

# G: 그래프, v: 탐색 시작점, n: 정점의 개수 def BFS(G, v, n): visited = [0] * (n + 1) # 큐 생성 queue = [] # 시작점 v를 큐에 삽입 queue.append(v) visited[v] = 1 # 큐가 비어있지 않는 동안 while queue: # 큐의 첫 번째 원소 반환 t = queue.pop(0) visit(t) # t와 연결된 모든 정점에 대해 for i in G[t]: # 방문되지 않은 곳이라면 if not visited[i]: # 큐에 넣음 queue.append(i) # n으로부터 1만큼 이동 visited[i] = visited[t] + 1

💬 덱 (deque)

더보기

컨테이너 자료형 중 하나

💡 deque 객체
양쪽 끝에서 빠르게 추가 및 삭제를 할 수 있는 List류의 컨테이너이다.

✔ 덱 연산

from collections import deque q = deque() # append(x): 오른쪽에 x 요소를 추가함 q.append(1) # enqueue() # popleft(): 왼쪽에서 요소를 제거하여 반환함 (요소가 없으면 IndexError 발생) t = q.popleft() # dequeue()

📑 연습문제

더보기

선형 큐
큐를 구현하여 아래 동작을 확인해보자.
세 개의 데이터 1, 2, 3을 차례로 큐에 삽입하고 큐에서 세 개의 데이터를 차례로 꺼내어 출력
(1, 2, 3이 출력되어야 함)

Queue를 이용하여 마이쮸 나눠주기 시뮬레이션을 해보자.
엔터(Enter)를 칠 때마다 아래의 정보를 화면에 출력

큐에 있는 사람의 수

현재 일인당 나눠주는 사탕의 수

현재까지 나눠준 사탕의 수

""" - 엔터(Enter)를 칠 때마다 아래의 정보를 화면에 출력 1. 큐에 있는 사람의 수 2. 현재 일인당 나눠주는 사탕의 수 3. 현재까지 나눠준 사탕의 수 """ import time def isFull(): global queue global rear if rear == len(queue) -1 : return True return False def enQueue(item): global queue global rear if isFull(): print("Queue is Full now!") else: rear += 1 queue[rear] = item def deQueue(): global queue global front global rear if front == rear: print("Queue is Empty now!") else: front += 1 return queue[front] def pressEnter(): global front global rear global queue global myChew input("엔터를 입력해주세요.") who = None for i in range(front + 1, rear + 1): who = queue[i][0] myChew -= queue[i][1] deQueue() print(f'큐에 있는 사람의 수: {rear - front}') print(f'현재 일인당 나눠주는 사탕의 수: {queue[i][1]}') print(f'현재까지 나눠준 사탕의 수: {20 - myChew}') print() print('**************************************') print() time.sleep(0.1) return who myChew = 20 front = rear = 0 queue = [None] * 1000000 cnt = 1 while myChew != 0: k = 1 n = cnt + 1 for i in range(cnt): enQueue((k, n - k)) k += 1 who = pressEnter() front = rear cnt += 1 print(f'사탕을 마지막으로 가져간 사람: {who}')

# 출력 결과
엔터를 입력해주세요.
큐에 있는 사람의 수: 0
현재 일인당 나눠주는 사탕의 수: 1
현재까지 나눠준 사탕의 수: 1
**************************************

엔터를 입력해주세요.
큐에 있는 사람의 수: 1
현재 일인당 나눠주는 사탕의 수: 2
현재까지 나눠준 사탕의 수: 3

큐에 있는 사람의 수: 0
현재 일인당 나눠주는 사탕의 수: 1
현재까지 나눠준 사탕의 수: 4
**************************************

엔터를 입력해주세요.
큐에 있는 사람의 수: 2
현재 일인당 나눠주는 사탕의 수: 3
현재까지 나눠준 사탕의 수: 7

큐에 있는 사람의 수: 1
현재 일인당 나눠주는 사탕의 수: 2
현재까지 나눠준 사탕의 수: 9

큐에 있는 사람의 수: 0
현재 일인당 나눠주는 사탕의 수: 1
현재까지 나눠준 사탕의 수: 10
**************************************

엔터를 입력해주세요.
큐에 있는 사람의 수: 3
현재 일인당 나눠주는 사탕의 수: 4
현재까지 나눠준 사탕의 수: 14

큐에 있는 사람의 수: 2
현재 일인당 나눠주는 사탕의 수: 3
현재까지 나눠준 사탕의 수: 17

큐에 있는 사람의 수: 1
현재 일인당 나눠주는 사탕의 수: 2
현재까지 나눠준 사탕의 수: 19

큐에 있는 사람의 수: 0
현재 일인당 나눠주는 사탕의 수: 1
현재까지 나눠준 사탕의 수: 20
**************************************

사탕을 마지막으로 가져간 사람: 4

BFS (너비 우선 탐색)
아래는 연결되어 있는 두 개 정점 사이의 간선을 순서대로 나열해 둔 것이다. 모든 정점을 너비우선탐색(BFS)하여 경로를 출력하여라. (시작 정점은 1로 한다)

# 입력 값 1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7 # 출력 값 1 - 2 - 3 - 4 - 5 - 7 - 6

→ 나의 작성 코드!

# G: 그래프, v: 탐색 시작점, n: 정점의 개수 def bfs(G, v, n): visited = [0] * (n + 1) # 큐 생성 queue = [] # 시작점 v를 큐에 삽입 queue.append(v) # 큐가 비어있지 않는 동안 while queue: # 큐의 첫 번째 원소를 반환 -> dequeue() t = queue.pop(0) # 방문하지 않은 곳인 경우, if not visited[t]: # 방문한 곳으로 표시해둠 visited[t] = True # 정점 t에서 할 일 수행 visit(t) # t와 연결된 모든 정점에 대해 for i in G[t]: # 방문되지 않은 곳이라면 if not visited[i]: # 큐에 넣기 queue.append(i) print(t, end = ' ') def visit(t): pass # 입력 데이터 input_data = '1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7' # 7개의 노드로 구성 N = 7 # 그래프 생성 graph = [[] for i in range(N + 1)] arr = list(map(int, input_data.split())) for i in range(0, len(arr) - 1, 2): v1, v2 = arr[i], arr[i + 1] graph[v1].append(v2) graph[v2].append(v1) # bfs 탐색 실시 bfs(graph, 1, N)

# data[].attributes.attachment_link.description
목차💬 큐(Queue)란?💬 선형 큐💬 연결 큐💬 우선순위 큐(Priority Queue)💬 큐의 활용: 버퍼(Buffer)💬 BFS (Breadth First Search)💬 덱 (deque)📑 연습문제 💬 큐 (Queue)란? [자료구조🧬] 큐 (Queue)큐 (Queue)스택(stack)과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조FIFO(First In First Out) 구조이다.

# data[].attributes.body
수학 : 그래프 이론 공부 -> 최단 거리 알고리즘도 간단하게 알아보긴하는데 네트워크 이론을 통한 6단계 법칙 증명이 진짜 목표

-> 그래프 이론을 활용한 네트워크 이론과 인접 행렬을 바탕으로 파이썬 사용해서 6단계 법칙 증명하기

진로 : 단일 운송수단에서 거리와 연료 소비량을 고려한 가상의 최적 유통망 설계
-> 사실 운송수단마다 배출하는 기체의 종류와 양이 다르기에 환경오염 완화에 큰 도움 안될듯

사회 : 거리와 연료 소비량(단일 운송수단 내)을 고려한 유통망 최적화에서 환경오염 효과가 있을지, 그리고 없다면 보완할수있는부분이 뭐인지
-> 최적 운송수단을 선택하기

과학 : 연료와 배출기체의 상관관계를 분석하고 배출기체의 오염량 분석하기

수업량 : 디지털 트윈 기술을 활용하여 최적 운송수단 선택 (연료 소비량, 효율성, 비용, 배출기체의 환경파괴량 고려)
-> 시뮬레이션으로 운송 수단 성능 예측
(이때 진로에서 만들어놓은 최적 유통망과 과학에서 탐구한 배출기체의 오염량 대입)

# data[].attributes.headline
그래프 이론에서의 인접 행렬

# data[].attributes.subject
그래프 이론에서의 인접 행렬

# data[].attributes.body
좀 어려운 내용

그래프 이론 수학 탐구할 때도 이런 자료 많이 참고할 예정

# data[].attributes.attachment_link.title
[자료구조] Graph - 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List)

# data[].attributes.attachment_link.description
목차 Graph Directed Graph & Undirected Graph Cyclic Graph & Acyclic Graph Graph 표현 방법 Graph Graph의 구조 여러 점들이 서로 연결되어 있는 관계를 표현한 자료구조 트리(Tree)도 그래프(Graph)의 한 형태 Graph의 구조의 용어 정점(Vertex) 또는 노드(Node): 데이터가 저장되는 기본 원소 간선(Edge): 정점간의 관계를 나타내며 무방향, 단방향, 양방향의 방향성을 갖음 인접(Adjacency): 두 정점이 간선으로 이어진 경우, 두 정점은 인접하다고 표현 인접(Adjacent Vertex): 간선에 의해 이어진 정점 진입차수(In-Degree): 정점으로 들어오는 간선의 개수 진출차수(Out-Degree): 정점에…

# data[].attributes.headline
그래프 이론 + 행렬 좀 더

# data[].attributes.subject
그래프 이론 + 행렬 좀 더

# data[].attributes.attachment_link.readable_text
그래프

연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조이다. 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합이다. 그래프 G=(V,E)로 V는 그래프에 있는 정점들의 집합, E는 정점을 연결하는 간선들의 집합이다.

차수

정점에 부속되어있는 간선의 수이다. 방향 그래프의 정점의(차수=진입차수+진출차수)로 방향 그래프 진입차수(In-degree)는 정점을 머리로 하는 간선의 수이고, 방향 그래프 진출차수(Out-degree)는 정점을 꼬리로 하는 간선의 수이다.

경로

그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것이다. 즉 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트이다. 경로길이(Path length)는 경로를 구성하는 간선의 수이다.

연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조
버스노선도나 전철 노선도, 인간관계를 나타내는 인맥 지도, 수도 배관에 따른 배수 시스템, 물질의 분자구조 등은 선형자료구조나 트리 자료구조로 표현할 수 없음, 이런 경우에 사용할 수 있는 자료구조가 그래프
그래프 G
○ 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합

○ G=(V,E)

V는 그래프에 있는 정점들의 집합

E는 정점을 연결하는 간선들의 집합

그래프의 종류

방향성과 연결 정도에 따라 여러 형태로 나뉨

무방향 그래프(Undirected graph)
두 정점을 연결하는 간선에 방향이 없는 그래프

방향 그래프(Directed graph), 다이그래프(Digraph)
간선에 방향이 있는 그래프

완전 그래프(Complete graph)
각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프
○ 정점이 n개인 무방향 그래프에서 최대의 간선 수 : n(n-1)/2개

○ 정점이 n개인 방향 그래프에서 최대 간선 수 : n(n-1)개

부분 그래프 (Subgraph)
원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프
그래프 G와 부분 그래프 G'의 관계

가중 그래프(Weight graph), 네트워크(Network)

정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프

그래프 관련 용어
① 인접, 부속
○ 그래프에서 두 정점 Vi과 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(Adjacent)되어 있다고 하고, 간선(Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어있다고 함

▶그래프 G1에서 정점 A와 인접한 정점은 B와 D이고, 정점 A에 부속되어 있는 간선은 (A,B)와 (A,D)

② 차수(Degree) : 정점에 부속되어있는 간선의 수
○ 무방향 그래프 G1에서 정점 A의 차수는 2, 정점 B의 차수는 3

○ 방향 그래프의 정점의 차수 = 진입차수 + 진출차수

○ 방향 그래프의 진입차수 (In-degree) : 정점을 머리로 하는 간선의 수

○ 방향 그래프의 진출차수 (Out-degree) : 정점을 꼬리로 하는 간선의 수

▶위 방향 그래프 G3에서 정점 B의 진입차수는 1, 진출차수는 2 정점 B의 전체 차수는 (진입차수 + 진출차수) 이므로 3임
③ 경로(Path)
○ 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것 즉, 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트

○ 경로길이 (Path length) : 경로를 구성하는 간선의 수

▶ 무방향 그래프 G1에서 정점 A에서 정점 C까지 A-B-C경로와 A-B-D-C경로, A-D-C경로, 그리고 A-D-B-C 경로가 있음
④ 단순경로 (Simple path)
○ 모두 다른 정점으로 구성된 경로

▶그래프 G1에서 정점 A에서 정점 C까지의 경로 A-B-C는 단순 경로이고, 경로 A-B-D-A-B-C는 단순경로가 아님
⑤ 사이클 (Cycle)
○ 단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

▶그래프 G1에서 단순경로 A-B-C-D-A와 그래프 G4에서 단순경로 A-B-A는 사이클이 됨
⑥ DAG (Directed acyclic graph)
방향 그래프이면서 사이클이 없는 그래프
⑦ 연결 그래프 (Connected graph)
○ 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프 즉, 떨어져있는 정점이 없는 그래프

○ 그래프에서 두 정점 Vi에서 Vj까지의 경로가 있으면 정점 Vi와 Vj가 연결(Connected)되었다고 함, 트리는 사이클이 없는 연결 그래프
# 단절 그래프 (Disconnected Graph)
연결되지 않은 정점이 있는 그래프

순차 자료구조를 이용한 그래프의 구현 : 인접 행렬

행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법
그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장
○ n개의 정점을 가진 그래프 : n * n 정방행렬

○ 행렬의 행번호와 열번호 : 그래프의 정점

○ 행렬 값 : 두 정점이 인접되어 있으면 1, 인접되어 있지 않으면 0
무방향 그래프의 인접 행렬
행 i의 합 = 열 i의 합 = 정점 i의 차수
방향 그래프의 인접 행렬
행 i의 합 = 정점 i의 진출차수

열 i의 합 = 정점 i의 진입차수

G1 그래프를 인접행렬로 표현하기

연결 자료구조를 이용한 그래프의 구현 : 인접 리스트
각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트
○ 각 정점의 차수만큼 노드를 연결

○ 리스트 내의 노드들은 인접 정점에 대해서 오름차순으로 연결
인접 리스트의 각 노드
○ 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성

○ 정점에 대한 인접 리스트의 헤드포인터는 정점 개수만큼 필요

○ 그래프는 정점의 집합이므로 각 정점에 대한 헤드 포인터를 그룹으로 묶어서 포인터 배열로 구성함
n개의 정점과 e개의 간선을 가진 무방향 그래프의 인접 리스트
○ 헤드 노드 배열의 크기 : n

○ 연결하는 노드의 수 : 2e

○ 각 정점의 헤드에 연결된 노드의 수 : 정점의 차수
n개의 정점과 e개의 간선을 가진 방향 그래프의 인접 리스트
○ 헤드 노드 배열의 크기 : n

○ 연결하는 노드의 수 : e

○ 각 정점의 헤드에 연결된 노드의 수 : 정점의 진출 차수

그래프 G1, G2, G3, G4에 대한 인접 리스트

무방향 그래프

방향 그래프

# data[].attributes.attachment_link.title
그래프의 구조(그래프, 차수, 경로), 인접 행렬

# data[].attributes.attachment_link.description
그래프 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조이다. 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합이다. 그래프 G=(V,E)로 V는 그래프에 있는 정점들의 집합, E는 정점을 연결하는 간선들의 집합이다.차수정점에 부속되어있는 간선의 수이다. 방향 그래프의 정점의(차수=진입차수+진출차수)로 방향 그래프 진입차수(In-degree)는 정점을 머리로 하는 간선의 수이고, 방향 그래프 진출차수(Out-degree)는 정점을 꼬리로 하는 간선의 수이다.경로그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것이다.

# data[].attributes.body
계속 행렬 내용에 벡터가 나와서 좀 알아보려고 간단하게만 읽고 넘어감

파이썬 코드 짤 때 필요한 내용은 아님

# data[].attributes.attachment_link.title
벡터의 곱셉 - 벡터의 내적. (정의, 계산법, 활용법)

# data[].attributes.attachment_link.description
우선, 벡터의 곱셉 중 한 종류인 벡터의 내적은 수학이라는 분야 안에 있는 기술 중 하나이지만, 게임 수학 쪽에 좀 더 연관이 있지 않을까 싶어 게임 수학에 대한 글로써 적을 예정이다. 첫 번째로 내적의 정의를 보고 계산방법과 활용 방법을 소개한 후, 유니티에서 실제로 쓰는 모습을 보여주겠다. 1. 내적의 정의 초등학교 때 곱셈이라는 연산을 배워봤을 것이다. 벡터라는 구조체에도 마찬가지로 곱셈 연산이 있다. 내적과 외적이 그 대상이다. https://alpaca-code.tistory.com/195 (벡터의 외적 글) 벡터의 외적. (정의, 크기 계산법, 계산 방법, 방향 결정법, 활용법) 이번 글에서는 벡터의 외적에 대하여 글을 남기겠다. 벡터의 외적은 기본적으로 벡터의 곱셈이다. 벡터의 곱셈에는 두…

# data[].attributes.headline
친환경 상품 유통망 구축

# data[].attributes.subject
친환경 상품 유통망 구축

# data[].attributes.body
근거 이론

1. 그래프 이론- 어떻게 적용한 건지

2. 데이터 분석 기법 (구체적) - 어떻게 적용

3. 예 : b상품 유통

4. 유류 소모량 비교 분석 - 최적화

5. 유통 차량 연비

6. 유통 차량 연식 - 배기가스 (전기차)

7. 전기차- 비용 올라가

8. 연료 소모량으로 비교-너무 단순해

9. 기업입장 - 연료 소모량 높아도 빠른 배송

10. 사람들은 연료x, 빠른 배송 o

11. 친환경 구척 제안 - 동참하는 회사에 어떤 이익 - 의견제시로만 끝