나다김강니

네트워크 계층네트워크에는 다양한 기기 간 통신을 위해 약속된 구조가 있다.  OSI 7계층OSI 7계층이란 국제 표준화 기구에서 네트워크 통신이 이뤄지는 과정을 7단계로 나눈 네트워크 표준 모델이다. 📤 송신부 각 계층은 독립적이며 데이터를 송신할 때 각 계층에서 필요한 정보를 추가해 데이터를 가공한다. 이때 제어 정보를 담은 헤더나 트레일러가 붙는데, 이 과정을 데이터 캡슐화라고한다.응용 계층 -> 물리 계층 📥 수신부  물리 계층부터 응용계층까지 거치며 받은 데이터에서 헤더와 트레일러를 분석해 제거하는 역캡슐화를 진행한다. 이 과정에서 각 계층은 필요한 제어 정보를 얻는다.  프로토콜  통신 규약. 즉, 데이터를 송수신하기 위해 정한 규칙을 의미한다.7계층(응용 계층)HTTP, FTP 등의 프로토..

최소 신장 트리(MST)최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리사이클이 포함되면 가중치의 합이 최소가 될 수 없다. -> 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.최소 신장 트리 대표 알고리즘 : 크루스칼, 프림 💡 최소 신장 트리의 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기데이터를 노드가 아닌 에지 중심으로 저장한다. 그래서 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.유니온 파인드 리스트도 함께 초기화한다. 자신의 인덱스 값으로 초기화한다.  2. 그래프 데이터를 가중치 기준으로 정렬한다.에지 리스트에 담긴 그래프 데이터를 가중치 기준으..

플로이드-워셜그래프에서 최단 거리를 구하는 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)모든 노드 간에 최단 경로 탐색 -> 시작 노드가 따로 정해져있지 않다.음수 가중치 에지가 있어도 수행 가능하다. 다만, 사이클이 있으면 안된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.시간 복잡도는 O(V3)   노드가 1000개이면 시간초과가 일어날 확률이 높다.💡  플로이드-워셜 핵심 이론A노드에서 B노드까지 최단 경로를 구했다고 가졍했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로 🔍 도출한 플로이드-워셜 점화식     D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 1. 리스트를 선언하고 초기화하기D[S][E]는 노드 S에서..

벨만-포드그래프에서 최단 거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 - 다익스트라와 같음음수 가중치 에지가 있어도 수행이 가능하다.전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음시간복잡도는 O(VE) 💡  벨만-포드 알고리즘의 핵심 이론1. 에지리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기* 에지리스트는 일반적으로 노드 변수 2개(start, end)와 가중치 변수로 구성되어있다.  2. 모든 에지를 확인해 정답 리스트 업데이트하기최단 거리 리스트에서 업데이트 반복 횟수는 노드-1 개이다.음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다. 모든 에지 E = (s, e, w)에서 다음 조건을 ..

다익스트라그래프에서 최단 거리를 구하는 알고리즘출발 노드와 모든 노드간의 최단 거리 검색제약 조건 : 에지는 모두 양수시간 복잡도는 O(ElogV)   V: 노드 수, E: 에지 수 💡  다익스트라 알고리즘의 핵심 이론1. 인접리스트로 그래프 구현하기  2. 최단거리 배열 초기화하기  3. 값이 가장 작은 노드 고르기  4. 최단 거리 배열 업데이트 하기현재 선택된 노드의 에지들을 탐색하고 업데이트-> Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값) 5. 과정 3~4를 반복해 최단 거리 배열 완성하기과정 4에서 이미 선택됐던 노드를 다시 방문하지 않기위해 방문 배열(visited)을 만든다. ☝🏻  다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 ..

1.6.1 캐시 메모리와 지역성캐시 메모리CPU와 메인 메모리(RAM) 간에 데이터 접근 시 속도 차이를 줄이기 위해 사용한다.CPU에서 자주 사용하는 데이터를 캐시 메모리에 따로 저장해두면 CPU가 해당 데이터에 더욱 빠르게 접근할 수 있다. 💡 캐시 메모리에는 어떤 데이터를 저장할까❓❓캐시 메모리에 저장할 데이터는 지역성을 바탕으로 결정한다. 📖 지역성CPU가 자주 참조하는 데이터가 고르게 분포되지 않고 특정 부분에 몰려 있는 것시간 지역성 : 최근 참조한 내용을 다시 참조할 가능성이 높다.공간 지역성 : 실제 참조한 주소 근처의 내용을 참조할 가능성이 높다 1.6.2 캐시 메모리의 매핑 방식캐시 메모리와 메인 메모리를 매핑하는 방식직접 매핑(direct mapping)메인 메모리를 일정한 크기로..

