컴퓨터학개론(Computer Science illuminated;Nell Dale & John Lewis) 1장~4장 정리

• 컴퓨팅 시스템
• 전자계산기, 컴퓨팅 시스템
  • 1940 첫 출현

연도 하드웨어 소프트웨어

1951	연산	진공관
기억	자기드럼, 자기테이프
1959	연산	트랜지스터
기억	자기디스크, 자기코어
1965	연산	IC 집적회로:
cpu, DRAM
기억	트랜지스터 이용
-휴대용: HDD, 플로피디스크
입출력	terminal, 키보드+화면
1971
1990

• computing machine 출현(1947) - 컴퓨터(HW) 컴퓨팅시스템(HW+SW) 의미 - 최초의 범용(다양한 용도로 쓰이는)기계
• 데이터 처리
  • 기억보조장치(MEMEX) 마이크로필름(미니레코드판) - 아날로그 컴퓨터
  • 최근 경향: 컴퓨터는 데이터 중심 관점 - data -> info 변환, 가공하는 기기 - 데이터 사이언스 탄생 - 1993 유선전화 디지털화, 2002 디지털 데이터 비율 상승 등 데이터 과학 필요성 대두
  • 컴퓨팅 시스템 = programmable data processor
• 네트워크의 발달
  • 커뮤니케이터 ex) 스마트폰
  • 도입과정 인터넷 - 1960군용->민간일부, 1983 군용망 분리, 사용 world wide web - 실험자료 공유목적(1989), 링크간 연결 cloud computing -메모리 렌탈 서비스 2006
• 학문의 탄생
  • 컴퓨터 과학 - 출현배경 프로그래머만 사용 – 시스템/앱 프로그래머 분리 순수 사용자 출현 - 자동화 - 수학+과학+공학
  • 데이터 과학: 데이터에서 얻기위해 여러 방법 사용 - 데이터 마이닝, 빅데이터
  • 융합분야 컴퓨터에 기초해 일반 학문에 융합 - 바이오 정보학/분자역학/경제 예측
• 컴퓨터 시스템 구성
  • 전문용어 Jargon
  • 같은 단어라도 다른 의미로 쓰이는 경우 多
  • 단위 K M G T P 등 시간: 10진수, 메모리: 2진수
  • 추상화
  • 설명 용이
  • 시스템의 계층구조
  • 컴퓨터 시스템의 구성
  • 4대 구성요소 HW SW Data User
  • 입출력 장치
  • 입출력 장치
  • 입출력
• 컴퓨터의 역사
• 컴퓨터 이전
  • 계산도구 : 주판, 기계식 계산기
  • 저장장치 : 자동베틀, 천공카드
  • 해석기관: 찰스배비지(설계) Ada 최초 프로그램
  • 전자식 컴퓨터 앨런튜링, 에니악

1. 컴퓨터의 분류

• 메인프레임 컴퓨터
  • 중앙 집중 처리
  • 클라이언트-서버 모델 (server수행/client요청)
  • 대기업에서 사용하는 대용량 컴퓨터
  • IBM 절반 이상 점유 IBM
  • 1911설립
  • IBM704: 최초 대량생산
  • FORTRAN: 최초 프로그래밍언어, 컴파일러
  • IBM system/360: 운영체제
  • IBM-PC: 레노버 매각, 최초 컴퓨터X
• 슈퍼 컴퓨터
  • 초당 1015번 Peta급 연산
  • CPU/GPU 1000개 이상 병렬처리
  • 용도: 기상대, 과학 계산, 시뮬레이션
  • 기업: 크레이 크레이 - 원통형 CPU 병렬처리 - 액체질소 냉각시스템 개발 - HP 현재 소유
