1. 자료구조
컴퓨터에 자룔르 효율적으로 저장하는 방식
- 자료구조를 설계하는 이유
① 실행 시간 효율 증대 = 프로그램 수행 시간 최소화
② 저장공간의 최소화 = 메모리 절약
- 자료구조 설계에 필요한 것
① 프로그램의 개발 목적
- 자료구조의 종류
① 단순구조 : 기본적인 데이터 타입(Type)
ex) 정수(int), 실수(float), 문자/문자열(char)
② 선형구조 : 각각의 자료들 사이의 전후 관계가 1:1인 것
ex) 리스트, 스택, 큐, 덱
③ 비선형구조: 각각의 자료들 사이의 전후 관계가 1:多(1 이상)로 망구조 혹은 계층 구조를 이루는 것
ex) 트리, 그래프
④ 파일구조 : 보조 기억 장치에 저장되는 파일에 대한 자료 구조
※ 일반적으로 자료 구조라 하면 "② 선형구조" 와 "③ 비선형구조"를 말한다.
2. 추상자료형
정보은닉 개념을 추가시켜 자료구조를 표현하는 방법
- 필요한 이유
① 정보은닉 : 중요한 정보만 나타내고, 중요하지 않는 정보를 숨기는 것
② 개발 효율성 증가
③ 사용자가 손쉽게 자료구조를 사용
④ 자료구조를 구현하기 전 설계도 작성 작업 > 핵심적인 내용의 간략한 표현
- 추상자료형의 예
프로그램 이름 : Parking //주차관리 프로그램
① 자료
In_Time : 들어온 시간 Full : 수용 가능한 차량 대수
Out_Time : 나간 시간 count : 현재 주차된 차량 대수
Num : 차량 번호 요금(각자 필요에 따라 작성)
② 명령
이름 입력 출력 설명
---------------------------------------------------------------------------------------
1.주차가능 IsOk() N/A True, False 주차가 가능한지 여부를 파악
---------------------------------------------------------------------------------------
2. 주차 Park() 차량번호 : Num N/A 주차하는 차량번호와 들어온 시간 저장
들어온시간 : In_Time 이때, 현 차량대수(count) 1증가
----------------------------------------------------------------------------------------
3. 나가기 Out() 나가는시간 : Out_Time 요금 끝나는 시간을 측정하여 요금을 계산
이때, 차량번호(Num)로 차량 식불
현 차량대수(count) 1감소
-----------------------------------------------------------------------------------------
- 작성 주의점
① 연산의 이름을 통해 어떤 행동을 하는지 파악이 가능해야함(상세 내용 및 주의점은 설명으로 표현)
- 추상자료형과 자료구조의 관계 // 인터페이스와 세부코드의 관계
※ 자료vs자료형
- 자료 : 프로그램에서 처리되는 특정값
- 자료형 : 자료 + 연산
3. 알고리즘
어떠한 문제의 해결 절차
- 알고리즘의 만족 조건
① 입력 : 외부에서 입력되는(제공되는) 자료가 0개이상 존재해야한다.
② 출력 : 적어도 1개 이상의 결과를 도출해야한다.
③ 명백성 : 의미가 정확해야한다.(컴퓨터가 알아야한다)
④ 유한성 : 무한의 Loop에 빠져서는 안된다. 반드시 종료되어야한다.
⑤ 유효성 : 실행가능한 연산으로 구성되어야 한다.
- 표현방법
① 자연어 : 사람의 언어, 말로 표현함. 사람에 따라 다르기 때문에 알고리즘으로서 부적절
② 순서도 : 그림으로 도식. 단계별, 직관적 표현에 능통하나, 복잡한 알고리즘 표현에 부적절
③ 의사코드 : 특정프로그램언어가 아닌 가상의 언어로 표현. 문법이 간편하여 편함.
가상코드, 유사코드, 슈도코드라고도 불림
④ 프로그래밍 언어 : C, Java와 같은 특정 프로그램언어로 표현하며, 문법이 엄격하여 기술에 비효율적
- 성능 분석
> 문제 해결이 가능한 여러가지 알고리즘 중 가장 우수한 알고리즘을 선택하기위해서 필요
① 기준
ⓐ 공간복잡도 : 알고리즘 실행에 필요한 저장공간 비교
ⓑ 시간복잡도 : 알고리즘 실행에 필요한 시간 비교
※ 대부분 시간 복잡도로 평가하나, 임베디드와 같은 특정 계열은 공간 복잡도로 평가한다.
>> 시간 복잡도 측정방법
→ 실제 실행시간 : 컴퓨터 성능과 상태에 따라 다른 값이 나옴(비객관적)
→ 실행되는 명령문의 개수 : 객관적인 지표로 사용가능
② 빅 오. 풀이법
> 시간 복잡도로 작성된 것을 최고차항만을 남기고 다란 낮은 항들과 상수를 제거한 것
효율 : O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^N) > O(N!)
------------------------------------------------------------------------------------------------
오랜만에 공부 & 포스팅하내요'' 마지막 빅오에 대한 것이 아주 적게 나왔습니다. 중요한 개념이겠지만...
난중에 다시 설명할 기회가 있으면 다시 정확히 설명하도록 하겠습니다.
보시다 오탈자가 있으면 가르쳐 주시면 감사감사하겠습니다.
컴퓨터에 자룔르 효율적으로 저장하는 방식
- 자료구조를 설계하는 이유
① 실행 시간 효율 증대 = 프로그램 수행 시간 최소화
② 저장공간의 최소화 = 메모리 절약
- 자료구조 설계에 필요한 것
① 프로그램의 개발 목적
- 자료구조의 종류
① 단순구조 : 기본적인 데이터 타입(Type)
ex) 정수(int), 실수(float), 문자/문자열(char)
② 선형구조 : 각각의 자료들 사이의 전후 관계가 1:1인 것
ex) 리스트, 스택, 큐, 덱
③ 비선형구조: 각각의 자료들 사이의 전후 관계가 1:多(1 이상)로 망구조 혹은 계층 구조를 이루는 것
ex) 트리, 그래프
④ 파일구조 : 보조 기억 장치에 저장되는 파일에 대한 자료 구조
※ 일반적으로 자료 구조라 하면 "② 선형구조" 와 "③ 비선형구조"를 말한다.
2. 추상자료형
정보은닉 개념을 추가시켜 자료구조를 표현하는 방법
- 필요한 이유
① 정보은닉 : 중요한 정보만 나타내고, 중요하지 않는 정보를 숨기는 것
② 개발 효율성 증가
③ 사용자가 손쉽게 자료구조를 사용
④ 자료구조를 구현하기 전 설계도 작성 작업 > 핵심적인 내용의 간략한 표현
- 추상자료형의 예
프로그램 이름 : Parking //주차관리 프로그램
① 자료
In_Time : 들어온 시간 Full : 수용 가능한 차량 대수
Out_Time : 나간 시간 count : 현재 주차된 차량 대수
Num : 차량 번호 요금(각자 필요에 따라 작성)
② 명령
이름 입력 출력 설명
---------------------------------------------------------------------------------------
1.주차가능 IsOk() N/A True, False 주차가 가능한지 여부를 파악
---------------------------------------------------------------------------------------
2. 주차 Park() 차량번호 : Num N/A 주차하는 차량번호와 들어온 시간 저장
들어온시간 : In_Time 이때, 현 차량대수(count) 1증가
----------------------------------------------------------------------------------------
3. 나가기 Out() 나가는시간 : Out_Time 요금 끝나는 시간을 측정하여 요금을 계산
이때, 차량번호(Num)로 차량 식불
현 차량대수(count) 1감소
-----------------------------------------------------------------------------------------
- 작성 주의점
① 연산의 이름을 통해 어떤 행동을 하는지 파악이 가능해야함(상세 내용 및 주의점은 설명으로 표현)
- 추상자료형과 자료구조의 관계 // 인터페이스와 세부코드의 관계
※ 자료vs자료형
- 자료 : 프로그램에서 처리되는 특정값
- 자료형 : 자료 + 연산
3. 알고리즘
어떠한 문제의 해결 절차
- 알고리즘의 만족 조건
① 입력 : 외부에서 입력되는(제공되는) 자료가 0개이상 존재해야한다.
② 출력 : 적어도 1개 이상의 결과를 도출해야한다.
③ 명백성 : 의미가 정확해야한다.(컴퓨터가 알아야한다)
④ 유한성 : 무한의 Loop에 빠져서는 안된다. 반드시 종료되어야한다.
⑤ 유효성 : 실행가능한 연산으로 구성되어야 한다.
- 표현방법
① 자연어 : 사람의 언어, 말로 표현함. 사람에 따라 다르기 때문에 알고리즘으로서 부적절
② 순서도 : 그림으로 도식. 단계별, 직관적 표현에 능통하나, 복잡한 알고리즘 표현에 부적절
③ 의사코드 : 특정프로그램언어가 아닌 가상의 언어로 표현. 문법이 간편하여 편함.
가상코드, 유사코드, 슈도코드라고도 불림
④ 프로그래밍 언어 : C, Java와 같은 특정 프로그램언어로 표현하며, 문법이 엄격하여 기술에 비효율적
- 성능 분석
> 문제 해결이 가능한 여러가지 알고리즘 중 가장 우수한 알고리즘을 선택하기위해서 필요
① 기준
ⓐ 공간복잡도 : 알고리즘 실행에 필요한 저장공간 비교
ⓑ 시간복잡도 : 알고리즘 실행에 필요한 시간 비교
※ 대부분 시간 복잡도로 평가하나, 임베디드와 같은 특정 계열은 공간 복잡도로 평가한다.
>> 시간 복잡도 측정방법
→ 실제 실행시간 : 컴퓨터 성능과 상태에 따라 다른 값이 나옴(비객관적)
→ 실행되는 명령문의 개수 : 객관적인 지표로 사용가능
② 빅 오. 풀이법
> 시간 복잡도로 작성된 것을 최고차항만을 남기고 다란 낮은 항들과 상수를 제거한 것
효율 : O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^N) > O(N!)
------------------------------------------------------------------------------------------------
오랜만에 공부 & 포스팅하내요'' 마지막 빅오에 대한 것이 아주 적게 나왔습니다. 중요한 개념이겠지만...
난중에 다시 설명할 기회가 있으면 다시 정확히 설명하도록 하겠습니다.
보시다 오탈자가 있으면 가르쳐 주시면 감사감사하겠습니다.