Computer Science
[자료구조] 그래프
1. 기본 개념 노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조, 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 예) 지하철 노선도, 네트워크 연결, 도로, 페이지 랭크 2. 그래프 용어 정리 정점(node): 위치의 개념 간선(edge): 위치 간의 관계, 노드를 연결하는 선 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 3. 종류 무방향 그래프(양방향) (A, B)는 (B, A) 동일 방향 그래프 는 는 다름 가중치 그래프 그래프의 간선에 비용(가중치)가 부여된 그래프 최소 비용, 최단 경로 등을 찾는 경우 연결 그래프 무방향 그래프의 모든 정점 쌍에 대해 항상 경로가 존재하는 경우 비연결 그래프 무방향 그래프의 특정 정점 쌍 사이에 경로가 존재하지..
![[자료구조/알고리즘] 정렬 알고리즘에 대해 알아보자](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FI7xi3%2FbtrP8Ov877H%2F0xDh90MiNe7JdEKjibeVd0%2Fimg.png)
[자료구조/알고리즘] 정렬 알고리즘에 대해 알아보자
선택 정렬(Selection Sort) 공간복잡도 O(N) / 시간복잡도 O(N^2) 첫 번째 인덱스부터 차례대로 그 뒤 숫자들을 모두 비교해서 가장 작은 값을 찾아 현재 인덱스와 자리를 바꿔준다. 즉, 맨 앞 인덱스부터 작은 수대로 채워 정렬하는 것(최소 선택 정렬), 반대는 최대 선택 정렬이다. 삽입 정렬(Insertion Sort) 공간복잡도 O(N) / 시간 복잡도 O(N^2), 최선의 경우(이미 정렬돼 있는 경우는 한번 밖에 비교하지 않아서) O(N) 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장, 비교 인덱스를 현재 인덱스 -1로 시작해서 -1씩 해가며 요소를 비교하고 적절한 위치를 찾아 삽입된다. 즉, 두 번째 요소는 첫 번째 요소와 비교. 세 번째 -> 두 번..
![[OS] 프로세스와 스레드 동기화](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbzVPgM%2FbtqOUkbGgLm%2FKbfLFwLkyAiRFrpGAefZh0%2Fimg.png)
[OS] 프로세스와 스레드 동기화
✨프로세스 동기화 : 하나의 자원을 한 시점에 하나의 프로세스만이 접근 ✨스레드 동기화 : 하나의 코드 블록 또는 메소드를 한 시점에 하나의 스레드만이 접근 🟠한 스레드의 특정 작업이 끝나기 전까지 다른 스레드의 방해를 받지 않도록 하는 것이 필요함(데이터 일관성 유지를 위해) 그래서 도입된 개념이 바로 임계 영역과 잠금(락, lock)이다. 🟠공유 데이터를 사용하는 코드 영역을 임계 영역으로 정해놓고, 공유 데이터(객체)가 가지고 있는 락을 획득한 단 하나의 스레드만이 해당 영역 내의 코드를 수행할 수 있게 한다. 그리고 해당 스레드가 임계 영역 내의 모든 코드를 수행하고 벗어나서 락을 반납해야지만 다른 스레드가 반납된 락을 획득하여 임계영역의 코드를 수행할 수 있게 된다. 🟠이처럼 한 스레드가 진행 ..
![[OS] 컨텍스트 스위칭(문맥교환Context Switching)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FlPkJh%2FbtqO0ePd7Kt%2FGIuFd6eY37BicjZtNUkqQk%2Fimg.png)
[OS] 컨텍스트 스위칭(문맥교환Context Switching)
🎂 컨텍스트 스위칭(context switching)이란? CPU가 어떤 프로세스를 실행하고 있는 상태에서 인터럽트에 의해 다음 우선 순위를 가진 프로세스가 실행되어야 할 때 기존의 프로세스 정보들은 PCB에 저장하고 다음 프로세스의 정보를 PCB에서 가져와 교체하는 작업을 컨텍스트 스위칭이라 한다. 이러한 컨텍스트 스위칭을 통해 우리는 멀티 프로세싱, 멀티 스레딩 운영이 가능하다 ! 컨텍스트 스위칭은 다음과 같은 상황에서 일어난다. I/O interrupt CPU 사용시간 만료 자식 프로세스 Fork 이러한 컨텍스트 스위칭이 일어날 때 다음번 프로세스는 스케줄러가 결정하게 된다. 즉, 컨텍스트 스위칭을 하는 주체는 스케줄러이다. 단점 : PCB를 저장하고 가져올때는 CPU가 아무런 일도 하지 못하게 된..
![[OS] 프로세스와 스레드](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbNpvME%2FbtqOxrDeWZG%2FjYHb0bLZNkerbNziHWHw2k%2Fimg.png)
[OS] 프로세스와 스레드
💫 간단 개념 💬 프로세스(Process) 현재 실행중인 프로그램이며, 운영체제로부터 고유 공간과 자원을 할당 받아 실행되는 작업 단위 💬 스레드(Thread) 해당 프로세스 안에서의 작업 흐름을 보여주는 실행 단위, 한 프로세스 내 스레드들 간 메모리를 공유한다. 💫 주요 특징 💬 프로세스 운영체제로부터 고유의 주소 공간과 자원을 할당 받아 실행 CODE, DATA, HEAP, STACK 구조로 이루어져 있음 다른 프로세스의 영향을 받지 않고 독립적으로 실행 과거에는 하나의 프로세스만 실행할 수 있었지만, 지금은 병렬 처리하는 '멀티 프로세스(멀티 태스킹)' 가능 💬 스레드(Thread) 한 프로세스 내에서 여러 스레드를 동시에 실행 가능 -> 바로 '멀티 스레드' 스택은 고유하게 할당 받지만 그 외 ..
![[OS] 운영체제(Operating System)의 개념](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb4GYTF%2FbtqOxrXheAP%2FMGoSGSDqqXSDfGSespTK0k%2Fimg.png)
[OS] 운영체제(Operating System)의 개념
💫운영체제란? 하드웨어를 관리하고, 응용 프로그램과 하드웨어 사이에서 인터페이스 역할을 하는 시스템 소프트웨어다. 시스템의 자원 및 동작을 관리한다. 더 쉽게 말하자면, 컴퓨터의 복잡한 하드웨어를 잘 모르더라도 컴퓨터를 사용하고 프로그램을 만들 수 있도록 지원해주는 소프트웨어다. 💫운영체제의 사용 목적 컴퓨터 자원을 더 효율적으로 사용하게끔 도와준다! 운영체제를 사용하는 이유는 처리능력 향상, 사용가능도 향상, 신뢰도 향상, 응답시간 단축하기 위함이다. 처리능력(Throughput) 시스템의 생산성을 나타내는 단위, 일정 시간 내에 시스템이 처리하는 일의 양 응답시간(Turn Around Time) 시스템에 작업을 의뢰한 시간부터 처리가 완료될 떄까지 걸린 시간 사용가능도(Availability) 시스템..
![[네트워크] HTTP 개념/ 특성 / 메소드 / 상태코드](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fk9392%2FbtqLD0npgcv%2FM9Ph1s42FKyESHIW5HiIaK%2Fimg.png)
[네트워크] HTTP 개념/ 특성 / 메소드 / 상태코드
💫 HTTP란? 👉 HTTP(Hyper Text Transfer Protocol)는 인터넷에서 데이터를 주고 받을 수 있는 통신규약(프로토콜!) HTTP는 클라이언트와 서버 사이에 이루어지는 요청/응답(request/response) 프로토콜이다. 💫 HTTP 특성 👉 가장 대표적인 특성은 2가지 비연결성, 무상태 💬 비연결성(Connectionless) : 클라이언트(브라우저)와 서버가 연결된 후, 클라이언트 요청에 대해 서버가 응답을 마치면 연결을 끊는 특성 💬 무상태(Stateless) : HTTP의 비연결성으로 인해 서버가 클라이언트를 식별할 수 없는 특성. 각각의 요청을 독립적인 트랜잭션으로 취급 장점 단점 비연결성(Connectionless) HTTP는 인터넷 상에서 불특정 다수의 통신 환경을..
![[네트워크] 세션과 쿠키의 차이](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FrBaUu%2FbtqLyLqjJFU%2FgWWdomGyHXnckJ2ltJBuY0%2Fimg.png)
[네트워크] 세션과 쿠키의 차이
*세션과 쿠키의 차이점은 맨 아래에 💫왜 쿠키와 세션을 사용할까? 👉 기본적으로 HTTP 특성으로 인한 문제를 해결하기 위해서 사용하는데 즉, 클라이언트 인증을 유지하기 위해 사용한다. 쇼핑몰의 예를 들어 보자. 쿠키와 세션을 사용하지 않으면 장바구니에 물품을 담은 경우 새로고침 시 장바구니가 초기화 되어 사용자가 불편을 겪게 된다. 마찬가지로 페이지를 이동할 때마다 로그인을 계속 해야 하는 불편함이 생기게 된다. 이유는 서버가 클라이언트(브라우저)가 누구인지 기억하지 않기 때문인데, 따라서 쿠키와 세션을 사용해 서버가 클라이언트를 기억할 수 있는 것이다. 💫HTTP 프로토콜의 특성 그렇다면 HTTP 프로토콜의 어떤 특징 때문에 쿠키와 세션이 필요한지 알아보자 👇 Connectionless : 클라이언트..
![[네트워크] 프로토콜의 개념 / 특징 / 요소 / 종류](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FkFP0N%2FbtqLscbrc0v%2F1alpaqo0gaFtk7y9FC8dGK%2Fimg.webp)
[네트워크] 프로토콜의 개념 / 특징 / 요소 / 종류
💫 프로토콜이란? 👉 서로 다른 시스템 및 기기 간 데이터 교환을 원활히 하기 위한 표준화된 통신규약 기기 간 통신은 교환되는 데이터 형식에 대해 상호 협의를 요구하기 때문에 프로토콜이 필요한 것이며, 공통의 데이터 교환 방법이나 순서에 대해 정의한 약속, 규칙 체계를 의미한다. 따라서 동일한 프로토콜을 사용하면 기종 및 프로그램이 다르더라도 컴퓨터간 상호 통신이 가능하다. 따라서 이기종 간 정보 통신을 하기 위해 표준 프로토콜을 채택하여 통신망을 구축해야 한다. 💫 프로토콜의 기본 요소 👉 기본 요소는 크게 구문, 의미, 타이밍 세 가지가 있다. -> '구의타' 기본요소 설명 구문(Syntax) 송수신 데이터 형식, 코딩, 신호 레벨 등 규정 의미(Semantic) 제어 정보로 조정과 에러 처리를 위한..
![[DB] 정규화 / 반정규화 / 함수적 종속성](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc9RAnw%2FbtqK7bxafGS%2Fq4hN3rUgEPr1KTPOHk58N1%2Fimg.png)
[DB] 정규화 / 반정규화 / 함수적 종속성
🎇 함수적 종속성(Functional Dependency) 정규화를 수행하기 위해 속성들 간의 관련성을 파악해야 하는데, 속성들 간의 관련성을 함수적 종속성이라고 한다. 일반적으로 하나의 릴레이션에는 하나의 함수적 종속성만이 존재하도록 정규화를 하게 된다. A -> B : A는 결정자 B는 종속자 🔶부분 함수적 종속 속성집합 B가 속성집합A의 전체가 아닌 일부분에도 함수적으로 종속됨을 의미한다. 🔶완전 함수적 종속 속성집합B가 속성집합A 전체에 대해서만 함수적으로 종속된 경우를 의마한다. 일반적으로 함수적 종속성은 완전함수종속을 의미한다. 🎇데이터베이스 정규화 데이터베이스에 삽입이상, 갱신이상, 삭제이상 등 이상현상이 발생하지 않기 위해서는 정규화 과정이 꼭 필요하다 🔶정규화(Normalization) ..