오늘은 여기까지

1. 신장 트리 (Spanning Tree)그래프 내 모든 정점을 포함하는 트리다. 그래프의 최소 연결 부분이다.모든 정점이 연결되어 있음사이클이 존재하지 않음간선의 개수 = 정점의 개수 - 1DFS, BFS를 이용하여 그래프에서 Spanning Tree를 찾을 수 있다. 탐색 도중 사용한 간선만 모으면 된다.하나의 그래프는 여러 개의 Spanning Tree를 가질 수 있다.2. 최소 신장 트리, (Minimum Spanning Tree)Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리모든 정점이 연결되어 있음사이클이 존재하지 않음간선의 개수 = 정점의 개수 - 1간선들의 가중치 합이 최소그리디 알고리즘을 사용하는 대표적인 트리 형태의 자료구조3. MST 구현 방법3.1 크루스칼..

그리디 알고리즘문제 해결 과정에서 단계마다 눈앞에 최선의 선택을 하고, 선택은 번복하지 않는다.그리디 알고리즘이 최적해를 보장하려면?최적 부분 구조: 부분해를 푸는 과정이 최적해를 구하는 과정과 일치그리디 선택 속성: 선택 과정이 다른 과정에 영향을 주지 않음배낭 문제부분 배낭 문제짐을 쪼갤 수 있는 배낭 문제를 가정하자.배낭에 담을 수 있는 최대 무게가 존재하고, 무게와 가치가 다른 짐들이 있다. 이 짐들을 조합해서 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제를 배낭 문제라고 한다.부분 배낭 문제는 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘을 사용하면 된다.짐별로 무게당 가치를 구한다무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣는다배낭 용량이 짐 무게보다 크..

타입변환 서로 다른 데이터 타입끼리의 연산이 필요할 때, 변수의 데이터 타입을 바꿔주는 작업을 데이터 타입의 형변환(타입변환)이라고 한다.형변환에는 자동 형변환(Promotion) 과 강제 형변환(Casting) 이 있다. 다른말로 자동 형변환은 묵시적 타입 변환, 강제 형변환은 명시적 타입 변환이라고도 한다.  1. Promotion (자동 형변환)프로그램 실행 도중에 자동적으로 형변환(타입변환)이 일어나는 것을 말한다작은 데이터 타입에서 큰 데이터 타입으로 자동으로 변환데이터 손실의 위험이 없기 때문에 자동으로 수행된다변환 순서: byte → short → int → long → float → doublebyte byteValue = 10; int intValue = byteValue; // 자동으로..

C/C++에서는 개발자가 직접 사용하지 않는 객체의 메모리를 해제해주어야 한다. 하지만 JAVA에서는 JVM이 구성된 JRE가 제공되며, 그 구성 요소 중 하나인 Garbage Collection이 자동으로 사용하지 않는 객체를 파괴한다.GC를 해도 더이상 사용 가능한 메모리 영역이 없는데 계속 메모리를 할당하려고 하면, OutOfMemoryError가 발생하여 WAS가 다운될 수도 있다. 따라서 규모 있는 JAVA 애플리케이션을 효율적으로 개발하기 위해서는 GC에 대해 잘 알아야 한다.Garbage CollectionJVM의 메모리는 총 5가지 영역(class, stack, heap, native method, PC)으로 나뉘는데, GC는 힙 영역만 다룬다.GC는 객체의 접근 가능성(Reachabili..

PCB (Process Control Block)운영체제가 프로세스를 관리하기 위해 사용하는 자료구조이다.커널 주소 공간의 Data 영역 내 존재하며, 프로세스마다 1개씩 있다.OS가 관리상 사용하는 정보Process state, Process ID, 우선순위, scheduling informationCPU 수행 관련 하드웨어 값Program counter, registers메모리 관련Code, Data, Stack의 위치 정보파일 관련Program counter와 같은 context 정보는 CPU에 있는데 왜 PCB에 또 보관하는가? Context Switching을 위해 Context SwitchingCPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정이다. 예를 들어, 프로세스 A에서 B로 CPU..

프로세스의 문맥(context)프로세스 상태에 대한 모든 정보를 뜻한다.하드웨어 문맥Program Counter각종 register프로세스 주소 공간code, data, stack프로세스 관련 커널 자료구조PCBKernel stack프로세스의 상태 Running CPU를 잡고 instruction을 실행 중인 상태 Ready CPU를 기다리는 상태 (나머지 조건을 모두 만족하고) Blocked CPU를 주어도 당장 instruction을 수행할 수 없는 상태Process 자신이 요청한 event(e.g. IO)가 즉시 만족되지 않아 기다리는 상태예를 들어, 키보드 입력을 기다려야 하는 프로세스가 있다고 하자. 해당 프로세스는 Blocked 상태이므로 CPU를 주지 않는다. Ready queue에 있는 다..

TCP인터넷 프로토콜 스위트의 핵심 프로토콜 중 하나로, 어플리케이션 간 reliable, ordered and error-checked 데이터의 전송을 보장한다.연결 지향적: 통신 전에 연결을 설정하고 유지한다.신뢰성: 데이터 전송의 신뢰성을 보장한다. 손실된 패킷은 재전송한다.순서 보장: 데이터가 보낸 순서대로 수신된다.양방향 통신: 양방향으로 동시에 데이터를 주고받을 수 있다.바이트 스트림: 데이터를 연속된 바이트 스트림으로 처리한다.TCP 작동 방식 간단히sender, receiver 간 3-way handshake를 통해 연결을 설정한다.데이터를 패킷 단위로 쪼갠다.패킷에 순서를 부여한다.오류 없이 패킷이 전달되도록 한다. 손실된 패킷은 재전송한다.흐름제어를 통해 데이터 전송 속도를 조절한다.흐..