01. 자료와 정보
IT 는 Information Technology 의 약자로 처음에는 정보가 중요했지만 점점 data 에 대한 중요성이 대두되고 있다
자료는 현실 세계에서 관찰이나 측정을 통해서 수집된 값이나 사실 정보는 적절한 의사결정을 할 수 있게 하는 지식으로 자료의 처리 결과물이다 -> 관찰이나 측정을 통해 수집된 데이터를 실제 문제에 도움이 될 수 있도록 해석하고 정리한 지식
자료 => 처리 => 정보
컴퓨터 사이언스란 위 처리 과정을 컴퓨터로 하는 것을 말한다
좋은 자료구조란 일하기 효율적이되도록 잘 정리된 자료의 구조를 말한다
02. 추상화
추상화
공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것으로 말하는 사람의 의사를 간결하게 한다
자료의 추상화
다양한 대상을 컴퓨터에 저장하고 처리하기 위해 대상들의 의미와 구조에 대해 공통 특징을 뽑아 정리한 것
지도나 그래프 등도 추상화에 포함된다
03. 자료구조와 알고리즘
자료구조
추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것 자료의 추상화와 구조화가 적절히 이루어지면 효율적이고 확장성이 좋아짐
자료구조를 볼 때 컴퓨터는 굉장히 구체적으로 본다 (하나하나 직접 실행하기 때문) 사람은 추상화하여 본다 (매번 반복되는 내용들을 생각하지 않아도 되기 때문)
알고리즘
추상화된 명령의 연속된 덩어리 자료구조가 처리해야 될 대상이 되는 자료의 추상화였다면 알고리즘은 자료를 이용해 처리해야 될 작업(명령)에 대한 추상화를 말한다
자료구조는 입력 값에 의해 구체화 되고 알고리즘은 프로그램을 통해 구체화 된다
프로그래밍 언어는 자료구조와 알고리즘을 구체화하기 위한 방법
추상 자료형
자료의 복잡한 논리적 성격을 정의하는 형식으로 자료의 집합과 연산 집합에 대한 정의로 구성되며, 자료구조를 표현하는 가장 대표적 방법
자료의 추상화를통해 자료의 집합과 연산 집합을 수학적 표현으로 정의하여 추상 자료형을 만든다
학점 테이블에서 사용할 자료구조를 따로 정의하여 사용하기도 한다 학점 내 이름, 과목, 점수 등을 정의해서 사용한다면 학점 또한 하나의 자료구조가 되는 것
1
2
3
4
5
type 학점 = {
이름: string
과목: string
점수: number
}[]
04. 알고리즘의 개념과 조건
알고리즘
컴퓨터에게 명령할 추상화된 명령어의 연속된 덩어리
알고리즘의 조건
- 출력: 알고리즘 수행 후 한 가지 이상의 결과를 생성한다
- 유효성: 반드시 실행 가능해야 한다
- 입력: 내/외부의 입력 값은 유한해야 하며, 반드시 입력 형태가 정의될 수 있어야 한다
- 명확성: 각 명령들은 명확해야 한다 (애매하면 안된다)
- 유한성: 종료가 명확하게 정의되어 있어야 한다
05. 알고리즘의 성능
실행시간 분석
알고리즘의 예측 실행시간을 추정하여 성능을 분석한다 알고리즘의 실행 횟수를 O(n) 으로 표현하여 실행 시간의 유사한 증가 경향을 표현한다
실행 메모리 분석
알고리즘을 실행 하는데 필요한 메모리를 추정하여 성능을 분석한다
알고리즘의 공간 복잡도는 프로그램 실행 후 완료까지 필요한 총 메모리 공간을 말한다 고정 공간: 프로그램의 크기나 ㅇ비출력 횟수에 관계 없이 컴파일 시에 결정되어 프로그램 실행이 끝날 때 까지 고정적으로 필요한 공간을 말한다 가변 공간: 프로그램 실행 과정에서 동적으로 할당되어야 하는 자료구조와 변수들을 위해 필요핸 메인메모리 공간
최근 메모리 성능이 좋아지면서 자주 사용되지는 않는다
실행시간 측정
실제로 프로그램을 실행하는데 걸리는 시간을 측정하여 성능을 측정 실제 실행될 수 있는 프로그램이 있어야 하기 때문에 비용이 너무 커서 사용하지 않는 방법