• 미니 컴퓨터
  • 메인프레임보다 낮은 중간 정도 성능
  • 소규모 회사/업체의 작업용
  • 마이크로 컴퓨터: 더 작은 경우
  • 메인프레임보다 자유로운 환경 제공 ->해커등장 -IBM과 반대
  • 기업: DEC DEC - 미니 컴퓨터 시장 개척 - PDP-1 MIT 해킹 그룹 인수 (1959) - PDP-7 Unix 최초 버전 실행 - PDP-11 C언어 최초 실행 (1970) - 슈퍼미니컴 시장 진출 -> 파산(1998)
• PC, 워크스테이션
  • IBM+MS Mac 경쟁 IBM : 공개전략 -> MS SW 독점 Mac : 비공개전략, 마우스 그래픽 최초 도입
  • 워크스테이션: 성능 강화 PC 복잡한계산, 애니메이션 제작용 현재는 PC와 구분 X 기업: 썬 마이크로시스템
  • 휴대용 컴퓨터(노트북, LAPTOP)
  • 초기 태블릿PC - 노트북 기반, 비싸고 성능저하
• PDA, 스마트폰
  • PDA: 개인용 디지털 보조기 ex) 팜 파일럿 – 전자 메모장, 성공
  • 휴대폰: 전화 목적 임베디드 시스템 - PDA정도 성능, 점차 성능 강화
  • 스마트폰: 향상된 컴퓨팅 휴대폰 - Simon 최초 IBM 스마트폰 - 아이폰2007, 안드로이드폰2008 - 애플(폐쇄) 구글(공개)
  • 태블릿 컴퓨터: 크기를 키운 스마트폰
• 게임기, 핑거팁 컴퓨터
  • 게임기 pc와 구조 비슷, 게임용 컴퓨터
  • 핑거팁 컴퓨터 라즈베리파이: 25달러, 작은 pc 아두이노: 5달러, 임베디드 개발용 보드 - 외부 센서 제어에 유리 - 전자제어 입문용, 교육용

1. PC 구조

• 기본 지식 보드 내부구조 전원공급장치
• 메인보드와 슬롯
  • 메인보드=마더보드 daughter board–확장 보드(장착,전원연결 필요) 슬롯: PCI, AGP, PCI express
• CPU와 메모리
  • CPU
  • 메인메모리 - address에 저장된 value
  • RAM: 휘발성 메모리 ex) DRAM 多
  • ROM: 비휘발성 메모리 ex) 메인보드의 start-up 프로그램 bios chip
  • 내부 bus: CPU 메모리 사이 통로
  • 캐시 메모리: 반복사용되는 정보 저장 빠른 실행 가능, 보통 CPU 내장
• 모니터와 그래픽카드
  • 화면해상도
  • 모니터 연결방법 메인보드 내장그래픽 - 중급 그래픽 성능, 사무용, DVI-D단자 2. GPU – 그래픽 카드 내부 장착 칩 - 엔비디아 GeForce, AMD Radeon
  • GPU 커넥터 - HDMI(영상,음성,제어 모두) > DVI(영상신호만)

1. PC 저장장치
   • 자기저장장치

• 종류 : 하드디스크, 플로피디스크, 자기테이프
• HDD: hard disc driver - 1TB 이상 대용량
• HDD 포맷팅 - 트랙/원형섹터/ 섹터(1K ~ 8K byte 단위 read /write 기본 단위, 1 byte 만 고쳐도 1섹터씩 수정)
• HDD 용량
  • 광학저장장치
• 레이저 광학기술(CD,DVD,blu-ray) land: 평평 / pit: 레이저로 태움
• CD: 74분 650~MB
• DVD: 4.7~GB
• blu-ray: 25GB 필요성 낮아짐
  • 연결단자와 케이블
• SATA: 하드디스크 접속 규격
• Parallel Ports: 8비트 병렬 전송 usb
• Serial Ports: 1비트 직렬전송, 저비용
• USB : 케이블 통일 전원불필요
  • 플래시메모리
