개발공부 블로그

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 동기화와 관련된 문제 동기화와 관련된 고전적인 문제가 3가지 있다 Bounded-Buffer-Problem Readers-Writers Problem Dining-Philosophers Problem 3. Dining Philosophers Example = 식사하는 철학자 문제(Dining-Philosophers Problem) Dining Philosophers Example 코드 Synchronization variables semaphore chopstick[5]; //모든 초기값은 1로 가정한다 Phiolsopher i do { P(chopstick[i..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 동기화와 관련된 문제 동기화와 관련된 고전적인 문제가 3가지 있다 Bounded-Buffer-Problem Readers-Writers Problem Dining-Philosophers Problem 1. Bounded-Buffer-Problem 버퍼의 크기는 유한하다 -> 생산자 & 소비자 문제가 발생한다 프로세스가 Producer/Consumer로 여럿 존재한다 Producer(생산자) Empty 버퍼가 있는지 확인한다(없으면 기다린다) 공유 데이터에 lock을 건다 Empty Buffer에 데이터 입력 및 버퍼를 조작한다 lock을 푼다 Full buffe..

https://www.boostcourse.org/cs204 자료구조 강의를 듣고 정리한 내용입니다 *강의 후반부에서 다루는 알고리즘에 대한 내용을 정리한 글입니다 알고리즘과 관련된 선수지식 > 리스트에 있는 데이터를 정렬할 때, 어떻게 정렬을 할 것인지 고려해야 한다 Out-of-place 정렬 데이터 구조의 복사본을 만든 후 정렬하는 방법이다 //용량이 늘어난다 in-place 정렬 내부에서 데이터 구조들의 위치를 바꾸어 정렬하는 방법이다 > 리스트에 중복된 요소가 있는지 체크해야한다 안정 정렬 : 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는 방법이다 -> 순차적이고, 규칙적이다 불안정 정렬 : 중복된 숫자의 순서를 보장할 수 없다 -> 비 순차적, 불규칙적이다 > 해당 정렬 알고리즘을 썼을때 ..

https://www.boostcourse.org/cs204 자료구조 강의를 듣고 정리한 내용입니다 레드 블랙 트리 색상 변환 -> 노드의 색을 바꾸는 것 색상변환을 하면 부모, 이모노드는 검은색 조부모 노드는 빨간색이 된다 회전을 하고나면 부모, 이모노드는 빨간색 조부모 노드는 검은색이 된다 레드 블랙 트리에서는 트리를 생성한 후 트리의 색을 파악하여 규칙을 어긴 것이 있는 지 확인한다 이때 해당 노드의 조부모 노드를 고쳐야한다 해당 노드를 고치는것이 아니다 레드 블랙 트리 코드 public void checkColor(Node node) { if(node == root) return; if(!node.black && !node.parent.black) //메서드를 호출하여 이모 노드의 색깔을 파악한다..

https://www.boostcourse.org/cs204 자료구조 강의를 듣고 정리한 내용입니다 adding data 균형이 맞아야한다는 규칙에 따른 트리 생성 어떤 종류의 회전을 했는지 기입하고 트리의 상태를 항상 그려야 한다 -> 트리가 균형이 맞는지 확인하는 과정에서 필요하다 트리의 균형을 맞추는 또 다른 방식 레드 블랙 트리 모든 노드를 빨강 또는 검정으로 설정한다 새로운 요소를 추가 할 때 마다 규칙을 확인한다 트리의 규칙(중요) 모든 노드는 빨간색이거나 검은색이다 루트는 항상 검은색이다 //아닐시 강제로 변환 새로 추가되는 노드는 항상 빨간색이다 //빨강 -> 검정 루트에서 잎 노드로 가는 모든 경로 (== 트리에서 만들 수 있는 모든 경로)는 같은 수의 검은색 노드가 있어야 한다 어떤 경..

