전체 글

인터럽트 하드웨어 인터럽트 timer의 인터럽트 컨트롤러의 인터럽트 : 요청한 I/O 작업이 끝났다는 것을 CPU에게 알림 트랩(Trap, 소프트웨어 인터럽트) Exception : 프로그램이 오류를 범한 경우 (ex. 0으로 나누는 연산, 사용자 프로그램에서 운영체제에 접근 등) System call : 프로그램이 커널 함수를 호출하는 경우 인터럽트 벡터 인터럽트의 처리 루틴의 주소를 가지고 있음 인터럽트 처리 루틴 인터럽트를 처리하는 커널 함수 — 인스트럭션이 실행되고 다음 인스트럭션이 실행되기 전에 I/O컨트롤러나 timer에서 보낸 인터럽트가 들어왔는지 체크 — 만약 인터럽트가 들어왔다면 지금 하던 작업을 멈추고(Program Counter 저장) CPU 제어권을 운영체제(OS)에게 넘김 — 운영..

트리 구조 트리는 노드(Node)와 노드들을 연결하는 간선(Edge)으로 연결된 비선형 자료구조 관련 용어 노드(Node) 트리를 구성하는 기본 용소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 갖고 있음 노드 : A, B, C, D, E, F, G, H, I ,J 간선(Edge) 노드와 노드 간의 연결선 루트 노드(Root node) 트리 구조에서 부모가 없는 최상위 노드 루트 노드 : A 부모 노드(Parent node) 자식 노드를 가진 노드 H, I의 부모 노드는 D 자식 노드(Child node) 부모 노드의 하위 노드 노드 D의 자식 노드는 H, I 형제 노드(Sibling node) 같은 부모를 가진 노드 H, I은 같은 부모를 가진 형제 노드 리프 노드, 외부 노드, 단말 노드(Lea..

알고리즘 문제풀이 2468. 안전영역 그래프 탐색으로 모든 좌표 순회 방문여부(visited)와 높이로 조건 설정 시간초과 발생.. from collections import deque import sys input = sys.stdin.readline dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] deq = deque() def search(graph, height): visited = [[0]*n for i in range(n)] count = 0 for y in range(n): for x in range(n): if graph[x][y] > height and visited[x][y] == 0: deq.append((x, y)) count += 1 visited[x][y] =..

알고리즘 및 정렬 구현 더보기 오늘은 문제를 제대로 푼 게 없는것 같다.. 벌써 정체가 오면 안되는데, 하나도 쉬운게 없다. 남들은 진도가 쑥쑥 나가는데 조금 무섭다. 남들과 비교하면 안되지만 어쩔 수가 없다. 더 열심히 하자❗️ 11279. 최대 힙 힙 정렬 구현 이중 완전 트리인 힙을 가장 마지막 노드의 부모 노드부터 순차적으로 힙 정렬 부모 노드와 마지막 노드를 스왑(Swap)하고 다시 힙 정렬 실시 def max_heapify(arr, n, i): largest = i # 부모 노드의 인덱스로 초기화 left = 2 * i + 1 # 왼쪽 자식 노드의 인덱스 right = 2 * i + 2 # 오른쪽 자식 노드의 인덱스 # 왼쪽 자식 노드가 부모 노드보다 크면 largest 값을 갱신 if lef..

해시 테이블(Hash Table) Key, Value로 데이터를 저장하는 자료구조 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 떄문에 데이터 검색할 수 있음 시간복잡도 O(1) -> Search(검색), Insert(삽입), Delete(삭제) 해시값으로 변환하는 과정을 '해시 함수(Hash Function)'이라고 함 저장할 배열(버킷)이 중복되는 현상 -> 해시 충돌(Collsion) 해시법 데이터 저장 위치 = 인덱스 데이터 추가 또는 삭제가 빈번한 경우 효율적으로 수행 가능 해시(hash)란 특정 연산의 결과 값(데이터 접근시 사용) 원소값을 해시값으로 변환하는 과정 -> 해시 함수(Hash Function) 해시 충돌 처리방법 체인법(Chaining) : 해시값이 같은 원소를 연결 리스트..

퀵 정렬(Quick Sort) 가장 빠른 정렬 알고리즘으로 알려져있음 피벗(pivot)을 기준으로 좌측에는 피벗보다 작은 값, 우측에는 큰 값을 정렬 def qsort(arr, start, end): # 배열과 좌우 끝 인덱스 pl = start pr = end # 피봇값 지정 pivot = arr[(pl+pr)//2] # 우측 인덱스가 좌측 인덱스가 크거나 같을동안 진행 while pl pivot: pr -= 1 # 좌우 인덱스가 교차하지 않을때 swap if pl pl: qsort(arr, pl, end) array = [5, 2, 6, 7, 4, 3, 8, 1, 9, 0] qsort(array, 0, 9) print(array)# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 피벗(pivot)..

컴퓨터 시스템(CS:APP) 인트로 아래와 같이 hello.c 프로그램의 수명주기를 따라가면서 주요 개념과 용어, 관련된 구성요소를 소개 #include int main() { printf("hello, world\n"); return 0; } 1.1 정보는 비트와 컨텍스트로 이루어진다. hello 프로그램은 소스 프로그램(소스파일)으로 생성되어 hello.c라는 텍스트 파일에 저장됨 소스 프로그램 : 0과 1로 표시되는 비트(bit)들의 연속 / 바이트라는 8비트 단위로 구성 각 바이트는 프로그램의 텍스트 문자를 나타냄 대부분 컴퓨터 시스템은 텍스트 문자를 아스키(ASCII) 표준을 사용해 표시 아스키 표준은 각 문자를 바이트 길이의 정수 값으로 나타냄 hello.c처럼 오로지 아스키 문자들로만 이루어..