• 플래시메모리 기술: 비휘발성 장점: 작고 충격에 강함, 하드디스크보다 빠른 속도 단점: 수명 짧음, 큰 단위로 지움(읽을땐 괜찮음) - SD카드 USB SSD
• SD 카드 스마트폰, 디카, gps 기억장치
• USB 플래시 드라이브: 이동형 저장장치
• SSD 빠르고 조용하고 작고 전력소모적음, 비쌈 -STAT 연결 / 메인보드 연결

1. 데이터의 2진수 표현
   • 2진수 표현
   • 가장 간단한 데이터이기 2진수를 사용함(yes ,no)
   • 스위치, 캐퍼시터(충전, 방전)
   • 캐퍼시터 8개로 8개까지 저장 가능 너무 많이 필요해서 2진법 도입
   • 비트: 2진수 한 자리를 의미
   • 바이트: 8비트 읽고 쓰는 최소 단위 (영어 문자 1개)
   • 256까지 표현 가능
   • 모든 데이터 2진수 형태 저장 - 숫자, 문자, 이미지, 신호데이터 등 해석 가능
   • 8진수, 16진수의 사용
   • 2,10진수 단점: 32비트짜리 매번 바꿔 해석 힘들다
   • 8진수: 2진수 3자리씩 표기
   • 16진수; 2진수 4자리씩 표기
   • 사칙연산-자리 올림 자주 발생
   • 표현방법 2진수 0b, 8진수 0, 16진수 0x를 앞에 붙임
   • zero 헷갈려서 slashed zero 도입
   • 아날로그와 디지털
   • 아날로그: 연속적인 물리량 디지털: 수치로 표현
   • 디지털화 A/D컨버터 마이크 D/A변환기 스피커
   • 디지털 데이터의 장점 - 통신 잡음에 강함, 압축하기 좋음
2. 수치 데이터

• 자연수 표현 natural numbers
• 2진수 표기 0 포함, 1byte:255 2byte 65536까지
• 음수 표현
• 처음엔 처음 1bit을 부호로 해석 -계산이 복잡함, 0이 2개
• 2진수 음수 계산방법: 2의 보수 이용
• 오버플로우, 언더플로우 - 양수+양수/음수+음수 허용한계 벗어남
• 자연수 2k-1까지 표현 정수 -2k-1 ~ 2k-1-1 표현
• 실수 표현
• 고정 소수점 방식 - 가상의 소수점 가정 - 간단하지만 숫자 범위 작음
• 부동 소수점 방식 234 x 1056 = 1.234E56 32비트-소수점이하 6자리 64비트 소수점이하 13자리 정밀한 계산 요구되는 시점에 특별한 방법 쓰기도 함, 무한소수 표현 못함
• 양자 컴퓨터
• 전자가 아닌 양자를 사용 0이면서 1인 상태 표현 – 4가지 표현 가능qubit 2가지 동시 계산 가능

1. 텍스트 데이터

• 텍스트 데이터
• 문자를 2진수 코드로 저장
• 아스키코드 글자1개 –8비트
• word = 한꺼번에 처리하는 비트/바이트 수 *윈도우 프로그래밍에서만-(1word=2바이트)
• ASCII 코드
• 코드 표준을 정함 -> 아스키,유니코드
• 아스키 코드 7비트로 128자 지정, 첫 32개는 전송/제어 코드 *숫자2가 아닌 문자2를 보낼 땐 아스키코드 50임
• 확장 아스키 코드 8비트로 256자 지정-이때 8비트=1바이트 지정
• 유니코드 문자 집합
• 전 세계 모든 문자 다루는 표준 문자전산 처리방식
• 전 세계 문자 고유 코드 부여
• 문자 1개 = 4바이트
• 앞부분은 확장 아스키코드와 동일
• 앞부분 16bit(2바이트)에 집중 배치
• 표기법: U+(16진수) U+AC00 = 가
• 32비트 유니코드 42억개이지만 16비트에 집중
• 16비트로는 이미 문자 표현 불가능
• 현대 한글 모든 조합 11172자 고대 한글 1638750자
• 한자만 해도 국가별로 다름
• CJK 통합 한자(한자 통일+각 나라별)
• 유니코드 전송 방식
• 4바이트 코드-회사입장에서는 저장 용량 커짐 -가변 너비 문자 인코딩 등장 - 자주 사용 문자 1,2바이트로 사용
• UTF-8 미국/유렵 1바이트만 사용
• UTF-16 2바이트 사용해 한글/한자 해결 CJK 국가 선호
• 윈도우10에서 양쪽 모두 가능, 대부분 자동 감지
• 팬그램 알파벳/자모 다 나오는 font 테스트 문장

