전체 글
[Data Structure] 이진 탐색 트리(Binary Search Tree)
[Data Structure] 이진 탐색 트리(Binary Search Tree)
2022.08.17이진 탐색 트리(Binary Search Tree)? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. 각 노드에 중복되지 않는 키가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다. 이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다. 이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다. 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만..
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)
2022.08.17우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐의 요소는 모두 우선순위를 가지고 있으며, 우선순위가 같은 경우에는 큐의 순서에 따라 처리한다. 우선순위 큐는 여러 방식으로 구현할 수 있지만 힙(heap)이 가장 효율을 보이기 때문에 일반적으로 힙을 이용하여 구현한다. 방식 시간 복잡도 배열 O(N) 연결 리스트 O(N) 힙 O(logN) 힙(heap) 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드는 자식노드 사이에 대소관계를 가지고 있다. 중복된 키를 허용한다. 힙의 종류 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙 최소 힙(min heap): ..
[Java] 2. List
[Java] 2. List
2022.08.12List? List는 컬렉션 프레임워크에서 제공하는 컬렉션 클래스 중 하나이다. 컬레션 프레임워크의 핵심 인터페이스에는 대표적으로 List, Set, Map이 있는데 여기서 List는 순서가 있고 데이터의 중복을 허용하는 특징이 있다. List 인터페이스의 구현 클래스에는 ArrayList, LinkedList, Stack, Vector 등이 있다. ArrayList ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스이다. ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리과 기능적인 측면에서 동일하며 Vector는 기존에 작성된 소스와의 호환을 위해 남겨두고 있을 뿐이기 때문에 가능하면 ArrayList를 사용하는 것이 좋다. ArrayList를 생성할..
[Java] 1. Collections Framework
[Java] 1. Collections Framework
2022.08.11Collections Framework? JDK1.2부터 Collections Framework가 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 표준화된 방식으로 다룰 수 있도록 체계화되었다. Collections Framework에서는 컬렉션데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다. 그리고 인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의하였다. 각 인터페이스 특징 List 순서가 있는 데이터의 집합, 데이터의 중복을 허용함 ArrayList, LinkedList, Stack, Vector 등 Set 순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허..
[Unix Programming] ipcs & ipcrm
[Unix Programming] ipcs & ipcrm
2021.12.13ipc 설비의 상태를 출력하는 ipcs와 ipc의 설비를 제거하는 ipcrm 명령어에 대해 알아보자. 먼저 ipcs는 위와 말한 것과 같이 IPC 설비의 현재 상태정보를 출력하는 명령어이다. 위와 같이 상태정보를 확인할 수 있다. 다음으로 ipcrm은 시스템으로부터 IPC 설비를 제거하는 명령어로 작성 형태는 다음과 같다. ipcrm 옵션에 따라 제거할 수 있는 IPC를 정할 수 있다. Message Queue: -q Shared Memory: -m Semaphores: -s
[Unix Programming] Shared Memory
[Unix Programming] Shared Memory
2021.12.13Shared Memory는 여러 process가 동시에 접근할 수 있는 메모리로, 두 개 이상의 process가 물리적 메모리의 일부를 공유한다. 여기서 주의할 점은 아무 process가 접근할 수 있는 것이 아니라, 잘 제어된 함수를 통해 요청한 process만 접근이 가능하다. Shared Memory는 앞에서 봤던 IPC 기법들 중에서 가장 빠르고 효율적이다. Shared Memory 기법의 사용 방법에 대해 간략히 살펴보면, 먼저 shmget 함수를 통해 접근 가능한 메모리 공간 할당을 요청한다. 그다음 shmat 함수를 통해 논리 메모리에 shmget을 통해 얻은 물리 메모리를 mapping 시켜준다. 마지막으로 사용하지 않으면 shmdt 함수를 호출하여 논리 메모리를 통해 물리 메모리에 접근하..
[Unix Programming] Semaphore
[Unix Programming] Semaphore
2021.12.04synchronization 기법 중 하나인 semaphore에 대해 알아본다. Semaphore는 공유된 자원에 대한 접근을 제어 하는 방식으로 1개의 공유되는 자원에 제한된 개수의 process나 thread가 접근할 수 있도록 한다. 다시 말해서, process간의 message 전송 또는 shared memory를 통해 특정 데이터를 공유하게 되는 경우 여러 개의 process가 동시에 접근하면서 문제가 발생할 수 있는데 이 접근을 제어하는 것이 semaphore이다. 이는 mutex와 유사한 기능을 수행하지만, 다음과 같은 차이가 있다. 하나의 process/thread의 접근을 제어하는 mutex와 달리, semaphore는 공유자원에 접근할 수 있는 process/thread의 수를 나타내는..
[Unix Programming] Message Passing
[Unix Programming] Message Passing
2021.12.04Message Passing은 IPC 기법 중 하나로 memory protection을 위해 커널의 도움을 받아 message를 전달한다. 여기서 message는 문자나 byte의 열이라고 생각하면 된다. Message Passing의 방식은 한 process가 msgsnd를 하게되면 사용자의 주소 공간으로부터 message queue에 message가 저장되고, 다른 process가 msgrcv를 하게되면 message queue에 있는 message를 사용자의 주소 공간으로 가져오게된다. 앞에서 본 것과 같이 Message Passing은 커널에 message queue를 만들어서 통신을 한다. message queue는 msgget 함수를 통해 만들어지며 message의 임시 버퍼로 쓰인다. 그럼 ..
[Unix Programming] IPC 기본 개념
[Unix Programming] IPC 기본 개념
2021.12.03IPC 기법에는 여러가지의 종류가 있는데 우선 다음의 기법에 대해 알아보도록 하자. - message passing - shared memory - pipe 우선 위 기법에 대해 알아보기 전, facility key와 get 연산에 대해 먼저 알아야 한다. IPC에는 facility key라는 것이 있는데 이것은 IPC 객체를 유일하게 식별하기 위해 사용되는 수이다. 소켓 통신을 할 때 IP와 Port 번호로 소켓을 유일하게 식별하는 것처럼, IPC 통신에서는 facility key를 사용하여 객체를 식별하는 것이다. facility key 값을 integer 형식의 숫자로 부여해도 되지만 숫자는 중복될 가능성이 높기 때문에 이 위험을 방지하기 위해 ftok이라는 함수를 쓴다. ftok은 파일 이름을 키..
[Unix Programming] Record Locking
[Unix Programming] Record Locking
2021.12.02Record Locking은 두 명 이상의 파일 사용자가 동시에 정보를 업데이트하려고 할 때 발생할 수 있는 오류, 즉 경쟁상태를 방지하기 위해 파일 또는 파일의 일부를 잠그는 것이다. Record Locking read lock - 여러 프로세스들이 같은 구역 동시에 설정 가능(write lock 적용 불가) write lock - 다른 프로세스들의 읽기나 쓰기 록을 불허 record lock을 걸기 위해서 fcntl이란 함수를 사용한다. #include int fcntl(int filedes, int cmd, struct flock *ldata); 여기서 filedes는 file descriptor를 의미하고, cmd는 F_GETLK, F_SETLK, F_SETLKW 을 넣어 설정할 수 있다. str..