✅ 1. 기본사항(1) 트리의 정의트리의 종류: 트리를 기반으로 하는 여러가지 규칙이 추가된 다양한 트리가 존재함.트리: 사이클이 없는 단순 연결 그래프를 트리(Tree) 라고 함.단순 연결 그래프: 단순 그래프(루프, 병렬변이 존재하지 않는 그래프) + 연결 그래프(오직 하나의 연결 성분만 가지는 그래프) 를 합친 그래프를 단순 연결 그래프로 볼 수 있음.즉, 단순 연결 그래프 + 사이클이 없으면 트리라고 볼 수 있음.또한, Trivial tree(꼭지점 하나만 존재하는 트리), Empty tree(꼭지점 하나도 없는 비어있는 트리), Forest(한 개 이상의 트리로 구성된 그래프) 와 같은 것도 트리로 정의를 함.TIP: Forest 는 트리들이 여러개 존재하는 그래프를 의미할 수 있음.트리 예제:..

✅ 1. 그래프의 탐색(1) 평면 그래프평면 그래프: 그래프의 모든 변(간선)이 서로 교차하지 않게 그릴 수 있는 그래프를 평면 그래프라고 함.평면 그래프가 아닌 예시: 완전 그래프, 완전이분그래프 등은 변(간선)이 교차하는 그래프이기 때문에 평면 그래프가 아님.평면 그래프의 예시(1): 3-정규그래프는 평면 그래프로 변(간선)이 교차하지 않음. 또한, K4(완전그래프)와 동일한 완전 그래프로도 볼 수 있기 때문에 K4 또한 평면 그래프로 볼 수 있음.K4(완전그래프) 평면 그래프인 이유: 교차된 한 변(간선)을 밖으로 돌아가서 연결되도록 하면 평면 그래프이기 때문임.평면 그래프의 예시(2): K5(완전그래프) 에서 한 변(간선)을 제거한 그래프는 위와같이 평면 그래프로 만들 수 있음.(2) 오일러의 공..

✅ 1. 기본사항(1) 그래프 소개1737년 쾨니히스베르크 도시에 다리 건너기 문제를 당시 천재 수학자 오일러가 풀려고 접근함.이때, 오일러가 해당 문제를 풀 때, 본질만 남기고 다 지우는 추상적인 방법을 사용하는데, 결과로 나온 것이 그래프임.해당 그래프를 활용해서 문제를 보니, 답이 없는 문제임을 알아낼 수 있었음.(2) 주요 용어그래프 G = (V, E) 들로 구성이 되어있으며, V = 정점들의 집합, E = 간선들의 집합임.인접: 연결된 두 꼭지점은 서로 인접한다고 함.병렬 변: 두 꼭지점을 연결하는 변이 여러개 있는 경우를 의미함. ( ex: v1, v2 를 잇는 간선이 e1 뿐 아니라 e3.. 등 있을 때 )루프: 동일한 꼭지점을 연결하는 변을 의미하며, 꼭지점 v1에 동그랗게 다시 자신을 가..

✅ 1. 기본사항(1) 디지털 논리회로디지털 논리회로: 0과 1같은 이산적인(끊어진) 신호를 이용해 정보를 처리하는 전자 회로를 의미한다.쉽게 말해, 입력과 출력이 디지털 신호로 들어오거나 나오게 되는데, 이때 중간에서 디지털 논리회로가 이를 처리를 해주는데, 이것은 0과 1로만 표현되는 하나의 반도체 회로로 볼 수 있음.또한, 0과 1을 통해 논리회로로써 참(True)과 거짓(False)을 전기 신호로 표현해 논리 연산을 수행하는 구조임.즉, 논리회로 자체는 AND, OR, NOT, ... 으로 실제로 물리적으로 구현이 되어있음을 알 수 있음. (2) 기본 논리게이트 ( AND, OR, NOT )AND 게이트: 디지털 신호(0,1)가 입력값 X, Y에 들어오게 될 때, (0,0)인 경우 0(False)..

✅ 1. 기본사항(1) 함수란?함수: 어떤 입력값을 넣었을 때 규칙(f)에 따라 정확히 하나의 출력값을 대응시키는 관계를 의미함. ( 입력 하나 -> 출력 하나 )X에서 Y로의 함수 조건인 X의 모든 원소가 반드시 대응되어야 하고, 각 원소는 오직 하나의 관계만 가지는 조건을 만족하는 상태에서의 X에서 Y로의 관계는 관계 집합 f 는 X x Y (X, Y 곱집합)의 부분집합으로 볼 수 있음. 집합 관점 쉬운 설명: 집합 A, B가 있을때, A에서 B로의 관계 중 A의 모든 원소가 반드시 대응되어야 하고, 각 원소가 오직 하나의 값만 가지면 이것은 함수인 것임.(1) 함수 정의1: 집합 X의 모든 원소 x, 집합 Y의 임의의 원소 y에 대응되는 관계 집합을 f(x) = y 로 표현하기도 함.정의역: 함수에..

