본문 바로가기

자료구조

[컴퓨터구조] RAID5 디스크 복구, 패리티 계산 방법
자료구조 2021. 6. 8. [컴퓨터구조] RAID5 디스크 복구, 패리티 계산 방법 ※ E block 의 패리티비트의 계산 오류가 있어 2023.12.06에 내용이 수정되었습니다. 지적해주신 지환킴님 상기님 감사합니다. 위 그림은 리눅스에서 가장 흔하게 볼 수 있는 RAID5(레이드5)로 구성된 이미지입니다. 이 포스트에서는 그렇게 크게 중요한 것은 아닌데, 서론만 조금 설명해보면 레이드 5 구성은 보통 최소 3개 이상의 디스크로 구성된 것을 말합니다. 보통은 디스크 5개로 구성해서, 각 디스크마다 패리티를 한개씩 분산되어 저장합니다. 이 중에서 디스크가 하나가 사망선고를 당해서 데이터가 사라져도, 이 포스팅 주제인 패리티 XOR연산을 통해 데이터를 얼마든지 복구가 가능합니다. 대신 얼마든지 복구가 가능한 것은 조건이 한가지가 따라옵니다. 바로 "디스크가 5개라고 가정했을 때, 최소 3..
[자료구조] 버블 정렬
자료구조 2018. 9. 23. [자료구조] 버블 정렬 자료구조의 기본 알고리즘 " 버블정렬 " 구현이 간단하고 쉬운 정렬부터 하다보니, 여전히 성능에서는 많이 떨어지는 경향이 있네요. 버블정렬이란, 맨 앞 2개 데이터씩 비교하면서 작은 수를 한 칸씩 앞으로 당겨오는 것을 말해요. 계속 당겨오는 것을 반복하면서 데이터 개 수만큼 반복하면 어느새 정렬이 되어있게되죠 :-) 그래서 시간복잡도는 O(n²) 그림을 보면서 이해하도록 하죠 :) 이렇게 한 바퀴를 돌면 가장 큰 수인 [4]가 맨 뒤로 정렬되게 되죠. 그럼 이 규칙을 확인해보면, 한 바퀴 돌때마다 가장 큰 수가 맨뒤로 정렬되는 규칙이 확인했구요! 그렇다면 다음번 비교할 때는 맨 마지막 값을 하나씩 빼면서 비교하면 되겠군요!? 이런 규칙을 통해서 최종 정렬 결과는 [ 1, 2, 3, 4 ] 가 나오겠죠? ..
[자료구조] 삽입 정렬
자료구조 2018. 9. 23. [자료구조] 삽입 정렬 자료구조의 기본 알고리즘 " 삽입정렬 " 이번에도 구현이 아주 쉽지만, 시간복잡도가 미친듯이 높은 한마디로 성능이 좋지않은 정렬 방법을 소개하려해요. 삽입정렬이란, 원본 데이터에서 값을 하나씩 꺼내서 새로운 리스트의 가장 마지막 값 또는 처음 값부터 끝까지 전체 데이터를 비교해서 해당 데이터에 맞는 자리에 삽입을 해주는 정렬이에요. 그래서 시간복잡도는 O(n²) 위 글 요약으로만 이해되셨을 수도 있지만, 이해가 잘 되지 않는 분을 위해 그림과 함께 다시 한번 더 설명해보도록 하죠. 그림처럼 정렬되지 않은 데이터가 [ 3 , 2 , 1 , 4 ] 일 때, 데이터를 하나씩 꺼내와서, 새로운 리스트에 들어가있는 모든 데이터와 비교를 하여 정렬하는 알고리즘입니다. 구현은 매우 쉽지만 실무에서는 거의 사용되지 않..
자료구조 2018. 9. 23. [자료구조] 선택 정렬 자료구조의 기본 알고리즘 " 선택 정렬 " 선택정렬이란, 가장 무식하고 단순한 방법으로 비교하여 정렬하는 알고리즘이죠 최악의 경우 데이터가 많아질수록 속도 성능은 제곱만큼 하락하는 정말 우리나라에선 사용 못할거에요 그쵸? 그리하여 결론은 선택정렬의 시간복잡도는 O(n²) 그럼 알고리즘을 하나하나 비교해보도록 해볼게요. 아래와 같이 랜덤한 숫자 5개가 있다고 가정한다면 Step 1. 8 9 10 2 6 1-1 : 첫 번째 비교대상의 시작은 8이니, 배열의 최소 값은 8. 1-2 : 9는 최소값(8)보다 작은가 ? No ! 1-3 : 10은 최소 최소값(8)보다 작은가 ? No ! 1-4 : 2는 최소값(8)보다 작은가 ? Yes ! 그렇다면 최소값은 2. 1-5 : 6은 최소값(2)보다 작은가 ? No !..

티스토리툴바