graph4 그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프를 구현해보도록 하겠습니다. 1. 인접 리스트 인접 리스트 방식은 한 정점에 대해서 인접한 리스트를 연결 리스트로 연결한 것입니다. 다음과 같은 그래프를 인접 리스트로 표현해보면 다음과 같습니다. 그림을 보고나면 대충 감이 잡히실겁니다. 각 정점에 대해서 노드는 간선의 갯수만큼 연결되어있습니다. 맨 처음의 A, B, C, D 노드를 헤드 포인터라고 하며, 이 헤드 포인터는 그래프의 정점의 갯수만큼을 필요로합니다. 즉, 무방향 그래프의 노드의 수 만큼의 연결 리스트가 만들어지고 각 연결 리스트는 정점이 가진 간선의 갯수(차수, degree)만큼의 길이를 가지게 됩니다. 만약 방향 그.. 2021. 10. 5. 그래프 구현 1 - 인접 행렬로 그래프 구현하기 모든 자료구조가 그래왔듯이 그래프를 구현하는 방식에는 순차 자료구조를 이용하는 방식과 연결 자료구조를 이용하는 방식 두가지가 있습니다. 그래프에서도 마찬가지이지만 이름을 조금 다르게 부릅니다. 순차 자료구조를 이용해서 구현하는 것을 인접 행렬 기반 그래프, 연결 자료구조를 이용해서 구현하는 것을 인접 리스트 기반 그래프 라고합니다. 오늘은 첫 번째 순차 자료구조를 이용한 방식인 인접 행렬을 이용한 그래프를 구현해보겠습니다. 1. 인접 행렬 Adjacent Matrix 인접 행렬은 그래프에서 정점이 어떤 간선으로 연결되었는지를 나타내는 행렬입니다. 정점 n개의 그래프에 대해서 nXn행렬을 이용합니다. 이때 정점끼리 연결되어 있다면 행렬의 값을 1로, 연결되어있지 않다면 행렬의 값을 0으로 이용합니다. 예시.. 2021. 10. 4. 그래프 Graph 리스트와 스택, 큐는 1:1 구조의 자료구조, 트리는 1:다의 자료구조였습니다. 그렇다면 다:다 관계를 가진 자료구조도 존재할 것 같다는 생각이 듭니다. 그래프는 이처럼 다:다의 관계를 가진 자료구조 입니다. 1. 그래프 지하철 노선도 처럼 한 역에서 찍어서 다른 역에 도달하는 방법까지는 수많은 방법이 있습니다. 그리고 한 역은 하나의 역만 연결될 수도 있고 수많은 역과 연결되어 있을 수도 있습니다. 이 지하철 노선도가 그래프를 가장 잘 나타내주고 있습니다. 그래프는 다:다의 관계를 가진 정점과 간선으로 이루어진 자료구조입니다. 정점은 객체(Vertex)를 나타내고 간선(Edge)은 객체끼리의 연결을 의미합니다. 이때 그래프 G는 G=(V, E)와 같은 형태로 정의합니다. 간선 V는 객체i와 2. 그래프.. 2021. 10. 4. [Git] git log의 옵션으로 브랜치 정보 확인 지난 시간에 브랜치를 만들고, 여러 분기를 나누어 봤습니다. 그렇게 작업하다보면 브랜치 사이의 관계라던가 브랜치에 대한 간단한 정보를 확인할 필요가 생기게 됩니다. 물론 소스트리 등의 GUI 툴을 이용하게 된다면 편하게 확인할 수 있겠지만 아직 우리는 Git Bash라는 터미널 내에서 작업하고 있습니다. 그렇기에 이 터미널 상에서 이들 정보를 알아 볼 수 있는 방법을 소개해드리고 넘어가고자 합니다. 이 포스트의 내용은 git log 명령의 옵션을 이용합니다. 1. --oneline --oneline옵션은 이름 그대로 커밋 정보를 한 줄로 표시해줍니다. 기존의 git log를 통한 커밋 정보 확인은 커밋 해시, 브랜치, 작성자(Author), 작성일(Date), 그리고 커밋 메세지로 표기되었습니다. 그래서.. 2021. 7. 30. 이전 1 다음 300x250