1. 오디오 데이터

• 오디오 데이터 2진수 변환과정 3가지
  1. 샘플링: 아날로그 신호 1초에 몇 번 추출? 8000Hz: 전화, 44100Hz: CD MPED-1 96000Hz: DVD 블루레이
  2. 양자화: 신호 크기 정밀도 ex) 8bit: 256단계, 16 bit: 65536단계
  3. 부호화: 양자화 값을 이진수로 변환 ex) 8000Hz * 8bits = 64000bps = 64kbps
• 예제: 채널1(모노) 채널2(스테레오) 양자화: 8비트 16비트 샘플링 22040Hz
• 보통 CD 스테레오 2바이트 44100Hz -> 1초에 176400바이트, 코덱으로 압축해야함
• 오디오 파일 포맷
  • 레이저 광학기술
  • CD
  • 포맷??
  • CD, MP3, FLAC
• 데이터 압축: 공간, 대역폭을 줄이는 작업
  • 비손실/무손실과 손실 압축 기법이 있음
  • 이미 압축된 MP3는 zip으로 또 압축해도 X
  • zip 비손실/ JPEG 세밀한 변형, 압축률 good
• 압축 기법
  • 비손실 3가지 기법: 키워드/런-렝쓰/허프만 인코딩
  • run-length encoding 반복되는 패턴은 flag 와 반복횟수를 쓰자 3바이트로 압축, 흑백 팩스, 이미지에서 사용

1. 이미지 데이터

• 이미지와 그래픽스
  • 이미지 저장방법(레스터 방식): 픽셀들 배열
  • 흑백 : 1픽셀 – 1비트
  • 그레이스케일 : 1픽셀 – 8비트 256단계(검정00~하양FF) 2비트, 4비트 거친 그레이 스케일 가능
  • 컬러 : 1픽셀 – 3원색 * 그레이스케일 = 3바이트 트루컬러24비트/RGBA32비트/딥컬러30비트
• 빛의 삼원색
  • RGB 가산색계, 0.0~1.0 값
  • 컬러 파렛트 웹 브라우저 표시 가능 색상
• RGBA와 CMYK
  • 투명도가 추가된 RGBA 0~255 쓰는 직관적 표현 방식 0~1.0 쓰는 고급 그래픽스 방식
  • 인쇄 cyan,magenta,yellow 감산 색계 실제로는 검은색 안 나와서 cmyk 모델 사용
• 해상도
  • pixel, color depth(1픽셀당 비트 수), 해상도
  • progressive scan
  • interlaced scan – 저비용, 홀수선 짝수선 번갈아

1. 그래픽스와 동영상 데이터

• 래스터 그래픽스 방식
  • BMP-압축x, 파일크기 커짐
  • GIF-비손실,인터넷용,컬러파렛트,애니메이션 가능
  • PNG-비손실,인터넷,32비트트루컬러,
  • JPEG – ISO 지정 압축 기법 보통 손실압축, 세밀한변형-압축률높임
