그리디 알고리즘(Greedy Algorithm) 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후에 영향을 주지 않음 최적 부분 구조(Optimal Substructure) 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다 특징 전체 상황에서의 최적의 결과를 보장하지 못한다. 속도가 매우 빠르다 사용 예시 : 거스름돈, 활동 선택(Action Selection) 문제 등 동적 계획법(Dynamic Programming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 조건 겹치는 부분 문제(Overlapping Subproblems)..
Binary Search(이진탐색) 정렬된 배열, 이진 트리에서 특정한 값을 찾아내는 알고리즘이다. 정렬이 전제되어 있어야 한다. 한번 비교를 거칠 때 탐색 범위가 1/2로 줄어든다. 범위의 중앙 값과 비교한다. 찾는 값이 중앙 값보다 작다면 왼쪽(그림 : 내림차순 정렬이므로 오른쪽) 1/2의 범위에서 탐색한다. 찾는 값이 중앙 값보다 크다면 오른쪽(그림 : 내림차순 정렬이므로 왼쪽) 1/2의 범위에서 탐색한다. 1번/2번 해당하는 작업을 반복한다. 찾는 값이 중앙 값이면 탐색을 종료한다. 기본 형태의 Java 코드 int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; // high가 low보..
Heap(힙) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 💡 완전 이진 트리 : 이진 트리의 일종으로, 자식은 왼쪽부터 연결한다. (왼쪽 자식이 없으면서 오른쪽 자식이 존재할 수 없다) 일종의 반정렬 상태를 유지한다. 부모와 자식간에 정렬된 상태지만, 형제 노드간의 정렬은 이루어지지 않은 상태다. 중복된 값을 허용한다. (이진 탐색트리는 중복허용 X) 힙 종류 최대 힙(Max Heap) 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리 최소 힙(Min Heap) 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리 힙 구현 일반적으로 배열을 사용한다.(연결 리스트로 구현할 수도 있긴 하다.) 구현의 편의성을 위해 0번 인덱스는 사용하지 않는다. 일정한 규칙을 유지한다...
트리(Tree) 계층적인 자료를 표현하는 자료구조다. 나무를 거꾸로 한 모습이다. 사이클이 존재하지 않고, 모든 노드가 연결되어 있다. 방향 그래프이다 트리 관련 용어 이진 트리(Binary Tree) 자식의 노드의 수가 최대 2개인 트리를 의미한다. 트리 순회(Tree Traversal) 전위 순회(Pre-order Traversal) : 노드, 왼쪽 자식, 오른쪽 자식 순서로 방문하는 순회 방법 A-B-D-E-C-F-G 의 순서 중위 순회(In-order Traversal) : 왼쪽 자식, 노드, 오른쪽 자식 순서로 방문하는 순회 방법 D-B-E-A-F-C-G 의 순서 후위 순회(Post-order Traversal) : 왼쪽 자식, 오른쪽 자식, 노드 순서로 방문하는 순회 방법 D-E-B-F-G-C..
Stack(스택) 삽입(push)과 삭제(pop)이 한쪽 끝(top)에서만 일어나는 자료구조다. top : 가장 상단에 위치한 원소를 가리키는 용어 push() : top 위치에 데이터를 삽입하는 기능 시간복잡도 : O(1) 용량이 꽉 찬 스택에 push()를 시도하면 Stack Overflow 에러가 발생한다. pop() : top 위치의 데이터를 삭제/반환 하는 기능 시간복잡도 : O(1) 데이터가 없는 스택에 pop()을 시도하면 Stack Underflow 에러가 발생한다. 특징 후입선출 LIFO(Last In First Out) 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 pop()을 반복해야 한다 - O(N) JAVA 에서는 Stack 라이브러리를 제공한다. Queue(큐) 삽입(en..
Linked List(연결 리스트) 특징 노드가 연결되어 있는 형태의 자료구조다. 노드 : 데이터 + 다음 노드를 가리키는 포인터 연속되지 않은 메모리 공간에 저장(+동적 할당) 시간복잡도 접근 / 탐색 : O(N) 첫 번째 노드부터 (N-1)번을 거쳐 가야 한다. 삽입 / 삭제 : 단순 삭입/삭제 : O(1), but 현실적으로 O(N) 단순하게 연결된 구조만 변경하면 된다. 그러나, 원하는 위치에 삽입/삭제 하기위해서는 접근, 탐색의 과정이 필요하다. 따라서, O(1 + N - 1) ⇒ O(N)이 된다. 배열(Array)과의 차이 배열과 달리 크기에 제한이 없어 삭제/추가 작업이 자유롭다. 배열에 비해 접근, 탐색에 시간이 오래걸린다. 배열의 접근,탐색 시간복잡도 : O(1) 참고 간략 설명! 배열(..
Thread를 단순하게 사용할 때 문제점 스레드는 생성 비용이 많이 든다. 스레드를 생성할 때마다 Kernel 레벨의 스레드와 연결해야 한다. Kernel의 작업이 필요하다. 스레드가 많아질수록 Context-Switching이 더 자주 발생하게 되어 CPU overhead가 증가한다. → Thread Pool을 사용하여 문제점을 해결한다. Thread Pool 스레드를 허용된 개수 안에서 사용하도록 제한하는 시스템을 말한다. 스레드의 최대 개수를 제한하고 미리 생성한다. 사용자로부터 들어온 요청을 작업 큐에 넣는다. 작업 큐에 들어 있는 작업을 스레드 풀의 스레드가 맡아 처리한다. 작업이 끝난 스레드는 다시 3번 과정을 진행한다. 장점 스레드를 재사용할 수 있기 때문에 새로운 스레드를 생성하는 비용을 ..
Thread Safe Race Condition 상황이 발생해도 실행에 문제가 생기지 않는 것을 의미한다. 하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하여 동시에 함께 실행되더라도 각 스레드에서의 함수의 수행 결과가 올바로 나오는 것을 의미한다. Race Condition(경쟁 상태) 공유 자원에 대해 두 개 이상의 스레드가 동시에 읽거나 쓰는 상황을 의미한다. 접근의 순서에 따라 결과값에 영향을 주는 문제가 발생할 수 있다. Thread Safe를 지키는 방법 Re-entrancy(재진입성) 정적(전역) 변수를 사용하면 안 된다. 정적(전역) 변수의 주소를 반환하면 안 된다. 호출자가 호출 시 제공한 매개 변수만으로 동작해야 한다. 싱글톤 객체의 잠금에 의존하면..
IPC(Interprocess Communication) 프로세스는 유저 영역의 독립된 공간에서 실행되어 서로간에 통신이 어렵다. 그러나, 협력해야 되는 경우가 발생한다. IPC 기법은 이러한 독립적인 프로세스들 간에 데이터 및 정보를 주고받기 위한 메커니즘을 말한다. 1. 공유 메모리(Shared Memory) 모델 주소 공간의 일부를 공유하는 방식이다. 일반적으로 OS는 프로세스 간 접근을 금지하는데, 이 제약 조건을 제거해야 한다. 시스템 콜을 통해 공유 메모리가 설정되고, 그 이후의 통신은 커널의 관여 없이 진행이 가능하다. 장점 커널의 관여가 없기에 속도가 빠르다. 양방향 통신이다. 단점 Producer-Consumer Problem 을 발생시킬 수 있다. 1. Producer가 기존의 data..
프로그램을 컴파일하고 실행하는 방법은 크게 3가지로 나뉜다. 1. Compiler(컴파일러) 정적 컴파일 방식을 사용하는 언어 번역 프로그램이다. 런타임 전 소스 코드 전체를 미리 기계어로 변환하고 컴퓨터에서 실행한다. 다른 프로그램이나 하드웨어가 처리하기에 용이한 코드로 변환하기도 한다. 장점 실행 전에 미리 기계어로 변환했기 때문에 실행 속도가 빠르다. 단점 실행 파일 전체를 전송해야 하므로, 용량이 크다. 수정 후 실행하기 위해서는 컴파일 과정을 다시 거쳐야 한다. 특정 시스템에서 번역된 실행 파일은 다른 시스템에서 실행되지 않는다. 컴파일 언어 : C, C++, C#, Basic 등 2. Interpreter(인터프리터) 런타임에 프로그래밍 코드를 직접 한 줄씩 읽어가며 해당 기능에 대응하는 기계..
