티스토리

yoongrammer

검색하기

블로그 홈

yoongrammer

yoongrammer.tistory.com/m

새로운 것을 접하고 공유하는 개발 블로그

구독자: 26

방명록 방문하기

주요 글 목록

다음 순열(next permutation) 알고리즘 목차 다음 순열(next permutation) 알고리즘 next permutation 은 현재 순열보다 큰 다음 순열을 찾는 알고리즘입니다. [1, 2, 3]이 최초 숫자 배열로 주어진 경우 사전순으로 배열된 모든 가능한 순열은 아래와 같습니다. 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 [1, 2, 3] = 다음으로 큰 순열은 [1, 3, 2]입니다. [1, 3, 2] = 다음으로 큰 순열은 [2, 1, 3]입니다. ... [3, 2, 1] = 가장 큰 순열이기 때문에 다음으로 큰 순열은 없습니다. 동작 방식 다음 순열을 얻으려면 피벗 포인트(Pivot Point)를 사용합니다. 피벗 포인트는 교환, 분할 등의 작업을 수행하기 위한 기준이 되는 위치나 값입니다. next perm.. 공감수 0 댓글수 0 2023. 5. 15.
머신 러닝으로 시계열(Time Series) 데이터 예측하기 목차 머신 러닝으로 시계열(Time Series) 데이터 예측하기 머신 러닝은 시계열 데이터를 예측하는데 자주 사용됩니다. 시계열(Time Series)란? Time series(시계열)란 일정 시간 간격으로 측정된 데이터의 시퀀스를 말합니다. 시간은 보통 초, 분, 시간, 일, 주, 월, 분기, 연도 등의 단위로 표현되며, 주식 가격, 기온, 수익률, 판매량, 웹 사이트 트래픽 등과 같은 많은 현실 세계의 데이터가 시계열로 표현됩니다. 다음은 책 판매량에 대한 시계열 데이터입니다. book_sales.head() plt.plot(book_sales) plt.ylabel('Book') plt.xlabel('Date') plt.title('Time Plot of Book Sales') Linear Regr.. 공감수 0 댓글수 0 2023. 4. 29.
판다스(Pandas) 데이터 선택하기 (Selection) 목차 판다스(Pandas) 데이터 선택하기 (Selection) Pandas는 DataFrame 또는 Series 개체의 특정 부분을 검색하고 조작할 수 있는 다양한 데이터 선택 방법을 제공합니다. select를 설명하기 위해 사용하는 DataFrame은 다음과 같습니다. Selecting Columns DataFrame에서 열의 하위 집합을 선택하려면 다음 구문을 사용해야 합니다. df[column_list] column_list: 선택하려는 열 이름의 목록 다음은 A행을 가져오는 예입니다. df['A'] # output 2023-02-18 0.509482 2023-02-19 0.966399 2023-02-20 0.857979 2023-02-21 0.701611 2023-02-22 0.102038 20.. 공감수 0 댓글수 0 2023. 2. 19.
판다스(Pandas) 데이터 구조 알아보기 목차 판다스(Pandas) 데이터 구조 알아보기 판다스(Pandas)는 python으로 만들어진 데이터 처리 및 분석을 위한 라이브러리입니다. 판다스 데이터 구조를 알아보기 위해선 아래와 같이 모듈을 import 합니다. import pandas as pd import numpy as np 데이터 구조 Pandas에서 데이터를 저장하기 위한 객체로 DataFrame과 Series가 있습니다. DataFrame Pandas에서는 데이터 테이블을 DataFrame이라고 합니다. DataFrame은 column label과 row label(=index)를 가지고 있는 2차원 배열 구조입니다. 열에는 다양한 유형의 데이터(문자, 정수, 부동 소수점, 범주형 데이터 등)를 저장할 수 있습니다. DataFrame.. 공감수 0 댓글수 1 2023. 1. 26.
Lower bound & Upper bound 개념 및 구현 목차 Lower bound & Upper bound 개념 및 구현 Lower bound와 Upper bound는 경곗값을 찾는 알고리즘입니다. Lower bound와 Upper bound는 이진 탐색을 기반으로 하기 때문에 데이터가 정렬되어 있어야 합니다. 이진 탐색을 기반으로 하기 때문에 두 알고리즘의 시간 복잡도는 O(log n) 입니다. (n: 배열 길이) Lower bound Lower bound는 특정 값의 시작 위치를 찾는 알고리즘입니다. 동작 방식 Lower bound의 동작 방식은 다음과 같습니다. 초기에 left는 배열의 시작 위치로 right는 배열의 길이로 셋팅합니다. 배열의 중간 값(mid)을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값보다 작다면 left 값을.. 공감수 6 댓글수 0 2022. 12. 25.
펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 개념 및 구현 목차 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 펜윅 트리(Fenwick Tree)는 세그먼트 트리의 변형으로 수열의 구간 합을 빠르게 구할 수 있도록 고안된 자료 구조입니다. 펜윅 트리는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. 펜윅 트리는 세그먼트 트리처럼 O(logN) 시간으로 구간 합을 구할 수 있으며 세그먼트 트리에 비해 적은 공간이 필요하고 구현하기 쉽다는 장점이 있습니다. 펜윅 트리 구성 배열 A를 가지고 세그먼트 트리를 만들면 다음과 같습니다. 각 노드에는 구간합 정보가 들어 있습니다. 위 세그먼트 트리에서 각 층에에서 짝수 인덱스를 무시하면 아래와 트리를 얻을 수 있습니다. 이러한 구조를 펜윅 트리라고 합니다. 주어.. 공감수 1 댓글수 0 2022. 11. 20.
세그먼트 트리(Segment Tree) 개념 및 구현 목차 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. 다음 예를 보겠습니다. A = {1, 2, 3, 4, 5 … ,N} 라는 배열에 아래 연산을 M번 수행한다고 생각해봅시다. 배열의 범위 합을 구하는 Query 연산 A[0] + A[1] + A[2] + … + A[N-1] i번째 배열 값을 v로 변경하는 Update 연산 A[i] = v 단순한 방법으로는 각각 배열에 접근하여 연산을 한다면 시간 복잡도는 1번 연산 O(N), 2번 연산 O(1)이 됩니다. 이 두 연산을 M번 수행한다면 총 시간 복잡도는 O(MN)+O(M) = O(MN)이 됩니다. 세그먼트 트리를 사용하면 범위 최소/최대 및 합계 Query 및.. 공감수 5 댓글수 0 2022. 10. 9.
서로소 집합(Disjoint Set) & 유니온 파인드(Union find) 목차 서로소 집합(Disjoint Set) & 유니온 파인드(Union find) 서로소 집합(Disjoint Set) Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. Disjoint set 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는 데에 유용하게 사용할 수 있습니다. Disjoint set 자료구조는 MakeSet, Union, Find라는 연산을 제공합니다. MakeSet MakeSet 연산은 주어진 요소만 포함하는 집합을 생성합니다. 이 연산에서 parent 배열을 생성합니다. parent 배열은 노드의 부모 노드를 저장하고 있습니다. 부모 노드가 없다면 자기 자신을 가리.. 공감수 5 댓글수 6 2022. 9. 19.
캐시(Cache) 알아보기 목차 캐시(Cache) 란? 캐시(Cache)는 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 저장소입니다. 속도 향상을 위해 캐시를 사용하며, 다음과 같은 상황에서 캐시를 주로 사용합니다. 원본 데이터보다 빠르게 접근 가능할 때 같은 데이터에 반복적으로 접근할 때 변하지 않은 데이터를 주로 사용할 때 레디스(Redis)는 단순한 구조와 in-memory저장소로 인한 빠른 성능 때문에 캐시에 주로 쓰입니다. 캐싱 전략(Caching Strategies) 캐시로 사용할 때 어떻게 배치하는지가 시스템 성능에 큰 영향을 끼치는데 이를 캐싱 전략(Caching Strtegies)이라고 합니다. Look-Aside Look-Aside는 데이터를 찾을 때 우선 캐시에서 데이터를 찾고 데이터가 있다면 캐시에서.. 공감수 3 댓글수 0 2022. 8. 11.
의존성 역전 원칙 (DIP: Dependency Inversion Principle) 목차 의존성 역전 원칙 (DIP: Dependency Inversion Principle) 1. 상위 모듈은 하위 모듈에 의존해서는 안 되고 둘 다 추상화에 의존해야 한다. 2. 추상화는 세부 사항에 의존해서는 안 되고 세부사항(구체적인 구현)은 추상화에 의존해야 한다. 로버트 C. 마틴 의존성 역전 원칙(DIP)은 변화하기 쉬운 것에 의존하지 말라는 원칙입니다. DIP를 지킴으로써 하위 모듈(or 클래스)에 대한 상위 모듈(or 클래스)의 종속성을 줄일 수 있습니다. 상위 모듈(or 클래스): 도구로 작업을 실행하는 클래스 하위 모듈(or 클래스): 작업을 실행하는데 필요한 도구 DIP 적용 전 다음 예를 보겠습니다. Calculator 클래스가 Add클래스를 사용하여 덧셈을 하는 예입니다. 여기서 C.. 공감수 1 댓글수 0 2022. 6. 19.
인터페이스 분리 원칙 (ISP: Interface Segregation Principle) 목차 인터페이스 분리 원칙 (ISP: Interface Segregation Principle) 클라이언트는 사용하지 않는 인터페이스에 강제로 의존해서는 안된다. 로버트 C. 마틴 인터페이스 분리 원칙(ISP)은 클라이언트가 자신이 이용하지 않는 메서드에 의존하지 않아야 한다는 원칙입니다. ISP를 지킴으로써 큰 덩어리의 인터페이스를 구체적이고 작은 단위로 분리시키며 클라이언트가 꼭 필요한 메서드만 이용할 수 있게 합니다. ISP 적용 전 ISP를 위반하는 예를 보겠습니다. Vechicle은 go(), fly() 메서드를 가진 추상 클래스입니다. from abc import ABC, abstractmethod class Vehicle(ABC): @abstractmethod def go(self): pas.. 공감수 3 댓글수 0 2022. 5. 13.
리스코프 치환 원칙 (LSP: Liskov Substitution Principle) 목차 리스코프 치환 원칙 (LSP: Liskov Substitution Principle) S가 T의 하위 유형이면 프로그램에서 자료형 T의 객체는 해당 프로그램의 원하는 속성을 변경하지 않고 자료형 S의 객체로 교체(치환)할 수 있어야 한다. 바바라 리스코프(Babara Liskov) 로버트 C마틴은 이것을 다음과 같이 요약했습니다. 자식 클래스는 부모 클래스를 대체할 수 있어야 한다. 이 원칙의 핵심은 부모 클래스를 사용하는 위치에 자식 클래스를 대신 사용했을 때 코드가 원래 의도대로 작동해야 한다는 것을 의미합니다. LSP 위반 사례 일반적으로 많이 드는 예시가 바로 직사각형을 상속한 정사각형 클래스의 예시입니다. class Rectangle: def __init__(self, width, heig.. 공감수 1 댓글수 0 2022. 4. 30.
개방-폐쇄 원칙 (OCP: Open-Closed Principle) 목차 개방-폐쇄 원칙 (OCP: Open-Closed Principle) 소프트웨어 엔티티(클래스, 모듈, 함수 등)는 확장에 대해서는 열려 있어야 하지만 변경에 대해서는 닫혀 있어야 한다. Bertrand Mayer 계방 폐쇄 원칙은 기존 코드를 변경하지 않으면서(Close) 기능을 추가(Open)할 수 있도록 설계가 되어야 한다는 원칙입니다. 이 원칙을 지키기 위해서 주로 객체지향의 추상화와 다형성을 활용합니다. OCP 적용 전 class File: def __init__(self, name): self.name = name def __repr__(self): return f'File(name={self.name})' class FileStorage: def save_to_ORACLE(self, fi.. 공감수 1 댓글수 0 2022. 3. 3.
단일 책임 원칙 (SRP: Single Responsibility Principle) 목차 단일 책임 원칙 (SRP: Single Responsibility Principle) 클래스를 변경하는 이유는 단 한 가지여야 한다. 로버트 C. 마틴 단일 책임 원칙(SRP: Single Responsibility Principle)은 다섯 가지 SOLID 애자일 원칙 중 하나입니다. 클래스를 변경하는 이유가 한 가지이기 위해서는 하나의 액터에 대한 책임만 가지고 있어야 합니다. 여기서 책임은 하나의 특정 액터를 위한 기능 집합이고, 액터란 기능(=클래스 ,모듈)을 사용하는 주체입니다. SRP 적용 전 class Car(): def start(self): pass def stop(self): pass def drive(self): pass def wash(self): pass def changeT.. 공감수 4 댓글수 2 2022. 2. 22.
문자열 검색 알고리즘 : Boyer Moore - Good Suffix Heuristics 알아보기 목차 문자열 검색 알고리즘 : Boyer Moore - Good Suffix Heuristics 알아보기 Bad character heuristics은 한 칸만 이동하는 경우가 있습니다. 이 경우 최대 이동 거리를 도출하기 위한 방법으로 Good Suffix Heuristics를 사용합니다. Good Suffix는 패턴의 문자 일부와 일치하는 텍스트의 부분 문자열을 말합니다. Good Suffix Heuristics는 세 가지 상황이 있으며 각 상황에 맞는 오프셋을 제공합니다. Case1. Good Suffix가 패턴의 다른 곳에도 있는 경우 다른 곳에 있는 일치하는 패턴 문자를 Good Suffix와 일치하도록 패턴을 이동시킵니다. 아래 그림에서 Bad character heuristics를 사용한다면.. 공감수 0 댓글수 0 2022. 1. 12.
문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 목차 문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 알아보기 boyer-moore 알고리즘은 문자열 검색 알고리즘으로써 패턴의 전처리로 얻은 정보를 가지고 패턴을 가능한 많이 이동시켜 텍스트와 비교 횟수를 줄입니다. boyer-moore 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 기존 패턴 검색 알고리즘과 달리 boyer moore 알고리즘은 역방향 접근 방식을 사용합니다. 패턴의 마지막 문자부터 시작하여 오른쪽에서 왼쪽으로 비교를 시작합니다. 이동 위치를 정하기 위해 boyer-moore 알고리즘은 두 가지 휴리스틱을 사용합니다. Bad Character Heuristic Good Su.. 공감수 1 댓글수 0 2021. 12. 14.
문자열 검색 알고리즘 : Rabin-Karp 목차 문자열 검색 알고리즘 : Rabin-Karp 알아보기 Rabin-Karp 알고리즘은 해시 함수를 사용하여 문자열을 검색하는 알고리즘입니다. 해시 함수를 사용하여 문자열을 숫자 값인 해시 값으로 변경합니다. ex) hash("hello") = 5. 해시 값이 다르다면 두 문자열은 다르다는 것이 보장됩니다. 하지만 문자열이 달라도 해시 값이 같을 수 있습니다. 우리는 이것을 Spurious Hit라고 부릅니다. Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요합니다. 이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시 값과 일치하는지 비교하는 작업을 합니다. 따라서 Rabin-Karp 알고리즘은 다음 문자열에 대한.. 공감수 0 댓글수 0 2021. 10. 30.
문자열 검색 알고리즘 : KMP(Knuth Morris Pratt) 목차 KMP(Knuth Morris Pratt) 알고리즘 알아보기 navie 알고리즘은 최악의 경우 O(m(n-m+1))의 시간이 걸립니다. (n 패턴의 길이, m 텍스트 길이) 문자 하나하나 씩 비교하기 때문에 불필요한 문자 비교가 있을 수 있습니다. 다음은 navie 알고리즘으로 텍스트 T[]="banananobano"에서 패턴 P[]="nano"를 찾는 과정입니다. 이 동작에서 일부는 낭비입니다. i=2에서 T[3] = 'a', T[4]='n' 이라는 것을 확인했으니 i=3, 4에서 패턴 n과 비교하는 것은 불필요합니다. KMP 알고리즘은 lps(Longest Proper Prefix which is Suffix) 배열을 사용하여 문자열 검색 시 불필요한 문자 간 비교를 없애 성능을 개선시킨 알고리.. 공감수 0 댓글수 0 2021. 10. 25.
문자열 검색 알고리즘 : Naive Pattern Searching 목차 Naive Pattern Searching 알아보기 naive pattern searching은 패턴 검색 알고리즘 중에서 가장 간단한 알고리즘입니다. 단순히 문자를 처음부터 끝까지 하나하나 비교해가며 패턴을 찾기 때문에 작은 문자열에서 패턴을 찾을 때 유용합니다. 구현 길이가 n인 텍스트 T안에 모든 위치에서 길이가 m인 패턴 P와 매치 여부를 검토합니다. 패턴의 길이는 텍스트의 길이보다 작거나 같아야 합니다. (m ≤ n) T[0 ... n-1] P[0 ... m-1] 패턴 P는 텍스트 T의 처음부터 n-m+1까지 이동하며 매치가 되는지 검토합니다. 패턴이 발견되면 패턴의 위치를 출력하고 다음 일치 위치를 찾습니다. 구현하면 다음과 같습니다. void naivePatternSearch (char.. 공감수 0 댓글수 0 2021. 10. 13.
최단 경로 문제: 플로이드 와셜 알고리즘 (Floyd-Warshall Algorithm) 목차 플로이드 와셜 알고리즘 (Floyd-Warshall Algorithm) 알아보기 플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로(Shortest path) 문제 중에 모든 정점 쌍(All-pairs)에 대해 최단 거리를 구하는 알고리즘입니다. 플로이드 와셜 알고리즘은 Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, 또는 WFI algorithm 이라고도 합니다. 특징 Dynamic Programming을 사용합니다. 유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다. 그래프에 음수 사이클 여부를 확인할 수 있습니다. 구현 플로이드 와셜 알고리즘은 각각.. 공감수 0 댓글수 0 2021. 10. 12.
최단경로 문제: 벨만-포드 알고리즘(Bellman-Ford Algorithm) 목차 벨만-포드 알고리즘(Bellman-Ford Algorithm) 알아보기 벨만-포드 알고리즘 (Bellman-Ford Algorithm)은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다. https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로 yoongrammer.tistory.com 특징 brute force str.. 공감수 1 댓글수 0 2021. 9. 24.
최단 경로 문제: 다익스트라 알고리즘 (Dijkstra's Algorithm) 목차 다익스트라 알고리즘 (Dijkstra's Algorithm) 알아보기 다익스트라(Dijkstra) 알고리즘은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다. https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로 yoongrammer.tistory.com 특징 음수 가중치를 가진 간선이 없어야 합니다. 탐욕 알고리즘.. 공감수 3 댓글수 0 2021. 9. 16.
최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로를 말합니다. 경로 p = 의 가중치(w) 합이 다음과 같다면 $$ w(p) = \sum_{i=1}^k w(v_{i-1},v_{i}) $$ 정점 u에서 v까지의 최단경로 값은 다음과 같이 표시합니다. $$ \delta(u,v) = \begin{cases} min\{w(p) : u \overset{p}\rightsquigarrow v \}, & \mbox{if u에서 v로 가는 경로가 있다면} \\ \infty, & \mbox{if u에서 v로 가는 경로가 없다면} \end{case.. 공감수 2 댓글수 0 2021. 8. 21.
위상 정렬(Topological sort) 개념 및 구현 목차 위상 정렬(Topological sort) 개념 및 구현 비순환 방향 그래프 (DAG: Directed Acyclic Graph) Directed Acyclic Graph (DAG)는 사이클이 없는 방향 그래프입니다. DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용됩니다. 위상 정렬(Topological sort) 위상 정렬(Topological sort)은 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것입니다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 됩니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다. 그래프에 사이클이 있으면서 두 정점 u,v가 사이클 속에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v.. 공감수 9 댓글수 3 2021. 8. 10.
[자료구조] 그래프 순회 (Graph traversal) 개념 및 구현 목차 그래프 순회 (Graph traversal) 알아보기 그래프 순회(traversal)는 모든 정점을 방문하는 작업입니다. 그래프는 탐색하는 동안 동일 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(Visited)했다는 표시를 하여 중복 방문을 피하도록 합니다. 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색 (DFS: Depth First Search) 너비 우선 탐색 (BFS: Breath First Search) 깊이 우선 탐색 (DFS: Depth First Search) 깊이 우선 탐색 (DFS: Depth First Search)은 그래프에서 최단 경로를 찾는 간선 기반 알고리즘입니다. DFS는 형제 정점을 .. 공감수 1 댓글수 0 2021. 7. 29.
[자료구조] 그래프 표현 및 구현 목차 그래프 표현 및 구현 그래프는 일반적으로 두 가지 방식으로 표현합니다. 인접 행렬 (adjacency matrix) 인접 리스트 (adjacency list) 인접 행렬(adjacency matrix) 인접 행렬은 그래프를 2차원 배열에 저장하는 방법입니다. 부속된 간선을 찾는 것은 빠르지만 |V| x |V| 만큼의 공간이 필요하여 저장 측면에서 비효율적입니다. (|V| : 정점 수) 노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용합니다. 각 행과 열은 정점을 나타냅니다. 1. 방향성 그래프 (Directed Graph) 방향성 그래프를 인접행렬로 표현하면 다음과 같습니다. 각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장.. 공감수 1 댓글수 1 2021. 7. 15.
[자료구조] 그래프 (Graph) 목차 그래프 (Graph) 알아보기 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다. 정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말함. 간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍 (u, v)로 표현함. 그래프(G)는 정점들의 집합 V와 간선들의 집합 E를 사용하여 (V, E)로 나타냅니다. G = (V , E) V = {1, 2, 3, 4, 5} E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)} 그래프 용어 Directed edge & Undirected edge 방향성(유향) 간선 (Directed edge) 방향을 가진 정점의 쌍 (u, .. 공감수 1 댓글수 0 2021. 7. 11.
[자료구조] 해시 테이블 (Hash Table) 목차 해시 테이블 (Hash Table) 알아보기 해시 테이블(hash table)에 대해 알아보기 전에 Direct address table에 대해 알아보도록 하겠습니다. Direct Address Table Direct address table은 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다. Direct address table은 키 k가 테이블 slot T[k]에 저장되기 때문에 테이블의 크기는 전체 키(U) 개수가 됩니다. 위 특징 때문에 direct address table은 중복 키가 없고, 테이블의 크기가 작은 경우에 사용할 수 있습니다. 구현 방법 전체 키 집합(U = {0,1 ... ,9})의 크기만 한 테이블(T)을 배열로 만듭니다. 실제 사용하는 키 집합(K = .. 공감수 4 댓글수 0 2021. 6. 28.
[자료구조] 우선순위 큐 (Priority Queue) 개념 및 구현 목차 우선순위 큐 (Priority Queue) 개념 및 구현 일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다. 하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다. 우선순위 큐는 다음과 같은 속성을 가지고 있습니다. 모든 항목에는 우선순위가 있습니다. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다. 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됩니다. 4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같습니다. (여기서 높은 값이 높은 우선순위.. 공감수 4 댓글수 1 2021. 6. 16.
[자료구조] 힙 (Heap) or 이진 힙(binary heap) 목차 힙 (Heap) or 이진 힙(binary heap) 알아보기 힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조입니다. 힙은 다음과 같은 속성을 가지고 있습니다. 완전 이진트리(Complete Binary Tree) 이다. 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다. 키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음. 힙의 종류 힙에는 두가지 종류(최대 힙, 최소 힙)가 있습니다. 1. 최대 힙 (Max Heap) 부모 키값이 자식노드 키값보다 큰 힙 Key(parent) ≥ Key(child) .. 공감수 5 댓글수 0 2021. 6. 13.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.