자료구조

프로그램: 자료구조와 알고리즘으로 이루어집니다 

 

자료구조 => 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냅니다.

 

가장 단순한 자료구조로는 "변수" 

 

변수를 어디에 저장하는지에 따라서 처리방법이 달라진다  즉! 자료구조에 따라 알고리즘이 달라진다

ex1)
	int a= 87;
	int b=70;
	int c= 100;
	int average =(a+b+c)/3;
    
ex2)
    int[]arr={87,70,100};
    int average=0;
    for(int i ; i<arr.length;i++){
   	average += arr[i];
       }
        average /= arr.length;

알고리즘=> 어떤 문제를 해결하기 위한 구체적이고  확실한 방법

 

 

상황에 맞는 적절한 자료구조를 택하고 알고리즘을 적용한다.

part2

사용자의 요구사항에 따라 알고리즘은 다르지만 일반적으로 알고리즘의 속도를 성능에 척도로 사용하는데 이를 "시간 복잡도"라고 한다.  

 

시간복잡도 : 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간 

 

BUT  컴퓨터 성능에 따라 걸리는 시간이 다르기에 코드에서 성능에 많은 영향을 주는 부분 ( ex.반복문 )을 찾아 실행시간을 예측 할 수있다 

 

EX) 주어진 배열에서 '5' 찾을때 

ⓛ  ③  ⑤  ⑦    경우의 수  1. 최선의 경우 한번에 찾음  Big-Ω

                                          2. 최악의 경우 배열의 길이 만큼 걸림 Big-O

                                          3. 평균의 경우 배열의 길이 중간 만큼 걸림 Big-€

Big O natation(빅오 표기법)

O(1) :선형시간 알고리즘 , 계산량이 한번일 필요는 없지만 문제를 해결하는데 입력의 크기에 상관없이 100번의 계산이 걸린다고 하더라도 상수이기에 O(1)로 표기한다.

 

part3

배열 

:배열의 이해를 위해서는 배열이 메모리에서 어떤 모습을 하고 있는지 알아야 한다.

ex) int[10] arr ={1,2,3,4,5,};

     운영체제는  메모리에서 숫자 10개가 들어갈 수 있는 빈공간을 찾아 값을 할당한다.

     또한 배열의 시작 주소를 알고 있다, 배열에 인덱스 참조는 길이에 상관없이 한번에 가져오기에 O(1)성능을 가진다.

배열은 읽기/쓰기 , 즉 참조하기 좋은 성능을 가지고 있다  but 데이터삽입,삭제  성능은 좋지 않다.

 

배열의 장점	배열의 단점
읽기,쓰기와 같은 참조에는 O(1)의 성능을 가진다.	크기 예측이 힘들기 때문에 메모리 낭비가 발생할수 있다.
연속적으로 메모리공간에 할당되어있어 시작주소만 알면 다음 주소 접근이 쉽다 O(1)	데이터 삽입,삭제가 비효율적이다. (운영체제가 연속적으로 메모리 공간을 할당하기 때문에  데이터 삽입시 다시 새로 데이터를 넣어줘야 한다.)

 

part4

연결리스트 -개념 (LinkedList)

 

Q 이런 배열의 문제를 어떻게 해결 할까?

저장하려는 데이터들을 메모리 공간에 분산해 할당하고 분산된 데이터를 연결해주면 된다.

 

배열의 단점을 보완 해줄 수 있는  연결리스트 

->연결리스트는 노드(node)라는 것을 만들어서 수행하는데 노드의 구조는 단순합니다 

"Node"는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있습니다.

 

연결리스트 특징

                          1. 처음 연결리스트 정보를 알고 있으면 다음접근이 가능하다

                          2. 연결리스트에 데이터를 추가하면 빈 메모리공간 아무 곳에 데이터를 생성하고 연결만 해주면 되기 

                              때문에 배열에서 초기값이 필요없다.

 

	배열	연결리스트
크기	고정	동적
주소	연속	불연속
데이터참조	O(1)	O(n)
삽입과삭제	O(n)	O(n)

part5

연결리스트-구현

추상자료형이란?

         "어떠한 데이터와 그 데이터에 대한 연산" 

EX)

세탁기=기능(연산)       옷(데이터)

:데이터와 그 데이터를 연산하는 기능을 표기하는 것 

 

연결리스트의 추상자료형

1. 모든 데이터 출력/ printAll()

2. 모든 데이터 제거/ clear()

3. 인덱스 삽입/ insertAt(index,data)

4. 마지막 삽입/ insertLast(index)

5. 인덱스 삭제/ deleteAt(index)

6. 마지막 삭제/ deleteLast()

7.인덱스 읽기/ getNodeAt(index) 

 

part6

스택-개념

First In Last Out(FILO)

:먼저 들어간 데이터가 나중에 나오는 규칙이다.

ex)

먼저 들어온 사람이 맨뒤에있다.

---

연결리스트를 이용하여 스택 구현

Q. head를 가지고 스택만들기 쉽다?

head에 데이터를 삽입,제거도 똑같이 한쪽으로 진행하면 스택구조가 된다.

 

*스택은 어디에 쓰이는가?

주로 되돌리기 작업에 사용 

ex) 포토샵 ctrl+z 전에 작업을 컴퓨터가 스택에  모든것을 기록하고 있다. 다시 돌려줌

혹은 문법검사할때 스택에서 데이터를 넣고 그짝이 맞는지 확인! 짝이 맞지 않으면 

에러를 발생시킨다.

 

스택의 추상자료형

push - 데이터를 삽입

pop   - 데이터 제거

peek - 데이터 참조("top" =head 에 있는 데이터를 참조) 

isEmpty - 비었는지 체크

자료구조-스택(Stack)