Computer Science10 [자료구조] 그래프 1. 기본 개념 노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조, 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 예) 지하철 노선도, 네트워크 연결, 도로, 페이지 랭크 2. 그래프 용어 정리 정점(node): 위치의 개념 간선(edge): 위치 간의 관계, 노드를 연결하는 선 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 3. 종류 무방향 그래프(양방향) (A, B)는 (B, A) 동일 방향 그래프 는 는 다름 가중치 그래프 그래프의 간선에 비용(가중치)가 부여된 그래프 최소 비용, 최단 경로 등을 찾는 경우 연결 그래프 무방향 그래프의 모든 정점 쌍에 대해 항상 경로가 존재하는 경우 비연결 그래프 무방향 그래프의 특정 정점 쌍 사이에 경로가 존재하지.. 2022. 11. 27. [자료구조/알고리즘] 정렬 알고리즘에 대해 알아보자 선택 정렬(Selection Sort) 공간복잡도 O(N) / 시간복잡도 O(N^2) 첫 번째 인덱스부터 차례대로 그 뒤 숫자들을 모두 비교해서 가장 작은 값을 찾아 현재 인덱스와 자리를 바꿔준다. 즉, 맨 앞 인덱스부터 작은 수대로 채워 정렬하는 것(최소 선택 정렬), 반대는 최대 선택 정렬이다. 삽입 정렬(Insertion Sort) 공간복잡도 O(N) / 시간 복잡도 O(N^2), 최선의 경우(이미 정렬돼 있는 경우는 한번 밖에 비교하지 않아서) O(N) 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장, 비교 인덱스를 현재 인덱스 -1로 시작해서 -1씩 해가며 요소를 비교하고 적절한 위치를 찾아 삽입된다. 즉, 두 번째 요소는 첫 번째 요소와 비교. 세 번째 -> 두 번.. 2022. 10. 31. [OS] 프로세스와 스레드 동기화 ✨프로세스 동기화 : 하나의 자원을 한 시점에 하나의 프로세스만이 접근 ✨스레드 동기화 : 하나의 코드 블록 또는 메소드를 한 시점에 하나의 스레드만이 접근 🟠한 스레드의 특정 작업이 끝나기 전까지 다른 스레드의 방해를 받지 않도록 하는 것이 필요함(데이터 일관성 유지를 위해) 그래서 도입된 개념이 바로 임계 영역과 잠금(락, lock)이다. 🟠공유 데이터를 사용하는 코드 영역을 임계 영역으로 정해놓고, 공유 데이터(객체)가 가지고 있는 락을 획득한 단 하나의 스레드만이 해당 영역 내의 코드를 수행할 수 있게 한다. 그리고 해당 스레드가 임계 영역 내의 모든 코드를 수행하고 벗어나서 락을 반납해야지만 다른 스레드가 반납된 락을 획득하여 임계영역의 코드를 수행할 수 있게 된다. 🟠이처럼 한 스레드가 진행 .. 2020. 12. 2. [OS] 컨텍스트 스위칭(문맥교환Context Switching) 🎂 컨텍스트 스위칭(context switching)이란? CPU가 어떤 프로세스를 실행하고 있는 상태에서 인터럽트에 의해 다음 우선 순위를 가진 프로세스가 실행되어야 할 때 기존의 프로세스 정보들은 PCB에 저장하고 다음 프로세스의 정보를 PCB에서 가져와 교체하는 작업을 컨텍스트 스위칭이라 한다. 이러한 컨텍스트 스위칭을 통해 우리는 멀티 프로세싱, 멀티 스레딩 운영이 가능하다 ! 컨텍스트 스위칭은 다음과 같은 상황에서 일어난다. I/O interrupt CPU 사용시간 만료 자식 프로세스 Fork 이러한 컨텍스트 스위칭이 일어날 때 다음번 프로세스는 스케줄러가 결정하게 된다. 즉, 컨텍스트 스위칭을 하는 주체는 스케줄러이다. 단점 : PCB를 저장하고 가져올때는 CPU가 아무런 일도 하지 못하게 된.. 2020. 12. 1. [OS] 프로세스와 스레드 💫 간단 개념 💬 프로세스(Process) 현재 실행중인 프로그램이며, 운영체제로부터 고유 공간과 자원을 할당 받아 실행되는 작업 단위 💬 스레드(Thread) 해당 프로세스 안에서의 작업 흐름을 보여주는 실행 단위, 한 프로세스 내 스레드들 간 메모리를 공유한다. 💫 주요 특징 💬 프로세스 운영체제로부터 고유의 주소 공간과 자원을 할당 받아 실행 CODE, DATA, HEAP, STACK 구조로 이루어져 있음 다른 프로세스의 영향을 받지 않고 독립적으로 실행 과거에는 하나의 프로세스만 실행할 수 있었지만, 지금은 병렬 처리하는 '멀티 프로세스(멀티 태스킹)' 가능 💬 스레드(Thread) 한 프로세스 내에서 여러 스레드를 동시에 실행 가능 -> 바로 '멀티 스레드' 스택은 고유하게 할당 받지만 그 외 .. 2020. 11. 30. [OS] 운영체제(Operating System)의 개념 💫운영체제란? 하드웨어를 관리하고, 응용 프로그램과 하드웨어 사이에서 인터페이스 역할을 하는 시스템 소프트웨어다. 시스템의 자원 및 동작을 관리한다. 더 쉽게 말하자면, 컴퓨터의 복잡한 하드웨어를 잘 모르더라도 컴퓨터를 사용하고 프로그램을 만들 수 있도록 지원해주는 소프트웨어다. 💫운영체제의 사용 목적 컴퓨터 자원을 더 효율적으로 사용하게끔 도와준다! 운영체제를 사용하는 이유는 처리능력 향상, 사용가능도 향상, 신뢰도 향상, 응답시간 단축하기 위함이다. 처리능력(Throughput) 시스템의 생산성을 나타내는 단위, 일정 시간 내에 시스템이 처리하는 일의 양 응답시간(Turn Around Time) 시스템에 작업을 의뢰한 시간부터 처리가 완료될 떄까지 걸린 시간 사용가능도(Availability) 시스템.. 2020. 11. 30. 이전 1 2 다음
