본문 바로가기

IT235

[알고리즘] ep1-5) 병합정렬(merge sort) ㅁ분할정복법 == 분할통치법(Divide and Conquer): 문제를 작은 부분으로 나누어 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방법e.g. 병합정렬, 퀵정렬, 이진탐색, 하노이탑   ㅇ병합정렬 = 합병정렬(merge sort): 비교 기반의 정렬 알고리즘 중 하나로, 분할 정복 기법을 사용"제자리 X + stable" O(nlog(n))폰 노이만이 개발했으며 stable 특성 때문에 실무에서 많이 사용된다  병합(merge) 예시 - 연결리스트로 구현한 merge 함수     (참고)      합병정렬 트리: mergeSort의 실행을 이진트리로 보이기이진트리의 각 노드는 mergeSort의 재귀호출을 표현하며 다음을 저장한다- 실행 이전의 무순리스트 및 분할- 실행 이후의 정렬리스.. 2024. 7. 5.
오버플로우 방지 코드 작성법 4가지 int calculateMid1(int left, int right) { return (left + right) / 2;} 단순히 심플한 수식이지만 오버플로우가 발생할 수 있는 위험한 코드이다오늘은 오버플로우를 방지할 수 있는 코드 작성법 4가지에 대해 설명하려 한다    1. 가장 유명한 방식int calculateMid2(int left, int right) { return left + (right - left) / 2;} 오버플로우 방지의 교과서 같은 방식이다   2. 비트 연산 방식int calculateMid3(int left, int right) { return left + ((right - left) >> 1);} 비트를 오른쪽으로 한 칸 이동시키는 연산으로, 이는 2로 나누.. 2024. 7. 5.
[알고리즘] ep1-4) 힙정렬(heap sort) 복습하고 오자!https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep1-3-%ED%9E%99heap [알고리즘] ep1-3) 힙(heap)*완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트claremont.tistory.com    ㅇ힙정렬(heap sort): 힙을 이용하여 정렬하는 방식"제자리 + unstable" O(nlog(n)) 1. 원소들을 전부 힙에 삽입한다.2. 힙의 루트는 남은 수들 중에서 최솟값(or 최댓값)을 가지므로 루트를 출력하고 힙에.. 2024. 7. 4.
[운영체제] ep10) I/O Management and Disk Scheduling I/O를 다루는 OS 설계의 목적 2가지1. 속도 이슈2. 통일된 방식으로 모든 I/O 기기를 다루는 것 속도 이슈에서 중요한 것은 Seek time(탐색시간)이다Seek time(탐색시간) - 시간 大Rotational delay(회전지연)Transfer Time(전송시간) (참고) 탐색시간, 회전지연, 전송시간 https://claremont.tistory.com/entry/%EC%BB%B4%ED%93%A8%ED%84%B0-%EA%B5%AC%EC%A1%B0-ep7-%EB%B3%B4%EC%A1%B0%EA%B8%B0%EC%96%B5%EC%9E%A5%EC%B9%98 [컴퓨터 구조] ep7) 보조기억장치하드디스크와 플래시메모리같은 보조기억장치들은 개인 컴퓨터부터 서버구성 및 관리까지 다방면으로 사용되는 부품.. 2024. 7. 4.
[운영체제] ep9) Multiprocessor and Real-Time Scheduling 멀티 프로세서 시스템이란 뭘까? 2가지 특징이 있다- 프로세서가 여러 개이지만, 메인 메모리가 딱 하나다- 하나의 OS가 시스템 전체를 관리한다 멀티 프로세서 시스템에서는 동기화(Synchronization) 개념이 매우 중요하다 [멀티 프로세서 시스템 스케줄링 디자인 이슈들]- 동기화 빈도- 프로세서 수 프로세서에 프로세스를 할당하는 방법은 2가지가 있다방법 1: 각각의 프로세서마다 별도의 레디-큐를 둔다방법 2: 전역 큐를 둔다 (큐가 c.s. 안에 있어야 한다) - Mutual Exclusion요즘에는 방법 2를 채택한다 멀티 프로그래밍을 쓸까? 말까?동기화가 자주 일어나지 않는다면 문맥 전환이 적어 오버헤드가 적기 때문에 멀티 프로그래밍을 잘 사용할 수 있지만동기화가 자주 일어난다면 문맥 전환이 .. 2024. 7. 4.
[운영체제] ep8) Uniprocessor Scheduling ㅇCPU 스케줄링: Process에 CPU 시간을 할당하는 방법스케줄링의 목적은 유저 입장과 시스템 입장으로 나눌 수 있다response time(응답시간): 프로세스가 처음 도착한 후, 처음 CPU를 할당받아 실행되기까지 걸리는 시간turnaround time(반환시간): 프로세스가 시스템에 도착한 후, 모든 작업을 마치고 종료될 때까지의 총 시간throughput(처리율/처리량): 단위시간당 Process를 종료시키는 수processor efficiency(CPU 효율성): 얼마나 OS 개입이 적고, CPU를 이용하였는지Fairness(공정성): 같은 기준을 갖은 Process들은 모두 공정하게 같은 기회를 가져야 한다Predictability(예측 가능성): 언제쯤 끝날지에 대한 예측 가능성  스케.. 2024. 7. 4.
[알고리즘] ep1-3) 힙(heap) *완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리의 일종 + 영단어 heap: 무엇인가를 차곡차곡 쌓아 올린 더미+ 자료구조의 힙(Heap)과 컴퓨터 메모리의 힙 영역(Heap Area)은 완전히 다른 개념이다  [힙의 활용]우선순위 큐(Priority Queue): 힙을 사용하여 구현할 수 있으며, 각 요소가 우선순위를 가지는 큐힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘으로, O(nlog(n))의 시간 복잡도를 가진다그래프 알고리즘: 크루스칼 알고리즘, 다익스트라 알고리즘 등에서 우선순위 큐를 활용해 최소 신장 트리,.. 2024. 7. 3.
[알고리즘] ep1-1) 우선순위 큐 ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다 활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등  [구현 방법 2가지]1. 리스트를 이용한 구현① 무순리스트로 구현: 리스트에 임의 순서로 저장e.g. 선택정렬  ② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장e.g. 삽입정렬   2. 힙을 이용한 구현① 최대 힙 사용② 최소 힙 사용   일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙)       출처 및 참고: 알고리즘-원리와.. 2024. 7. 3.
[데이터베이스] 빅데이터(Big Data) 빅데이터(Big Data): 기존의 관리 방법이나 분석 체계로는 처리하기 어려운 방대한 양의 정형, 반정형, 비정형 데이터의 집합 [TTA 정보통신용어사전] 빅데이터 유형 3가지- 정형 데이터(Structed Data): 형식과 구조가 있는 데이터  - 반정형 데이터(Semi-Structed Data): 형식과 구조가 변경될 수 있는 데이터 데이터의 구조 정보를 데이터와 함께 제공하는 파일 형식의 데이터e.g. HTML, XML, JSON(Javascript Object Notation), RDF(Resource Description, Framework)질의 처리가 어려워 데이터 분석에 사용 시 정형 데이터로 변환하여 사용한다- JSON 데이터는 CSV(Comma Separated Value) 또는 테이.. 2024. 7. 3.

티스토리툴바