재귀와 백트래킹 연결 리스트

 

 

스택이 아래로 쌓이기 때문에 반복문보다는 시간이 오래 걸린다 (스택이 많이 쌓이기 때문에)

 

 

 

루프를 이용하면 스택이 필요하지 않고, 리커젼 보다 더 잘 수행될 수도 있다.

리커전이 익숙해지면 더 쉽게 답을 찾을 수도 있다.

 

 

---

 

 

[ 숙제 ]

 

=> 씨언어로 행 ㅇㅅㅇ?

 

 

---

 

 

* 리스트

 

리스트 <-> 셋 집합

 

집합 리스트의 가장 큰 차이점

집합 -> {1,2,3} == {3,2,1}

집합은 순서가 상관없지만 리스트는 순서가 상관있음

학생은 순번이 있기 때문에 리스트를 써야 하는 것

 

리스트를 표현하는 방법 -> 대표적으로 Arr

 

* 어레이가 뭐가 답답해서 링크드 리스트가 나왔을까?

 

- 어레이

하나의 배열 항목을 저장하기 위해 메모리 블록 하나가 할당된다. 

 

(장점)

1. 데이터 순서를 나타내는 집합이다. (순서!)

2. 똑같은 타입의 데이터를 순서대로 관리할 때

' 이거 다음거는 이거, 이거 다음거는 이거! ' 임을 찾고 싶으니까

3. 내가 어떤 값을 가져오고 싶을때 항상 같은 시간을 가진다. offset = size * index

한 번의 곱셈과 한 번의 덧셈이 필요함

 

(단점)

1. 올해 어레이를 삼천칸 잡앗음.  내년엔 6천이 됏음. 

올해나 내년에는 2천개는 쓰고 4천개는 남아잇고 이런식으로 유동적으로 쓸 수가 없음

(너무 많이 잡으면 낭비고 너무 적게 잡아도 문제)

2. 배열의 크기는 정적이다

* 정적이다 = 바꿀 수 없다.

3. 특정 부분에 데이터 삽입이 어렵다.

(뒤에 밀어야될 넘들이 백만개가 있으면 다 밀어야 됨)

 

 

 

- 링크드 리스트 : 데이터 집합을 저장하기 위해 사용되는 데이터 구조이다.

 

1. 연속되는 항목들을 포인터로 연결한다.

2. 마지막 항목은 NULL을 포인트한다.

3. 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.

4. (시스템 메모리가 허용하는 한) 필요한 만큼 길어질 수 있다.

5. 메모리 공간을 낭비하지 않는다 (하지만 포인터를 위한 추가의 메모리를 필요로 한다)

 

주황색: 링크드 리스트

노란색 : 어레이

 

- 링크드 리스트는 어떤 데이터를 찾으려면 얼마나 가야될 지 모름

 

 

링크드 리스트를 Abstract Data Type(ADT)로 만들면

- 고객 추가 함수

- 고객 서치 함수

- 고객 업데이트 함수 등등..

 

이 필요하겠지