• 벡터 그래픽스 방식
  • 장단점 수정하기 좋음, 확대O, 이미지에 부적합
  • 응용분야 SVG(2차원벡터그래픽) - 인터넷 자료 교환용 단순한 도형(아이콘,로고) 글꼴,
  • pdf(글꼴 처리 해야해서) - 포맷 공개
• 동영상 데이터
  • 코덱 - 손실압축
  • MPEG 1 CD 저장용 2 DVD 저장, 화상회의용 – MP3 나옴 4 가장 널리 쓰임
  • MPEG 압축 기법 공간 압축: JPEG처럼 프레임마다 압축 시간 압축: 프레임간 차이만 저장
  • I-frame 원본 P-frame I에서 바뀐부분 B-frame I,P의 양방향 차이 - 다만 역재생 어려움 - Original 800 > I 100 > P 33 > B 12~33
• 메타 데이터
  • 기계 위치 날짜 등 정보, 관련 정보

1. 게이트와 논리회로

• 반도체 소자
  • 컴퓨터에 CPU 반드시 필요
  • 트랜지스터, (집적한 IC) 집적도 높여 대량 사용 IC – LSI – VLSI
  • 메모리 반도체 DRAM(자료저장용) 캐퍼시터 사용, 상대적으로 간단
  • 시스템 반도체 CPU 트랜지스터 이용, 가치 높음,
  • DRAM 1bit 저장하는 캐퍼시터 대량 집적 대용량 메모리 - RAM 휘발성메모리 - ROM 비휘발성 메모리
  • 플래시 메모리 RAM ROM 합친 느낌 USB 메모리, SSD(가격이 비쌈)
• 게이트, 논리회로
  • 2진수연산 모든 계산 ROM에 저장: 느림, 고비용 2. 덧셈 회로 – 현재 사용되는 방법
  • 논리회로: 연산을 위한 gate 결합
  • Boolean expressions 이용
• 게이트의 종류
  • NOT gate, inverter /AND/OR
  • XOR gate: 둘 중 하나만 참이어야 참1이다(덧셈시)
  • NAND gate: 둘 다 1이면 거짓0
  • NOR gate: 1있으면 0
  • BUF gate: 증폭, 지연
  • 다중입력 게이트
• 게이트 만들기
  • 트랜지스터 이용
  • 유니버설 게이트: NAND 한 종류로 모든 게이트 가능함

1. 프로세서 구조 (CPU 기본적인 구조 설명)

• 회로 동등성
  • 같은 입력에 대해 같은 출력이 나옴
  • Boolean algebra 단순화 수학 이론
• 가산기(더하는 회로)
  • 2진수 더하기
  • 반가산기(half adder) 덧셈은 XOR과 AND 4자리 2진수 더하기
  • 전가산기 half adder 2개, or 결합 sum과 carry 출력
  • 입력3개 출력2개 4자리 계산 full adder 4개
• 멀티플렉서: 조합회로 기술 중 하나
  • MUX 여러입력 중 하나만 선택
  • DEMUX 여러 출력 중 하나만 선택
  • 4x1 멀티플렉서=4개 중 1개 선택 두 자리 2진수로 4개 표현
• 메모리 회로: cpu 중간 계산 결과 저장
  • 디램이 캐퍼시터 쓰기에 트랜지스터보다 느림 -결과를 못 받음, 중간에 임시 저장(latch) 트랜지스터로 결과 저장
  • S-R latch NAND 꼬아서 0or1 저장 ->1비트 메모리 - 0을 넣어야 작동? negative logic - S=1, R=1 이면 상태 유지 - S=1, 잠깐 R=0 X=0으로 초기화 - 잠깐 S=0 X=1로 됨 - S-R latch S,R 둘 다 0 금지
  • D flip-flop - 0 안되는 불안정한 점 개선 - 지금의 CPU
  • 레지스터(CPU내의 초고속 메모리) D flip flop 이용
  • 클럭의 도입 여러 개 저장할 때 시간을 맞춰야함 클럭clock: 시간 맞추는 기준 신호 ex) 3.0GHz CPU – clock 기준 의미 30억번 저장
