그래프
-
1. Dictionary and Copy in Python 그래프는 자료구조의 꽃이라 불릴 정도로 굉장히 중요하고 그 만큼 어려우며 대부분의 코딩테스트의 문제 중에서 킬러 문제를 담당하는 문제입니다. 그렇기 때문에 이를 제대로 이해해 보기 위해 파이썬의 개념을 먼저 익혀보도록 하겠습니다. 만약 파이썬 개념에 대해서 잘 아시는 분이시라면 중반부로 넘어가셔도 좋습니다! Python Dictionary (파이썬 딕셔너리) 우리가 많이 쓰는 리스트 자료구조에는 순서가 존재했습니다.(ordered) 하지만 딕셔너리는 순서가 없는 item의 모음으로 각 item이 key/value 쌍을 갖습니다. (즉, 순서가 없다! - unordered) Dictionary is mutable(변경 가능) and iterable..
[자료구조와 알고리즘 | 파이썬] Graphs - 그래프 자료구조(+약간의 python 개념)1. Dictionary and Copy in Python 그래프는 자료구조의 꽃이라 불릴 정도로 굉장히 중요하고 그 만큼 어려우며 대부분의 코딩테스트의 문제 중에서 킬러 문제를 담당하는 문제입니다. 그렇기 때문에 이를 제대로 이해해 보기 위해 파이썬의 개념을 먼저 익혀보도록 하겠습니다. 만약 파이썬 개념에 대해서 잘 아시는 분이시라면 중반부로 넘어가셔도 좋습니다! Python Dictionary (파이썬 딕셔너리) 우리가 많이 쓰는 리스트 자료구조에는 순서가 존재했습니다.(ordered) 하지만 딕셔너리는 순서가 없는 item의 모음으로 각 item이 key/value 쌍을 갖습니다. (즉, 순서가 없다! - unordered) Dictionary is mutable(변경 가능) and iterable..
2022.12.31 -
이번 시간에는 그래프 탐색 방법 중 너비 우선 탐색(BFS)에 대해서 배워볼 것입니다. 1. 그래프 탐색이란 하나의 정점으로붙 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는 지 그래프는 탐색하는 동안 동일한 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 그래서 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(visited)했다는 표시를 함으로써 중복 방문을 피하도록 하는 것이 그래프 탐색의 핵심입니다. Queue를 이용하여 구현 2. BFS (Breath-First Search, 너비 우선 탐색 ) DFS는 그래프의 개념이 반드시 선행되어야 하기 때문에 ..
[Algorithm | Java] 너비 우선 탐색(BFS)(그래프 탐색) 알고리즘이번 시간에는 그래프 탐색 방법 중 너비 우선 탐색(BFS)에 대해서 배워볼 것입니다. 1. 그래프 탐색이란 하나의 정점으로붙 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는 지 그래프는 탐색하는 동안 동일한 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 그래서 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(visited)했다는 표시를 함으로써 중복 방문을 피하도록 하는 것이 그래프 탐색의 핵심입니다. Queue를 이용하여 구현 2. BFS (Breath-First Search, 너비 우선 탐색 ) DFS는 그래프의 개념이 반드시 선행되어야 하기 때문에 ..
2022.12.28 -
이번 시간에는 그래프 탐색 방법 중 깊이 우선 탐색(DFS)에 대해서 배워볼 것입니다. 1. 그래프 탐색이란하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는 지그래프는 탐색하는 동안 동일한 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 그래서 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(visited)했다는 표시를 함으로써 중복 방문을 피하도록 하는 것이 그래프 탐색의 핵심입니다. 2. DFS (Depth-First Search, 깊이 우선 탐색 )DFS는 그래프의 개념이 반드시 선행되어야 하기 때문에 다음 포스트를 먼저 확인하길 바랍니..
[Algorithm | Java] 깊이 우선 탐색(DFS) (그래프 탐색) 알고리즘이번 시간에는 그래프 탐색 방법 중 깊이 우선 탐색(DFS)에 대해서 배워볼 것입니다. 1. 그래프 탐색이란하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는 지그래프는 탐색하는 동안 동일한 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 그래서 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(visited)했다는 표시를 함으로써 중복 방문을 피하도록 하는 것이 그래프 탐색의 핵심입니다. 2. DFS (Depth-First Search, 깊이 우선 탐색 )DFS는 그래프의 개념이 반드시 선행되어야 하기 때문에 다음 포스트를 먼저 확인하길 바랍니..
2022.12.28 -
이번 시간에는 그래프에 대해 알아보도록 하겠습니다. 1. Graph - 그래프란? 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다. 먼저 그래프와 트리의 차이점을 살펴보면 다음과 같습니다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류이고 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 무방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 모두 가능 순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 ..
[자료구조 | Java] Graph(그래프)이번 시간에는 그래프에 대해 알아보도록 하겠습니다. 1. Graph - 그래프란? 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다. 먼저 그래프와 트리의 차이점을 살펴보면 다음과 같습니다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류이고 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 무방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 모두 가능 순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 ..
2022.12.28