1.5 가상 메모리사용자가 프로그램을 실행하면 OS는 디스크에 저장된 데이터를 메모리로 로드한다.하지만 메모리 공간은 한정되어 있고, 사용자는 동시에 여러 프로그램을 실행하고 싶어한다.가상메모리는 이런 메모리 한계를 극복하는 방법이다.  1.5.1 가상 메모리란 ⭐️⭐️⭐️가상 메모리란 프로세스의 일부만 메모리에 로드하고, 나머지는 디스크에 둔 상태로 프로세스를 실행하는 방식이다.-> 프로세스 전체가 메모리에 올라오지 않아도 프로세스를 실행하는 데 문제가 없다는 점에서 착안됐다. 💡 가상 메모리의 장점프로그램이 메모리 크기에 대한 제약을 덜 받는다프로그램 크기가 실제 RAM보다 커도 실행이 가능하다CPU이용률과 처리율을 높인다.(동시에 많은 프로그램을 실행하므로)필요한 영역만 메모리에 로드해 스와핑 횟..

1.4 메모리 관리 전략다수의 프로세스를 실행하려면 한정된 메모리 공간에 많은 프로세스를 로드할 수 있어야 한다.메모리 공간을 더 효율적으로 활용하기 위한 여러 방안이 있다.  1.4.1 논리 메모리와 물리 메모리CPU가 프로세스를 처리할 때 보는 주소 값과 실제 메모리의 주소 값은 다르다.프로세스가 보는 메모리 영역을 논리 메모리 영역, 가상 메모리 영역이라고 한다.실제로 사용되는 메모리 영역(RAM)을 물리 메모리 영역이라고 한다.CPU가 프로세스를 실행하며 보는 주소 값을 논리 주소, 가상 주소라고 한다.실제 메모리에서 사용하는 주소는 물리 주소라고 한다.💡 메모리 관리 장치(MMU)CPU가 프로세스를 실행할 때 사용하는 주소 값과 실제 주소 값이 다르므로 논리 주소를 물리 주소로 변환해주는 하드..

1.3 스케줄링멀티 프로세스 환경에서는 여러 프로세스가 모두 실행되어야 하지만, CPU자원은 한정적이다.그래서 스케줄링을 통해 모든 프로세스를 공평하게 실행해 한정된 자원을 효율적으로 활용하는 것이 OS의 주요 목적이다.  1.3.1 스케줄링의 목적스케줄링의 주요 목적은 멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하는 것 💡  스케줄링의 목적 5가지공평성특정 프로세스가 실행되지 않는 경우가 없도록 모든 프로세스가 공평하게 실행되어야 한다.효율성자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링해야 한다.안정성높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링한다.반응 시간 보장일정 시간 내에 응답할 수 있도록 스케줄링한다. 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으..

1.2.7 프로세스 동기화경쟁 상태여러 프로세스 또는 스레드에서 하나의 공유자원에 동시에 접근하여 경쟁하는 상태 💡  너무 많은 우유 문제 - 프로세스 동기화가 필요하다!!엄마가 냉장고에 우유 없는 걸 확인엄마 우유 사러감엄마 우유 사고 돌아오는 길에 아빠도 냉장고에 우유 없는 거 확인아빠 우유 사러감우유 2개 됨 -> 의도하지않은 결과  임계 영역공유 자원에 접근할 수 있고 접근 순서에 따라 결과가 달라지는 코드 영역* 우유문제에서 냉장고에 우유가 있는지 없는지 판단하고 우유를 추가하는 부분이 이에 해당한다.  ☝🏻 임계 영역에서 경쟁상태를 방지하기 위해 프로세스 동기화가 필요하다. 💡  임계 영역에 여러 접근이 동시에 발생하는 것을 방지하는 3가지 방법상호 배제 기법(mutual exclusi..