• 프로세서 구조(종합 설명)
  • 반가산기-전가산기-n비트 가산기-계산가능
  • 래치-플립플롭-레지스터 – 저장가능
  • 멀티플렉서-결과 선택
  • ALU: 산술/논리(연산)장치 CPU 일부, op-code
  • 레지스터 파일: 레지스터 여러 개, ALU와 연결

1. 마이크로 프로세서

• 폰 노이만 아키텍처
  • 명령어, 제어장치 어떤 행동을 할것인지 저장한 것, CPU가 실행하는 최소 단위 명령어 정리해서 메인메모리에 저장(프로그램) 명령어 저장 방식
  • 폰 노이만 아키텍처
  • 명령어 사이클
  • 버스
  • 프로세서 비트
• IC와 CPU
  • IC분류
  • 마이크로프로세서
  • 마이크로프로세서 구분 - CPU: 계산전용 - MPU 단일칩CPU - MCU 아두이노 - SoC 1개의 desktop처럼 - AP 스마트폰, 태블릿의 고성능 SoC 칩 - GPU 3D 그래픽용 MPU - DSP 아날로그->디지털 신호처리 전용 - MMU 메모리 관리 칩(현재는 CPU 내장)
• 임베디드 시스템
  • 임베디드OS
  • 적용분야 - 항공기, 전투기 - 가전 - IOT : 스마트홈, 커넥티드 카

1. 기계어 어셈블리어

• 기계어
  • 폰 노이만 아키텍처
  • 인스트럭션(op-code,resister 선택 등 들음)
  • 기계어: instruction을 2진수로 직접 주는 방식
  • 기계어 특징: CPU별로 기계어 다르다 호환이 안된다
• 사례연구: PEP/8
  • CPU 복잡 -> 간단한 기초교육용 필요 - 가상의 CPU 시뮬레이션 모델
  • 16비트 구조, 0부터 FFFF까지
  • 116()
  • 누산기
  • 비트 레지스터
  • 개의
  • PC는 16비트(예상대로)
  • IR 16비트 아닌 8비트 명령 + 16비트 address IR에 뭐가 들어 있을ㄲ 앞쪽 4~5비트가 op code 뒤쪽 3비트가 해석방법(무슨 데이터를 가져올거냐 뺄거냐)
  • 뒤쪽 3비트 addressing mode immediate 방식 16비트부분레지스터로그대로해석 direct 방식 16비트가 메모리 address, 메모리에서 - 16비트 CPU라서 메인메모리 2바이트 가져옴

1. ex)

• 어셈블리어 기계어 너무 어려워 도입=mnemonic code
  • 기계어를 영단어 조합해서 표현
  • pep/8의 어셈블리 모델 비슷하게 바로 명령어, 주소 방법있음

1. 어셈블러로 기계어로 변환 exe 파일 2. exe 실행, 프로그램 실행 두 단계 거쳐야 함

• 메모리 주소 너무 길고 기억못함- 변수 도입 - 별명을 붙임 - 어셈블러가 변수도 관리
• 분기 명령
  • 다른 명령으로 이동
  • 레지스터값에 따라선택적 변경 가능
  • 경우에 따라 하는 일이 달라짐 - 혁신: 조건, 실행 바뀜, 반복가능

1. 의사코드

• 알고리즘과 의사코드
  • 알고리즘
  • 의사코드
  • 의사코드 예 A의 제곱근 x 구하기
• 의사코드 작성법
  • 원칙(일관되고 모호하지 않게) 값을 저장하는 변수, 입력(읽어옴), 출력(print), 선택(if then else), 다중선택(else if), 반복(while)
  • 어셈블리어 분기명령과 비슷한데 알아보기 쉽다.
