전체 글16 그래프(Graph)의 구현 👉 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix) 간선으로 연결되어 있는 노드들은 인접하다(adjacent)라고 표현하며, 그래프를 구현하는 방식은 다음과 같다. 인접리스트(Adjacency List) 그래프를 표현하는 가장 일반적인 방법. 연결 리스트를 활용해 표현하는 방식. 모든 정점을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한다. 배열(해시테이블)과 배열의 각 인덱스 마다 존재하는 또 다른 리스트(배열, 동적 가변 크기 배열(ArrayList), 연결리스트(LinkedList) 등)를 이용해서 인접 리스트를 표현 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근할 수 있다. 예) 0: 1 1: 2 2: 0, 3 3: 2 4: 6 5: 4 무방향 그래프에서 (a, b) 간선은 두번 저.. 2023. 4. 10. 선형구조👉 큐(Queue)와 덱(Queue) 그리고 스택(Stack) 큐(Queue) 선입선출(FIFO, First In First Out). 즉, 먼저 입력/삽입 된 데이터부터 출력/제거 하는 방식이다. 한쪽은 입력, 한쪽은 출력이 가능한 단방향 구조이다. 큐는 데이터 삽입(append)와 데이터 삭제(popleft) 이 핵심적인 함수로 동작한다. append 함수: 리스트 내, 좌측에서 우측 순서대로(index 증가) 데이터를 추가해 준다. popleft 함수: 리스트 내, 가장 좌측에 있는 데이터 한개를 삭제해 준다. 큐 사용할 때, 오버플로우(overflow)와 언더플로우(underflow) 발생에 유의해야 한다. 오버플로우(overflow): 큐에 저장할 수 있는 데이터의 크기를 초과한 상태에서 데이터 삽입을 수행할 때 발생한다. 언더플로우(underflow): .. 2023. 4. 10. 그래프(Graph)의 개념과 특징 그리고 종류, 트리(Tree)와 비교 그래프(Graph)의 개념 노드(N, node)와 간선(E, edge)로 이루어진 자료구조의 일종으로 연결되어 있는 객체 간의 관계를 표현 할 수 있는 자료구조이다. 그래프의 특징 그래프는 네트워크 모델이다. 2개 이상의 경로가 가능하다. → 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다. self-loop 뿐만 아니라 loop/circuit 모두 가능하다. 루트 노드라는 개념이 없다. 부모-자식 관계라는 개념이 없다. 순회는 DFS나 BFS로 이루어진다. 그래프는 순환(Cyclic) 혹은 비순한(Acyclic)이다. 그래프는 크게 방향 그래프와 무방향 그래프가 있다. 간선의 유무는 그래프에 따라 다르다. 그래프의 종류 무방향 그래프와 방향 그래프 무방향 그래프(Undirected Graph.. 2023. 4. 10. 알고리즘 문제에서의 자료구조란? 프로그램은 데이터를 표현하고, 그렇게 표현 된 데이터를 처리하는 것을 말한다. 여기서 데이터 표현이란 데이터의 저장을 포함하는 개념이고, 이 데이터의 저장을 담당하는 것을 자료구조라고 한다. 또한 여기서 말한 데이터 처리는 알고리즘이라고 말하는데 즉, 문제의 해결 방법을 말한다. 👉 자료구조란 데이터의 표현 및 저장방법, 알고리즘은 데이터 처리 해결 방법이다. 2023. 4. 10. 이전 1 2 3 다음