AVL 트리 스스로 균형을 잡는 이진 트리 자료구조를 말한다. 왼쪽과 오른쪽의 높이 차이는 항상 1보다 작거나 같아야 한다 높이의 차이가 1보다 커지면 트리의 규칙을 어긴것이다 예시 1 4 (노드) 2 8 10 12 불안정 -> 조부모 노드인 8을 좌측 회전을 해야 한다 예시 1 회전 후 4 2 10 8 12 트리의 균형을 되찾음 예시 2 10 8 12 4 2 AVL 규칙에 어긋난다 -> 8에 대해서 우측 회전을 해야한다 회전 후 10 4 12 2 8 왼쪽 자식의 서브 트리에서 문제가 생긴 경우 조부모인 10이 좌측-우측회전을 해야한다 -> 문제 해결을 위해 회전을 해야한다 회전을 할 때는 루트로 올라가서 방금 한 회전이 트리 위쪽에 새로운 문제를 야기했는지 확인해야 한다 만약 문제가 발생시 고쳐야 한다..

트리의 회전 이진 트리의 시간 복잡도는 O(log n)이고 한쪽으로 치우친 트리는 O(n)이다 -> 이 차이점을 균형이라고 한다 //균형잡힌 트리 ->데이터를 효율적으로 관리하기 위해서 균형있는 트리를 만들어야 한다 트리는 최대한 균형 잡히게 만들기 위해서는 숫자들이 정렬되어있어야 한다 균형잡힌 트리를 만들기 위해 트리의 노드 위치를 변경하는 것을 회전이라고 한다 조부모, 부모, 자식 노드 크기 관계에 따라 우측 회전, 혹은 좌측 회전을 한다. 트리를 재정렬하면 항상 중간 크기의 요소가 가장 위에 있는 루트가 된다 회전 방법 불균형이 왼쪽 서브트리에서 나타나는 경우 크기 관계는 조부모 노드 > 부모 노드 > 자식 노드이다 우측 회전을 하여 조부모 노드를 오른쪽 자식 노드의 위치로 옮긴다 불균형이 오른쪽 ..

트리의 표현 * //root 2 3 의 트리가 있을 때 중위식 : 2 * 3 전위식 : * 2 3 후위식 : 2 3 * 트리의 규칙 부모를 기준으로 작은 것이 왼쪽에 와야 한다 연결리스트에서 노드가 next 포인터를 갖고있었던 것처럼 트리에서는 left, right 포인터를 갖는다 트리의 노드 클래스 class Node { E data; Node left, right; public Node(E obj) { this.data = obj; left = right = nll; } } 트리에 새로운 데이터를 추가하는 과정 루트에서부터 시작한다 트리의 규칙에 따라 내려간다 null인 부분을 찾았다면 그 곳에 새로운 노드를 추가한다 트리의 재귀함수 재귀 함수를 이용하여 트리의 규칙에 따라 내려가는 기능을 구현한다 ..

힙에서 요소를 제거 무언가를 제거할 때 힙에서는 항상 루트에 있는 요소를 제거해야 한다 트리의 마지막 요소를 루트에 넣는다 -> 최대 힙 규칙에 어긋남 -> 적절한 위치를 찾을 때까지 계속 두 노드의 위치를 바꾼다 ->두 자식 중 큰 노드와 교환하는 것이 포인트이다 (중요) 힙에서 제거할 수 있는 요소는 루트뿐이다 루트에 있는 요소를 지우면 구멍이 생기고, 이를 메워야 한다 -> 힙에있는 마지막 요소를 넣는다 ->자식 노드보다 작은지 확인 후 위치를 바꿔야 한다 자식 노드중에서 큰 수와 위치를 변경해야 한다 이러한 과정을 "trickle down"이라고 한다 trickle down 과정이 끝나는 경우 lastposition 변수보다 큰 경우 -> 현재 위치에서 자식 노드가 하나만 있을 수도 있다는 점을 ..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 추상 자료형 : Object와 Operation으로 이루어져있다. 논리적으로 정의를 하는 것을 말한다. Semaphore S 이전의 방식들을 추상화시킨 방법으로 정수값을 가질 수 있는 추상자료형이다 lock을 걸고 푸는 것을 간단하게 사용가능하게 만든다 공유 자원을 획득하고 반납하는 것을 처리해준다 P연산과 V연산에 의해서만 접근 가능하다 P(S) : //lock을 거는 과정 while(S 자원을 획득한다 V(S) : //lock을 푸는 과정 while(S 자원을 반납한다 코드로 구현 Synchronization variable -> semaphore mutex..