• 배열변수
  • 변수에 값을 넣-주소를 찾아서 값 입력 -수열과 비슷하다?
  • 수열 변수 수열로 표현-아래첨자 표현 힘듦-a[2]처럼 씀
  • 배열변수 array -연속해서 배치(순서대로) -하나만 알면 나머지 위치도 알 수 있음 -1개당 2바이트 증가(32,64비트 경우 다름!!) 배열 번호 이용해 반복 수월해짐 배열 변수도 일반 변수처럼 사용 가능
• 문제 해결=알고리즘 답 찾기
  • (문제이해-계획-실행-재검토)
  • 문제 이해 질문하기(처리할정보, 예외, 답을 어떻게 아냐)
  • 계획 분할정복(작게 나눠 해결) =하향식 설계(top-down design)
  • 하향식 설계의 예(몇월-무슨계절?)

1. 탐색과 정렬

• 알고리즘
  • 정렬sort (비교연산 이용)
  • 알고리즘instaceanswer
  • 구할 수 있는 방법
  • 에 대한
  • 모든
• 순차탐색 = linear search
  • input data가 배열에 있다고 가정 하나씩 체크해서 보고
  • bool 복잡한 조건의 연결
  • 순차탐색의 개선 정렬된 배열이기에 필요없는 연산 할수도? 찾으면 끝내도록
• 이진 탐색
  • 이진탐색 가운데 값을 확인해서 범위를 절반으로 줄인다
  • 이진탐색 장단점 -속도 향상 -정렬된 배열에서만 사용 -n번 비교하면 2^n개 탐색 가능(최대log2n번)

그럼 정렬은 어떻게 할까?

• 정렬
  • 선택정렬 unsorted에서 가장 작은거 sorted로 옮김 -이미 옮긴 위치도 검사를 함-비효율 -빈 위치에 하나 넣자-> 하나의 배열만 쓰자
  • 하나씩 맞바꿔가며(swap) 작은거부터 정렬
  • 스왑 operation 2개를 바꾸려면 변수(대피)가 하나 더 필요함

1. 연결 리스트, 트리(효과적인 저장방법)

• 링크의 도입(배열에)
  • 배열의 문제(데이터 추가,삭제 힘듦) - 한칸씩밀고 넣거나 삭제 빈칸 생김
  • node 구조의 도입 -데이터의 연결 상태도 포함 -link: 다음 data의 위치를 가리킴 -맨뒤에 데이터 추가해도 실질적 순서는 link -data 수정 적어짐, 삭제도 마찬가지
• 복합 자료형
  • 구조체(structures)=레코드 (records) - 연관된 내용 한번에 저장, 여러 요소가 들어감 -node 구조는 복합자료형의 대표적 형태
• 연결 리스트
  • link에서 index대신 메모리 주소 사용 - 마지막은 end대신 0사용, 배열이 필요 없어짐
  • 연결리스트: 상호 연결된 리스트 - 마지막은 접지 표시함
  • 포인터 다른 노드를 가리키는 주소를 저장한 변수
  • null pointer: 끝값, 0으로 저장된 변수
  • 이중 연결 리스트-이전 데이터도 표시 -prev 존재, 양쪽으로 이동
• 트리 (링크 구조 확장)
  • 링크 단점: 1:1 대응만 가능
  • 한 노드에 여러 링크를 추가-링크를 배열로
  • root node, internal node, leaf nodes
  • 혹은 부모, 자식노드 -> 폴더 구조
• 이진 트리
  • 각 노드에 링크가 최대 2개(child)만 있음
  • left, right
  • 이진 탐색 트리BST(binary search tree) - right쪽이 무조건 큼
  • BST 예시 - 특정 값 찾을 때 이진 탐색과 동일한 방법?

1. 그래프와 추상자료형

