Hayden's Archive

※ 참고 : 한국방송통신대학교 정보통신망 강의 1강 1. 컴퓨터와 통신 (1) 컴퓨터와 통신 컴퓨터가 하는 일 = 데이터를 처리하는 것. 그래서 영어로 컴퓨터를 EDPS(Electronic Data Processing System)라고도 함. 컴퓨터는 데이터를 입력으로 받아들이고 출력으로 정보를 출력함. 온라인으로 연결되지 않고 나 혼자서 Stand Alone으로만 쓴다면 통신이 불필요할 것. 하지만 다른 컴퓨터와 Computing Power 또는 Computing Resource를 공유하기 위해 통신망이 생기게 됨. (2) 통신 기술과 데이터 처리 기술 단말기가 프린터를 이용하거나 디스크 장치를 중앙처리장치(입출력 채널)를 통해서 Read/Write 하기 위해서는 컴퓨터가 가지고 있는 데이터 처리 기술..

참고 : 방통대 자료구조 강의 트리 검색의 편리함 논리적 계층 계급적 특성 트리의 구성 노드 : 트리의 항목 / 트리에 저장되는 데이터(값+포인터)의 묶음 부모노드-자식노드 : 상하 계층구조가 있고 링크나 포인터를 통해 직접적으로 연결된 노드로서 상위계층의 부모노드와 하위계층의 자식노드를 뜻함 (바로 위가 아니면 조상과 자손) 루트노드 : 트리의 최상위 노드(부모가 없는 노드) 서브트리 : 부모 노드를 삭제하면 생기는 트리들 리프노드 : 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드 진입/진출 차수 루트 노드 : 진입차수 = 0 (부모가 없음) 루트를 제외한 모든 노드의 진입 차수 : 1 리프 노드 : 진출차수 = 0 (자식이 없음) 트리의 레벨 루트를 시작으로 트리를 정의하고 접근..

* 다이나믹 프로그래밍 = 동적 계획법 - 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 * 큰 문제를 작은 문제로 나누는 알고리즘 1) 다이나믹 프로그래밍(Dynamic Programming) 2) 분할 정복(Divide & Conquer = D&C) -> 공통점 : 큰 문제를 작은 문제 여러개로 나눠서 푼다. -> 차이점 : 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눴을 때 중복이 가능 / 분할 정복은 큰 문제를 작은 문제로 여러개로 나눴을 때 절대로 중복이 일어나지 않는다. * 다이나믹으로 풀 수 있는 문제의 속성 1) Overlapping Subproblem : 겹치는 부분(작은) 문제 (큰 문제를 여러개의 작은 문제로 나눈 다음 다시 그 답을 이용해서 원래 문제를 푼다. 이 작은 문제들이 중..

* 나머지 연산(Modular Arthimetic) - 컴퓨터의 정수는 저장 범위가 한정적 -> 그래서 답을 M으로 나눈 결과를 출력하라는 문제가 종종 나옴 - (A+B)%C 와 (A%C+B%C)%C 는 같고, (A*B)%C 와 (A%C*B %C)%C 는 같다 * 최대공약수(Greatest Common Drivisor = GCD) // 관련 알고리즘 : https://hayden-archive.tistory.com/279 - 서로소(Coprime) : 최대공약수가 1인 두 수 - 최대공약수를 구하는 가장 빠른 방법 -> 유클리드 호제법(Euclidean algorithm) 이용 - 유클리드 호제법 : a를 b로 나눈 나머지를 r이라고 할 때 GCD(a,b) = GCD(b,r) - 이 때 r이 0이면 그 ..

참고 : 방통대 김진욱 교수 운영체제 강의 교착상태(Deadlock) : 관련된 모든 프로세스가 무한히 대기 기아상태(Starvation) : 관련된 일부 프로세스가 지속적으로 대기 * 교착상태(Deadlock)의 필요조건 (아래 4가지가 동시에 만족될 경우 교착상태가 일어날 수 있음) 1. 상호배제 조건 - 공유할 수 없고 동시에 쓸 수 없는 자원일 때 발생함. - 하나의 자원이 있고 프로세스 A가 쓰고 있으면 프로세스 B는 쓰지 못하고 기다려야 함. 2. 점유 대기 조건 - 점유하고 있는 상태로 기다린다. - 프로세스 A가 자원 a를 할당받아 배타적으로 점유하고 있는데 프로세스 B가 점유하고 있는 자원 b가 해제되기를 기다림 3. 비선점 조건 - 선점은 자원을 빼앗아올 수 있는 건데, 비선점은 자원을..

- 알고리즘 문제의 효율성 : 1. 수행 시간 / 2. 사용한 메모리 / 3. 코드의 길이 - 효율성 중에서 수행 시간이 가장 중요하다. 보통 메모리는 넉넉하므로 걱정할 필요가 없다. 시간 안에 풀었다면 메모리 부족을 겪지 않는다. - 보통 배열이 가장 많은 공간을 사용한다. 배열의 크기가 크면 시간 초과를 받는 경우가 많다. - 불필요한 공간 없으면 보통 공간 복잡도(Space Complexity)는 신경 안 써도 된다. - 시간 복잡도(Time Complexity)를 통해 작성한 코드의 시간을 예상할 수 있다. - 99%의 케이스가 0.01초가 걸린다고 해도 1%의 케이스가 100초가 걸린다면 그 경우 시간 복잡도는 100초가 걸리는 셈이다. - 시간 복잡도를 계산할 때 보통 빅오 표기법(Big O ..