Computer Science30 [OS] 임계구역과 경쟁상태 그리고 동기화 목표: 멀티 프로세스/쓰레드 환경에서 핵심적인 문제인 동기화가 무엇인지 살펴봅니다. BankAccount 예제를 통해서 경쟁 상태와 임계 구역 문제에 대해 알아봅니다. 쓰레드에 대한 기본 개념이 없으신 분들은 이 글을 참조해주세요. 경쟁상태와 임계구역 현대의 운영체제 대부분은 멀티 쓰레드를 지원합니다. 근데 이때 공유 자원(shared data)에 여러 쓰레드가 접근해 값을 수정하면 데이터의 일관성(consistency)이 깨지게 되는데, 이를 경쟁 상태(Race Condition)라고 합니다. 이 경쟁 상태를 해결하기 위한 것이 동기화(Synchronization)입니다. 예를 들어보죠. 하나의 은행 계좌(공유 자원)에 부모님은 돈을 입금하고 자식은 돈을 출금하는 상황을 코드로 구현해 보겠습니다. 우선.. 2021. 4. 10. [정렬] 삽입정렬(Insertion Sort) 특징 구현이 간단하다 제자리 정렬이다 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 기본 아이디어 i는 1부터 시작하여 n-1까지 늘려간다. array[0]부터 array[i-1]까지 정렬되어 있을 때, array[i]를 포함하여 정렬한다. array[i]를 뒤에서부터 순차적으로 array[i-1], array[i-2] ... 과 비교하다가 자기보다 작은 숫자가 나오면 그 뒤에 삽입한다. 아래 영상 참고 www.youtube.com/watch?v=OGzPmgsI-pQ 비교연산은 1 + 2 + 3 + ... + (n-1) 회 일어나고, 스왑 연산의 횟수도 비교 연산과 같으므로 시간 복잡도는 O(n^2) 파이썬 코드 def insertion_sort(array): for i in range(1, l.. 2021. 3. 28. [정렬] 선택정렬 (Selection Sort) 특징 가장 기본적인 정렬 알고리즘이며 구현이 쉽다. 제자리 정렬 알고리즘이다. 불안정 정렬 알고리즘이다. 시간 복잡도가 O(n^2)으로 상당히 느리다. 기본 아이디어 배열을 순회하며 최소값을 찾는다. 최소값을 찾으면 배열의 가장 첫 인덱스에 있는 값과 자리를 바꾼다. (최대값을 찾을 수도 있다. 이때는 가장 뒤에 있는 값과 자리를 바꾼다.) 다시 배열을 순회하며 다음 최소값을 찾는다. 최소값을 찾으면 두 번째 인덱스에 있는 값과 자리를 바꾼다. 원소가 하나 남을 때까지 위 과정을 반복한다. 원소가 들어갈 자리는 이미 정해져 있고, 그 자리에 넣을 원소를선택하는 알고리즘 의사 코드 Algorithm selection_sort(array) input: array output: sorted array for .. 2021. 3. 26. [정렬] 버블정렬 (Bubble Sort) 특징 구현이 쉽다. 제자리 정렬이다. 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 스왑 연산이 많이 일어나기 때문에 굉장히 비효율적이다. 기본 아이디어 배열을 순회하면서 서로 인접한 두 원소를 비교한다. 만약 더 큰 원소가 앞쪽에 있다면 두 원소의 자리를 바꾼다(오름차순 기준). 만약 마지막까지 도달했는데 스왑이 한번도 일어나지 않았다면, 모든 원소가 정렬 상태에 도달한 것으로 판단할 수 있다. 이때는 연산이 끝나지 않았음에도 강제로 연산을 종료함으로써 수행시간을 조금 더 줄일 수 있다. 의사코드 Algorithm bubble_sort(array) input: array output: void n = length of array for i = n-1 to 2 by -1 do sorted = T.. 2021. 3. 11. [정렬] (번역) 정렬 알고리즘에서 안정성(Stability)이란? 이 포스팅은 아래 글을 번역 및 요약한 것입니다. Stability in sorting algorithms - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 정렬 알고리즘에서 말하는 안정성(stability)란 키-값 쌍을 가진 객체들 중 같은 키를 가진 객체들의 순서가 정렬 이후에도 유지되는 것을 말합니다. 위 .. 2021. 2. 15. 중간값을 구하는 안전한 방법 보통 중간값을 다음과 같이 나타내는 경우가 많은데, int mid = (start + end) / 2; 이건 별로 좋은 방법이 아니다. 작은 수에서는 문제가 일어나지 않지만 start + end가 정수 표현 범위(-2,147,483,647 ~ 2,147,483,647)를 넘어서는 경우 오버플로우가 일어나기 때문에 원하는 값을 얻을 수 없다. public class Main { public static void main(String[] args) { int start = 1_500_000_000; int end = 1_600_000_000; int mid = (start + end) / 2; System.out.println("mid = " + mid); } } 실행 결과 mid = -597483648 따.. 2021. 2. 15. 이전 1 2 3 4 5 다음
