C - 자료구조 기초2

기법이란 무엇인가?

기법 : 자료를 적절한 구조를 갖도록 조직하고 그에 따른 연산을 제공
	연산 : 자료를 관리하기 위한 작업(추가, 제거, 검색, etc)
    구조는 달라도 연산은 동일함 -> 구조에 따른 연산의 구현 방법은 다름
    추상화 : 개별적인 사람이나 사물, 상황의 성질로부터 추출되어 가공된 일반적이고 공통적인 개념
    매우 다양한 형태의 자료가 존재하며 각 자료들의 개별적인 속성을 제거하고 공통된 속성을 추출해 이를 이용하는 과정
    ex ) 전화번호, 앱, 버스번호 등 리스트로 자료를 관리한다는 점 
    리스트에 대한 추가/제거/검색 연산은 모든 앱에 공통적으로 작용됨
    이러한 형태에 대한 자료 구조를 추상 자료형(abstract data type)이라고 칭함,
    어떠한 자료와 그 자료에 대한 연산을 명기한 개념
    
    
구조 : 개별적인 자료들이 목적에 적합한 관계를 갖도록 배치된 상태
	구조(1) : 리스트 -> 자료를 여기저기 보관하지 않고 한곳에 모아서 표현함
    구조(2) : 정렬된 리스트 -> 그냥 리스트의 경우 자료의 위치를 예측하기 어려움
    구조(3) : 온 순서에 따라 처리하며 그 후에 온 자료들을 그 뒤에 차례로 처리 하는 방식 
    이러한 구조를 <큐>라고 한다
  	구조(4) : 족보 같은 경우를 표현하려면 한줄로 표현해선 원소들간의 관계의 일관성이 유지 되지 않음
    계층 구조로 표현하면 이해하기 쉬우며 이와 같은 구조를 <트리>라고 한다
    구조(5) : 가령 6명의 사람이 있고, 각각의 사람들간 관계가 존재한다. 이러한 관계를 표현하기 위해선
    시각적인 표현이 가장 효과적이다. 6명의 사람들중 다른 개체와 관계를 맺고 있지 않은 존재가 있다고
    가정하고 이러한 형태를 표현하는 구조를 <그래프>라고 한다.

효율이란 무엇인가?

효율 : 어떤 성과를 얻기 위해서 얼마나 많은 자원을 투입하였는지를 측정하는 것이며 성능이라고도 함
	- 효율 = solution / resource 이다
    ex ) 이번 일을 하는데 철이는 1000원을 쓰고 훈이는 3000원을 썼다.

효율적과 효과적은 어떤 성과를 얻기 위해 얼마나 많은 자원을 투입하였는지를 측정하는 점은 동일하다
	- 효율적은 동일한 성과를 얻기 위해 투입된 자원의 크기에 따라서 결정됨
    - 효과적은 동일한 자원을 투입했을때 얻는 성과의 크기에 따라서 결정됨
    
성능의 3가지 경우
	- 최선의 경우 : 최고기록 -> 여러 기록들 중에서 가장 좋은 기록만 기억
    - 평균의 경우 : 여러 과목의 점수를 평균해서 산정
    - 최악의 경우 : 대기시간 -> 가장 긴 시간을 알려줌
자료 구조에서의 성능은 최악의 경우(보장)에 대한 성능임

컴퓨터의 자원 
    - 시간 -> cpu : 이 프로그램은 10초 걸린다
    - 공간 -> 메모리 : 이 프로그램은 100MByte의 메모리를 요구한다
    CPU가 훨씬 비싸고 발전이 느린 부품이기에 여기서는 시간에 대한 자원을 더 중요하게 생각한다.

자료구조의 성능
	- 입력된 자료의 크기에 따라서 시간 (공간)이 얼마나 필요한지 측정
   	- 입력된 자료의 크기가 증가할수록 요구되는 시간(공간)의 증가 속도를 표현

 

공부할 내용의 구성

자료를 효율적으로 관리하는 기법
		성능 분석
일차원 구조 : 리스트
		- 배열
		- 연결리스트
		- 스택/큐

		정렬

계층 구조 : 트리
		- 이진 탐색 트리
   		- 우선 순위 큐

		탐색

관계를 표현하고 정보를 추출하는 기법 : 그래프
		- 깊이 우선 탐색
        	- 넓이 우선 탐색

 

맵/집합에 대한 개념

균형 이진 탐색 트리

해시 구조

네트워크

STL

를 따로 공부해서 준비해야함