자료구조, 첫번째 정리

자료구조,프로그래밍기본,DB

자료구조, 너무 어렵다.

자료구조란? (Data Structure)

컴퓨터 과학에서 효율적인 접근 및 수정을 가능하도록 하는 자료의 조직,관리,저장

자료 구조는 데이터 값의 몽미 또 데이터 간의 관계, 데이터 적용할 수 있는 함수나 명령 의미한다.

 

단순구조

정수, 실수 문자, 문자열

선형구조

순차리스트, 연결리스트(단순,이중,원형 연결 리스트), 스텍, 큐, 덱(데크라고도 불림)

비선형 구조

트리 ( 일반, 이진)

그래프 ( 방향, 무방향)

파일구조

순차, 색인, 직접

 

알아두면, 유용한 사이트

codeground.org

백준 코딩

 

알고리즘 : 문제를 해결하기 위한 절차나 방법을 말한다. (어떤한 행동을 하기 위해서 만들어진 명령어들의 유한 집합)

알고리즘의 아래의 요건이 만족이되어야한다.

입력 : 0또는 그 이상의 외부에서 제공된 자료가 존재한다

출력 : 최소 1개 이상의 결과를 가진다.

명확성 : 각 단계는 명확하며 애매함이 없어야 한다.

유한성 : 단계 유한한 횟수로 거친 후 문제를 해결을 하고 종료해야 한다.

효과성 : 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.

 

알고리즘 표현 방법

자연어 : 일상 생활에서 사용하는 말, 언어를 사용하여 표현

의사코드 : 자연어를 프로그래밍 언어처럼 표현

순서도 : 미리 정의된 기호나 도형을 이용하여 표현

프로그래밍 언어 : 프로그래밍언어로 표현

 

알고리즘 성능 분석

공간 복잡도

Big-O표기법 주료 사용, 프로그램을 실행시킨 후 완료 할 때 필요로 하는 자원 공간의 양

공간 복잡도 : 고정 공간 + 가변 공간

시간 복잡도

Big-O표기법 주료 사용, 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간

시간 복잡도 = 컴파일 시간 + 실행 시간

 

- 컴파일은 프로그램마다 거의 고정적인 시간이 소요됨

- 실행 시간의 경우는 사용되는 컴퓨터의 성능에 달라질 수 있으므로 실행시간보다 명령문의 실행 빈도수에 따라 계산됨

* 시간도 적게 쓰고, 자원도 적게 쓰는 것이 가장 최적이라고 볼 수 있음.

 

대부분의 경우 시간 복잡도를 이용하여 사용 함.

 

분석 4종류에는 최악경우 분석, 평균, 최선, 상각 이렇게 4종류가 있다.

 

첫번째, 최악경우 분석의 경우에는 '어떤 입력이 주어지더라도 알고리즘의 수행 시간이 얼마 이상은 넘지 않는다'라는상한(Upper Bound)

두번째, 평균경우 분석은 입력의 확률 분포를 가정하여 분석, 일반적으로 균등 분포(Uniform Distribution)

세번째, 최선경우 분석은 가장 빠른 수행 시간을 분석

네번째, 상각분석 일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산 횟수로 나누어 수행 시간 분석

 

알고리즘 수행 시간의 점근 표기법

수행 시간은 알고리즘이 수행하는 기본 연산 횟수를 입력 크기에 대한 함수로 표현

함수는 다항식으로 표현되며, 이를 입력의 크기에 대한 함수로 표현하기 위해 점근 표기법이 사용

 

종류

Big-Oh(상한) 표기법, Big-Omega(하한) 표기법, Theta(유사한) 표기법

위 세개의 표기법에 관해서는 타 블로그의 너무 잘표현되어져있는 것을 참고하도록 하자.

- 빅오 표기법을 유머와 함께 잘 설명 해주는 블로그(링크)

 

추상 데이터 타입 (ADT : Abstract Data Type) - 유사한 작동을 하는 특정 데이터 구조 집합이나 유사한 의미를 갖는 프로그래밍 언어에서의 특정 데이터 구조를 위한 수학적 모델

컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 말함

 

추상화는 "What" 논리적으로 정의[무엇]

구체화는 "How" 를 실제적으로 표현[어떻게]

 

컴퓨터를 이용하여, 크고 복잡한 문제를 단순화하여 쉽게 해결하기 위한 방법 (추상화)

자료 추상화 - 처리 할 자료, 연산, 자료형에 대한 추상화를 표현한다.

자료 - 프로그램의 처리 대상이 되는 모든 것을 의미한다.

연산 - 어떤 일을 처리하는 과정, 연산자에 의해 수행

 

자료형의 경우에는 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합이다

정수는 다들 알고 있을거라고 생각한다. (-1,0,1)

연산자는 위 정수에 대한 연산자의 집합이다 (+,-,*)

 

데이터 : 의미 있는 정보를 가진 모든 값, 사람이나 자동 기기가 생성 또는 처리하는 형태로 표시되어진 것

데이터 타입 : 데이터들의 집합과 이러한 데이터에 적용 할 수 있는 연산의 집합

추상 데이터 타입 : 자료 구조를 추상적, 수학적으로 정의한 것

 

출처: 위키백과, 나무위키 (다들 사랑해요 자료의 열람 :D)

자바와 함께하는 자료구조의 이해, 양성봉, 생능출판

깃허브 404 (링크)

 

글을 확인 후 업로드를 했는데, 글 내용이 전부 삭제가 되었다. 순간 당황하고 얼른 다시 백업해둔 글 내용으로 대체하여 수정했다. 너무너무 당황스러웠다.. 마치 낚시글 올린 듯한 기분이였다. 자료구조 책을 보니, 너무 눈 앞이 깜깜하지만 열심히와 이해하면서 하면, 실력이 늘어갈것이라고 생각한다 일단, 걱정은 접어두고 해보자 !