분류 전체보기 (247) 썸네일형 리스트형 [DS] Graph 개념과 탐색방법 1. Graph 그래프는 비선형 자료구조로 정점(vertex, 또는 노드 node)과 정점들을 있는 간선(edge)으로 이루어져 있다. 간선은 E(u,v)로 표현할 수 있는데, 이는 vertex u 와 vertex v를 연결하는 간선이라는 뜻이다. undirected graph 에서는 (u,v)와 (v,u)가 같은 의미를 가지지만 directed graph 에서는 (u,v)와 (v,u) 이 서로 방향이 다르기 때문에 다른 간선을 의미한다. 간선은 weight, value, cost 등의 가중치를 주어서 실제 문제에 적용하기도 한다. 1) 용어 Undirected Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하지 않는 그래프 Directed Graph: 정점과 간선의 연결관계에서 간선의 방향.. [DS] Heap 1. Heap 힙은 Tree 구조를 기반으로 한 자료구조의 일종으로 배열로 구현한 Complete Binary Tree (완전이진트리) 구조로 이루어져 있다. 힙은 root 노드에 위치하는 값의 성질에 따라 max heap과 min heap 두가지로 나뉜다. 1) max heap: 각 노드의 값이 해당 child 노드들의 값보다 큰 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 큰 값을 가진다. 2) min heap: 각 노드의 값이 해당 child 노드들의 값보다 작은 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 작은 값을 가진다. 2. 배열을 통한 구현 heap을 배열로 구현하게 되면 root 노드의 인덱스가 0이 되고, 뒤이어서 나머지 노드들의 값이 저장된다. 이때 heap은 완.. [JAVA] JVM (Java Virtual Machine) 1. JVM 이란? 자바 가상 머신 (Java Virtual Machine, JVM)은 시스템 메모리를 관리하면서 자바 기반 애플리케이션을 위해 이식 가능한 실행 환경을 제공한다. 한마디로 JVM은 자바 애플리케이션을 실행하는 프로그램이다. 이를 통해 자바는 OS 에 종속되지 않고, JVM이 존재한다면 실행 가능하다. Stack 기반의 가상 머신이다. 2. JVM의 용도와 정의 JVM에는 2가지 기본 기능이 있다. - 자바 프로그램을 어떤 환경 (기기, 운영체제 등등)에서도 실행될 수 있도록 하는것 - 프로그램 메모리를 관리하고 최적화 하는 것 (메모리 관리, Garbage collection) JVM은 기술적인 정의와 소프트웨어 개발자들의 일반적인 정의를 통해 두가지 정의를 나눌 수 있다. - 기술적 .. [DS] Tree & Binary Tree 1. Tree 트리는 비선형 자료구조로 부모와 자녀로 이루어진 계층적 관계를 가진 자료구조이다. 1) 용어 - Node: 노드. 트리를 구성하고 있는 각각의 요소를 의미한다. - Edge: 간선. 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미하다. - Root Node: 루트 노드. 트리 구조에서 최상위에 있는 노드 (뿌리)를 의미한다. - Terminal Node (leaf Node): 단말 노드. 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. - Internal Node: 내부 노드, 비단말 노드. 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다. - degree: 차수. 자식 노드의 개수. - height: 높이. 트리에서 루트 노드부터 가장 깊은 리프 노드까지의 길이. -.. [DS] Stack & Queue 1. Stack 스택은 선형 자료구조의 하나로 LIFO (Last In First Out) 또는 FILO (First In Last Out)라 불리는 구조로 이루어져 있다. 데이터 삽입시에 삽입되는 순서대로 스택 안에 차곡차곡 쌓이고, 출력시에는 마지막에 삽입된 데이터부터 역순으로 출력되는 식으로 데이터가 운영된다. 수식의 계산이나 서브 함수 실행 후의 복귀 등 재귀적인 상황에서 많이 사용한다. - Stack 자바 구현 더보기 import java.util.Arrays; import java.util.EmptyStackException; public class CustomStack { private static final int DEFAULT_CAPACITY = 10; private Object[] el.. [DS] Array & Linked List 1. Array 가장 기본적인 자료구조로 메모리 상에 같은 타입의 데이터가 연속적으로 저장되어 있다. 이러한 구조는 첫번째 원소의 위치를 기본 index로 offset을 더하여 이어지는 원소들의 위치를 계산하기에 쉽다. 이때문에 array는 논리적 저장순서와 물리적 저장순서가 일치한다. 따라서 index를 통해서 원소에 랜덤하게 접근이 가능하다. 따라서 검색 time complexity 는 O(1) 이다. 검색과 달리 삭제와 삽입 등의 과정에서는 해당 원소에 접근하여 작업을 완료한 후 빈 공간에 대해서 다른 원소들을 shifting 해줘야 하는 cost가 발생하고 이 경우의 시간 복잡도는 O(N)이 된다. 그렇기 때문에 array 값의 삽입, 삭제의 Time complexity는 O(N) 이다. 2. L.. [DS] 자료구조 개념 및 종류 1. 자료구조란? 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. 대부분의 언어는 일정 수준의 모듈 개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감춘 채 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. 2. 자료구조.. [Python] Python 병렬처리 - threading (3) [threading - Thread-based parallelism] ■ Lock Objects primitive lock 은 잠긴 상태일때 특정 thread 가 소유할 수 없는 동기화 primitive 이다. 현재 파이썬에서 _thread 확장 모듈에 의해 직접 구현되는 가장 low 한 동기화 primitive 이다. primitive lock은 locked 와 unlocke, 두가지 상태를 가지고 있는데, 초기 생성 시에는 unlocked 상태로 생성된다. 해당 class 는 acquire 와 release, 두개의 메소드를 가지고 있으며, 이를 통해서 Lock 의 상태를 다룰 수 있다. 각 메소드는 현재 lock 의 상태가 locked 인지 unlocked 인지에 따라서 다르게 작동한다. - acq.. 이전 1 ··· 23 24 25 26 27 28 29 ··· 31 다음
