본문 바로가기

Base

알고리즘 - Dynamic Programming(동적프로그래밍)이란? Dynamic Programming(동적계획법) 이란 1. Dynamic Programming(동적계획법)이란?큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말입니다. 동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없습니다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 합니다. 1.1 Divide and Conquer(분할정복)과 비슷한데요?네, 거의 비슷하지만 결정적인 차이점이 있습니다. 바로 작은 문제가 중복이 일어나는지 안일어나는지 입니다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법입니다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점입니다. 동적프로그래밍은 어떨까요? 네, 작은 ..
작성일: 2019. 4. 6. 19:23
자료구조 - 힙(Heap)이란? 힙 힙(Heap) 이란?- 힙은 최댓값, 최솟값을 찾아내는 연산을 쉽게하기 위해 고안된 자료형이다.- 힙(Heap)은 각 노드의 키(Key)값이 그 자식의 키값보다 작지않거나(최대 힙), 그 자식의 키값보다 크지 않은(최소 힙) 완전 이진 트리이다. 아래 그림은 최대힙(Max Heap)을 나타내는 그림이다. 최대 힙(Max Heap) - 각 노드의 키값이 그 자식노드의 키값보다 큰 힙최소 힙(Min Heap) - 각 노드의 키값이 그 자식노드의 키값보다 작은 힙 힙 연산아래의 연산들은 최대(Max Heap)힙을 기준으로 설명한다. 삽입 연산- 힙은 완전이진트리의 구조를 유지해야 하므로 삽입시 트리의 가장 마지막에 원소를 추가하는 것으로 시작한다. 5를 키로 가지는 원소 삽입우선 힙은 완전이진트리의 구조를..
작성일: 2019. 3. 22. 12:43
자료구조 - 큐(Queue)란? Queue란 Queue란- 큐는 한쪽 끝(rear)에서는 삽입연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제연산만 이루어지는 유한 순서 리스트이다. 특성- 구조상 먼저 삽입된 item이 먼저 삭제가 이루어진다. (FIFO) 큐의 표현1. 순차 표현- 1차원 배열을 이용한 순차표현이다.- 인덱스를 값으로 가지는 front, rear 라는 두개의 변수와 큐의 사이즈를 나타내는 n이라는 변수를 사용한다.- front, rear를 -1로 초기화 하여 큐가 empty임을 나타낸다. (front == rear일 때 큐는 공백)- rear에서 삽입 되므로 rear가 점차 증가하여 rear==n-1인 경우 큐는 full상태이다. 문제점- 큐에 삽입이 되며 점차 rear가 증가하게 되면 결국 full상태가 된다...
작성일: 2019. 3. 21. 15:14
알고리즘 - 그리디01 그리디(Greedy) 알고리즘이란? 그리디(Greedy) 알고리즘 이란- 그리디(Greedy) 알고리즘이란 탐욕알고리즘이란 뜻으로 각 단계에서 최선책만을 선택하며 다음단계로 진행하는 알고리즘을 말한다. - 최적의 해를 구하는 알고리즘은 아니다 최적의 해의 근사의 해를 구하는 알고리즘이다.- 동적프로그래밍이 지나치게 많은 일을 하는 것에서 착안하여 고안된 알고리즘이며 동적프로그래밍을 대체하는 것은 아니고 서로 보완하며 사용되는 알고리즘이다.- 각 단계에서 최선책만을 선택하기 때문에 현재의 선택에 의해 다음 단계의 조건이 변하는 경우에는 부적합한 알고리즘이다. 최적의 해가 아닌 이유?- 그리디 알고리즘은 당장 선택할 수 있는 경우중 최선의 선택을 하기 때문이다. 예를 들어 지금 당장 금을 팔면 1돈에 10000원인데 내일은 1돈에 12000원..
작성일: 2019. 3. 18. 18:04
자료구조 - Array(배열과) List 비교 Array(배열) 과 List의 차이점 Array(배열) 과 List의 차이점Array? - 다수의 데이터를 그룹핑해서 효율적으로 관리 가능한 자료형으로 데이터에 접근하기 위한 인덱스가 존재한다.장점- 인덱스를 통해 데이터를 가져오기 때문에 조회 속도가 빠르다.단점- 인덱스를 통해 데이터를 가져온다 즉, 데이터의 위치가 인덱스와 맵핑되어 고정된다. 추후 데이터가 삭제되는 경우 배열의 빈부분의 메모리가 낭비된다.- 위의 이유로 배열의 해당 인덱스에 데이터가 존재하는지 파악하는 로직이 추가적으로 필요하다. List? - 배열이 가진 인덱스의 장점을 버리고 대신 빈틈없이 데이터를 적재하는 장점을 취한 자료형. - 순서가 있으며 중복이 허용되는 자료형. 간단한 이해Array(배열) - 주민등록번호와 비교하면 된..
작성일: 2019. 3. 17. 19:10
운영체제 - 프로세스 동기화란? 프로세스 동기화 프로세스 동기화프로세스 동기화란하나의 자원을 한 순간에 하나의 프로세스만이 이용하도록 제어하는 것 스레드 동기화란하나의 코드블록 또는 메소드를 한순간에 하나의 스레드만이 이용하도록 보장하는 것 동기화가 없다면- 데이터 일관성이 깨짐 => 즉, 한 순간 하나의 데이터의 값이 여러개일 수도 있게 됨, 다시 말해 여러개의 스레드가 하나의 변수에 대한 값이 제각각일 수 있게 됨. 배경협력적 프로세스는 시스템 내에서 실행중인 다른 프로세스의 실행에 영향을 주거나 받는 프로세스 이다. 협력적 프로세스는 논리 주소 공간(코드, 또는 데이터)를 직접 공유 하거나 파일 또는 메시지에 의해서 공유가 이루어진다 전자의 방법을 통해 논리 주소 공간을 공유하는 것은 스레드(Thread)를 통해 달성할 수 있다...
작성일: 2019. 3. 5. 11:55
JAVA 퀵정렬(Quick Sort)이란 - 수정중 https://www.youtube.com/watch?v=7BDzle2n47c&t=303s 과정1. 배열에서 적절한 피봇을 선출한다- 배열에서 값이 중간값일 수록 좋지만 중간값을 찾기위해서는 탐색을 해야하므로 물리적으로 중간에 위치한 값을 피봇으로 선택 2. 배열의 시작위치의 인덱스를 L로 지정하고 배열의 끝 위치의 인덱스를 R로 지정한다 3. L은 피봇값보다 작은값(L < Pivot)은 무시하며 인덱스를 1씩 증가시킨다(계속해서 증가하다가 Pivot의 위치에 다달으면 Pivot값보다 작은값이 아니므로 피봇의 위치에서 멈추게 된다) 4. R은 피봇값보다 큰값(R > Pivot)은 무시하며 인덱스를 1씩 감소시킨다(계속해서 감소하다가 Pivot의 위치에 다달으면 Pivot값보다 큰값이 아니므로 피봇의 위치..
작성일: 2018. 11. 18. 19:30
프로세스간 통신(IPC) - 수정중 위 그림처럼 각각의 프로세스는 완전히 독립되어있다.장점 : 다른 프로세스에게 영향을 주지도 받지도 않는다단점 : 프로세스간 통신을위해 커널영역에서 IPC를 제공해야 한다 프로세스의 종류1. 독립 프로세스 - 다른 프로세스로부터 영향을 주지도 받지도 않는 프로세스 2. 협력 프로세스- 반대로 다른 프로세스로부터 영향을 주고 받는 프로세스 협력프로세스 이유1. 정보 공유2. 계산 가속화 등등 프로세스간 통신이란- 협력적 프로세스들이 서로 데이터와 정보를 교환할 수 있도록 하는 기법 단일 PC에서의 프로세스간 통신1. 공유메모리- 공유메모리 구축시에만 커널명령어를 사용- 공유메모리를 사용할 때에는 일반명령어로 사용가능- 일반적으로 운영체제는 한프로세스가 다른 프로세스의 메모리로 접근하는것을 금한다 공유메모리는..
작성일: 2018. 11. 18. 11:27