• 그래프
  • 비교 -연결리스트-1개의 링크 -트리-2개 이상의 링크, 한 방향 -그래프-제한 없음(데이터 저장 방식)
  • V=꼭짓점들의 집합(node) E=변들의 집합(link)
  • 종류(무방향 그래프, 방향 그래프) - graph: edge에 방향성 없음, 양쪽 진행가능 - digraph: 방향존재 ex) 노선도, 추가 정보도 저장 가능
  • 그래프 탐색 navigation 응용 - A에서 B 갈 수 있는가, 최단 거리, 최소 비용
• 추상자료형
  • 자료구조에 대한 동작 데이터 다루는 방법, 동작
  • ADT(abstract data type) - 객체 지향의 기초 .data : 자료구조와 동일하게 표기 .method() : 함수 형태로 표시
• 큐 (많이 쓰이는 ADT 함수 설명)
  • queue = 대기줄 작동방식: 선입선출 enqueue(): 원소를 큐에 추가 v=dequeue(): 오래된 원소를 제거
  • 만드는 방법 연결리스트, 배열
  • 프린터에 사용되는 방식(프린터 큐)
• 스택 (또 다른 ADT)
  • stack = 쌓다 작동방식: 후입 선출 push(v) : v를 스택에 추가 v=pop() : 가장 최근 원소를 제거
  • 만드는 방법 연결리스트, 배열 top이 가장 최근 데이터를 가리킴
  • 스택-미로찾기-지나온 길 기록 +로봇청소기
• 서브 프로그램
  • 자주 사용되는 프로그램 일부 재사용 = procedure, subroutine 새로운 명령으로 추상화 함수 – 수학의 함수를 추상화, 값을 return
  • 처리에 필요한 정보는 변수로 저장 매개변수parameter: 정보를 받는 인수argument: 매개변수에 전달되는값
  • 변수

1. 고급 프로그래밍 언어

• 고급 프로그래밍 언어
  • 필요성 - 프로그램을 만들 때 더 쉽게 - syntax(문법)를 이용, 목적에 따라 다양한 언어
  • 자료형 도입 - 의사코드와 다르게 형태 정확히 지정
  • 선언 - 변수를 미리 선언
  • Boolean expression - 비교, 논리연산자 정의
  • 대입문= 선택문if 반복문while 제어구조
• 번역 과정: 1.프로그램 이용 어셈블리로 exe실행
  • 컴파일러 방식 - 2번처럼 코드-컴파일러-exe만들고 실행 - 빠름, 처음만 복잡함?
  • 인터프리터 방식(언어를 이해하는 기계) - 바로바로 번역 ex)jupyter - 속도 느림, 번거로움
  • Java의 가상 기계 방식 - 컴파일러로 bytecode를 만듦-java에서 번역
  • 비교 - 어셈블러: exe파일 - 컴파일러: 고급언어->exe파일 컴파일이 복잡, exe실행 빠름, 특정 CPU에서만 작동
  • • 인터프리터: 바로 번역, CPU 간접 실행, 실행이 느림, 간단한 일
  • • 가상 기계 방식: 고급언어->바이트코드->기계 다른 CPU에서도 실행 가능 자바는 웹페이지에서 모든 pc에서 실행하도록?
• 프로그래밍 언어 분류
  • 분류: 수행적 / 선언적(함수적/논리적)
  • 함수적: 수학 함수로 자료 처리 R, f(x,y) - (fxy), 인터프리터 방식 ex) 사용자 입력 필요
  • 논리적 Prolog – 첫 부분 fact 나열 후 질문 like AI
• 객체지향 패러다임 OOP
  • 캡슐화: object의 정보와 방법을 모음
  • 클래스 ex) UI의 width,height 속성, create,resize 방법 - instance class로 찍어냄? - 상속 class추가로 확장-복잡한 class 다형성 – 상속 중 겹칠 때 우선 순위부여(이런 게 있다)

기말고사 부분입니다(1,2편으로 구성)

컴퓨터학개론(Computer Science illuminated;Nell Dale & John Lewis) 5장~ 기말고사 정리