✅ 1. 기본사항(1) 곱집합곱집합: 집합 A와 B의 곱집합은 A X B 로 표현이 되며, A의 원소와 B의 원소의 모든 순서쌍들의 집합을 곱집합이라함.A = {1, 2}, B = {a, b}곱집합 = A X B = {(1, a), (1, b), (2, a), (2, b)}쉽게 말해, 두 집합 A와 B에서 공통된 원소를 찾는 것은 교집합이며, 곱집합은 두 집합의 원소들을 하나씩 뽑아 만들 수 있는 모든 가능한 '순서쌍'의 모임을 말합니다.(2) 관계예시: "x는 y보다 작다"라는 관계(R)조건: x 관계: 곱집합의 모든 원소 중 특정한 조건을 만족하는 순서쌍들만 골라낸 것을 관계라고 함.즉, 관계는 곱집합 내의 부분집합으로 곱집합이라는 전체 틀 안에서만 존재하며, 곱집합과 종속적인 관계를 가짐.학생집합 ..

✅ 1. 기본사항(0) 학습 목표(1) 논리학과 집합론논리합(OR): 합집합으로 표현이 가능하며, 둘 중 하나만 참, 둘 다 참인 경우 다 참으로 모두 포괄하는 합집합의 형태임.논리곱(AND): 교집합으로 표현이 가능하며, 둘 다 참인 경우에만 참으로 한정적으로 포괄하는 교집합의 형태임.이와 같이 논리학과 집합론의 관계를 알 수 있음.(2) 집합과 원소집합 자체의 용어는 무정의 용어이며, 무정의 용어는 정의 없이 사용하는 용어를 의미함.(3) 집합의 표기법S가 하나의 집합일 때 a ∈ S: a는 집합 S의 원소임을 나타냄.S가 하나의 집합일 때 b ∉ S: b는 집합 S의 원소가 아님을 나타냄.집합 S: 중괄호 { , } 로 표기를 함.원소나열법: S = {1, 2, 3} 형식으로 나열을 표기함.조건나열..

✅ 1. 벨만-포드 알고리즘(1) 벨만-포드 알고리즘이란?벨만-포드 알고리즘: 데이크스트라 알고리즘과 동일하게 단일 출발점으로 부터 모든 정점간의 최단 경로를 구하는 알고리즘임.단, 데이크스트라 알고리즘은 음의 가중치를 갖는 간선이 존재하는 경우에는 처리가 불가능 했지만, 벨만-포드 알고리즘은 음의 가중치를 갖는 간선이 존재하는 경우에도 처리가 가능한 알고리즘임.대신 조건은 음의 사이클이 없는 경우에 한해서 가능함.즉, 데이크스트라 알고리즘의 경우 가장 짧은 간선 하나를 기준으로 그 끝에 있는 정점을 선택하며 퍼져나가는데 반해, 벨만-포드 알고리즘은 그래프에 존재하는 모든 간선을 매 라운드마다 훑으며 최단 거리를 업데이트하기 때문에 음수 가중치를 발견하더라도 다음 라운드에서 반드시 그 값을 반영하게 되는..

✅ 1. 저장장치의 종류(1) 순차접근 저장장치순차접근 저장장치: 데이터를 순차적으로 읽거나 쓸 수 있는 저장장치를 의미하며, 테이프 장치의 유형으로 볼 수 있음.특징: 초기 접근시간이 굉장히 오래 걸리기 때문에 보통 대량의 데이터 백업용으로 사용이 됨.(2) 직접접근 저장장치직접접근 저장장치: 저장장치 내의 지정한 위치를 직접 찾아 데이터를 읽거나 쓸 수 있는 저장장치임.현대에는 직접접근 저장장치를 주로 쓰며 보통 자기 디스크, 광디스크, SSD가 대표적임.자기 디스크: 자성을 띤 디스크의 표면에 데이터를 쓰거나 읽는 방식의 저장장치 이며, 보통 하드디스크로 보면 됨.헤드가 디스크의 표면을 읽고, 여러 플래터에는 트랙과 섹터가 있으며, 플래터가 여러개 이기 때문에 동시에 읽기 가능함.광디스크: 디스크 ..

✅ 1. 장치의 개념(1) 컴퓨터 시스템의 구성기존의 내용들은 모두 CPU, 메모리 장치로써 프로세스 실행에 필수적인 장치들을 다룸.해당 파트에서 배우는 내용은 프로세스 실행에 필수적인 CPU, 메모리 외에 나머지 장치들에 대한 내용임.(2) 입출력장치 - 구분입출력 장치는 크게 전용장치, 공용장치, 가상장치 세 가지 범주로 나뉨.구분 기준: 장치의 기능적 특징과 장치관리자의 관리 방법에 따라 구분을 함.전용장치: 한 번에 하나의 프로세스에만 할당이 가능한 장치를 의미한다.예를들면, 프린터의 경우 여러 프로세스가 하나의 프린터에 프린팅을 하게 된다면, 겹치게 되어 원하는 프린팅의 결과를 얻을 수 없기 때문에 이러한 장치의 기능적 특징으로 인해 프린터는 전용장치로 구분 할 수 있음.전용장치 단점: 하나의 ..