그래프의 정의 그래프는 트리를 포함하는 개념이고, 트리는 사이클을 포함하지 않는 그래프라고 볼 수 있다. 그래서 모든 트리는 그래프이지만, 모든 그래프는 트리가 아니다. 그래프는 정점의 모음과 간선의 모임이 결합한 것이다. 정점 자체는 아무것도 아니지만 이들이 간선을 통해 서로 연결되면 관계가 형성되고 이로 인해 그래프가 만들어진다. 인접 (adjacent) : 간선으로 연결된 두 정점을 가리켜 서로 인접 또는 이웃 관계에 있다고 말한다. (A, B), (A, D), (A, E), (B, C), (B, E), (C, D)가 서로 이웃 관계 경로(Path) : 정점 A에서 정점 C까지는 A, B, C와 A, D, C가 각각 하나의 경로 경로의 길이 : 정점과 정점 사이에 있는 간선의 수 경로 A, B, C..

힙과 우선순위 큐 결론부터 말하자면, 우선순위 큐는 ADT(Abstract Data Type) 이고, 힙은 우선순위 큐의 개념을 구현한 것이다. ADT 구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 기능이 있는지를 설명하고 나열한 것. 즉, 구현은 하지 않고 어떠한 기능과 어떠한 작동원리를 가지는지 추상적으로 설명한 것이다. 우선순위 큐는 단순 FIFO구조가 아니라, 각 큐에 들어오는 원소마다 우선순위가 정해져 있다. 만약, 우선순위가 높은 순서대로 큐에서 제거하기로 했다면 큐에 들어온 순서대로 원소가 제거되는 것이 아니라 우선순위가 높은 순서대로 큐에서 제거된다. 만약, 우선순위가 낮은 순서대로 큐에서 제거하기로 했다면 큐에 들어온 순서대로 원소가 제거되는 것이 아니라..

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 패스트푸드점에서 손님이 음식을 주문하는 프로그램을 작성 중이고, 음식마다 각각 가격이 있는 메뉴를 구현하고 있다고 상상해 보자. 메뉴 배열 안에 메뉴의 이름과 가격을 포함하는 배열이 또 있다고 가정하면, 메뉴 배열안에 있는 하위 배열을 찾는데 O(N)의 단계가 걸린다. 정렬된 배열이라면 이진탐색을 통해O(logN)이 걸린다. 하지만 해시 테이블을 사용하면 데이터를 O(1)만에 룩업할 수 있다. 해시 테이블 해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 대부분의 프로그래밍 언어는 해시 테이블(hash table)..

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 배열의 크기와 인덱스 배열의 크기 : 배열에 데이터 원소가 얼마나 들어있는지를 나타낸다. 위 그림에서 배열의 크기는 5이다. 배열의 인덱스 : 특정 데이터가 배열의 어디에 있는지 알려주는 숫자다. 자료구조 연산 대부분의 자료 구조는 네 가지 기본 방법을 사용하며 이를 연산이라 부른다. 연산은 아래와 같다. 읽기 검색 삽입 삭제 연산의 속도 측정 연산이 얼마나 '빠른가'를 측정 할 때는 순수하게 시간 관점에서 연산이 빠른가가 아니라, 얼마나 많은 단계가 필요한지를 논해야 한다. 왜 코드의 속도를 시간으로 측정하지 않을까? 누구도 어떤 연산이, 정확히 몇초가 걸린다고 단정할 수 없기 때문이다. 같은 ..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 큐 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과 다르게 선입선출(FIFO, First In First Out)이다. 아래의 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어 있다. 큐에 데이터를 넣는 작업을 인큐라 하고, 데이터를 꺼내는 작업을 디큐라고 한다. 인큐와 디큐 인큐 위 그림에서 리어(rear)인 53 뒤에 24를 인큐 한다. 이 처리의 시간복잡도는 O(1)이고 적은 비용으로 구현할 수 있다. 디큐 위 그림에서 프론트(front)인19와 22을 디큐 한다. 디큐한 후에는 모든 요소를 앞으로 옮겨야 한다. 이 처리의 시간복잡도는 O(N)이며 ..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 스택 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다. 스택에 데이터를 넣는 작업을 푸시라 하고, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다. 이렇게 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. int 배열을 이용한 IntStack 클래스 public class IntStack { private int max; private int ptr; private int []stk; public IntStack(int capaci..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 클래스 배열이란 클래스로 부터 만들어진 객체로 이루어진 배열을 뜻한다. 클래스 자체가 자료형이되어서 데이터를 더 쉽게 다룰 수 있다. 아래는 이름, 키, 시력을 저장하는 클래스의 객체로 이루어진 배열을 활용하여 평균 키와 시력 분포를 출력하는 예제 코드이다. public class Main{ static class PhyscData { //이름, 키, 시력을 저장하는 클래스 String name; int height; double vision; PhyscData(String name, int height, double vision) { //생성자 this.name = name; this.height = height; t..

노드 클래스 class Node: def __init__(self, data): self.data = data self.next = None Single Linked List 클래스 class SLL: def __init__(self, data): #생성자 self.head = Node(data) def append(self, data): #노드 추가 current_node = self.head while current_node.next is not None: current_node = current_node.next current_node.next = Node(data) def print(self): #노드 출력 current_node = self.head while current_node is not..