스파르타 인강 - 자료 구조, 알고리즘 2주차

01. 어레이와 링크드리스트

https://www.faceprep.in/data-structures/linked-list-vs-array/ 출처

연산자	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

02. 클래스

• 클래스란?

클래스는 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념

객체란? - 객체는 세상에 존재하는 유일무이한 사물

클래스가 사람이라면, 객체는 유재석이 될수도 있고, 박명수가 될 수도 있다.
클래스가 동물이라면, 객체는 강아지가 될수도 있고, 고양이가 될 수도 있다.

클래스에는 생성자(Constructor)라는 게 있는데 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있다.
파이썬에서 생성자 함수의 이름은 init으로 고정되어 있다!!!!( 아니 왜 밸로그는 __못쓰는거지?)

03. 링크드 리스트 구현 - 1

이걸 일일이 계속 연결하는건 너무나도 번거롭다.
따라서 LinkedList라는 클래스를 만들어보자!!
LinkedList 는 head node 만 필요하다!
다음으로 넘어가기 위해선 next를 통해야 함.

1) LinkdList 는 self.head 에 시작하는 노드를 저장한다.
2) 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다.

이제 LinkdList의 맨 뒤에 새로운 Node를 붙이는 append 함수를 만들어보자!
head를 변경시킬 순 없으니 cur이라는 변수를 이용해서 접근

cur.next가 None이라는 것은 맨 마지막까지 왔다는 소리

04. 링크드 리스트 구현 - 2

Q. 링크드 리스트에서 모든 원소 출력.

	...
	def print_all(self):
    cur = self.head
    while cur is not None:
        print(cur.data)
        cur = cur.next
	...
    

추가해주자!

Q. 링크드 리스트에서 index번째 원소를 반환하시오.

	...
	def get_node(self, index):
    node = self.head
    count = 0
    while count < index:
        node = node.next
        count += 1
    return node
	...
    

head에 저장되어있는 노드를 node 라는 변수에 담고,
count 라는 인덱스를 저장하기 위한 변수를 저장.

그리고 count 가 index 가 될 때까지
(이 때, while 문 내부에서 1씩 더해주니까 작을때까지로 조건)
node의 next 값을 node 에 대입하고 count 를 증가.
이 과정을 count 가 index가 아닐때까지 반복!
그리고 node를 반환시켜준다.

Q. 링크드 리스트에서 index번째 원소를 추가하시오.

	...
	def add_node(self, index, value):
    new_node = Node(value)
    if index == 0:
        new_node.next = self.head
        self.head = new_node
        return

    node = self.get_node(index - 1)
    next_node = node.next
    node.next = new_node
    new_node.next = next_node
	...
    

어느 코드에서나 index - 1 처럼 -1 하는 코드가 있으면,
0의 경우에는 어떻게 될까? 에 대한 걱정을 하자.
만약 0이 입력된다면, get_node(-1) 이 호출되어서 오류발생
따라서, 이런 경우는 예외처리를 따로 해줘야 한다.
만약 0번째에 노드를 넣고 싶다면?
새로운 노드의 next 를 현재 가지고 있는 head 에 연결하고,
우선 현재 가지고 있는 head 를 새로운 노드로 교체!

05. 이진 탐색

만약 UP DOWN 게임을 한다고 하자.
1~100의 범위에서 숫자를 맞춰야 하는데 가장 효율적인 방법은 절반인 50을 시도하는 것이다.
이러한 방법을 이진탐색 이라고 한다.

Q. 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있다. 이 배열 내에 14가 존재한다면 True, 존재하지 않는다면 False 를 반환하시오.

TIP. 숫자 내림 방법 : // 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 구함

print((4 + 5) / 2)
4.5
print((4 + 5) // 2)
4

만약에 순차탐색으로 14라는 숫자를 맞출경우 배열의 첫번째부터 훑으니까 14번이 걸린다.
하지만 위에 작성한 이진 탐색으로 맞출경우

• 첫 번째 시도 : (0 + 15) / 2 = 7번째 인덱스의 값, 8 < 14 이므로
  7 + 1, 8번째부터 15번째 사이를 찾는다.

• 두 번째 시도 : (8 + 15) / 2 = 11번째 인덱스의 값, 12 < 14 이므로
  11 + 1, 12번째부터 15번째 사이를 찾는다.

• 세 번째 시도 : (12 + 15) / 2 = 13번째 인덱스의 값, 14 == 14 이므로 성공!

총 3번밖에 안걸린다.
이걸 빅오 표기법으로 하면 O(logN)만큼 걸린다고 할 수 있다.

06. 재귀 함수 - 1

• 재귀란?

재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

자기 자신을 호출하는 함수이다.

이해하기 쉽게 유명한 예시를 하나 들겠다.

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

재귀 함수를 이용하면 간결하고 효율성 있는 코드작성이 가능하기 때문에 사용한다.

Q. 60에서 0까지 숫자를 출력하시오.

재귀함수를 사용할 때 생각해야 할 것은 반드시 빠져나가는 지점을 만들어줘야 한다는 것.

안그러면 무한 루프에 빠져서 에러발생!

탈출조건 써줘서 해결완료~

06. 재귀 함수 - 2

• 팩토리얼( Factorial)

  재귀함수와 관련되어 나오는 대표적인 문제에 팩토리얼이 있다.
  팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다.

3! 은 3 2 1 = 6,
4! 는 4 3 2 1 = 4 3! = 24
즉,
Factorial(n) = n Factorial(n - 1)
Factorial(n - 1) = (n - 1) Factorial(n - 2)
....
Factorial(1) = 1
의 구조

n = 1일 때, 탈출조건 써주는건 필수!

• 회문 검사

회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미한다.

예 => 토마토, 오디오, 소주만병만주소 ......

컴퓨터는 palindrome(회문을 의미)으로 회문인지 확인 가능.

is_palindrome("토마토")   # True
is_palindrome("tomato") # False
is_palindrome("abcba")  # True

Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.
"abcba" # True

그런데, 이 방법을 재귀 함수를 이용해서 해결할 수 있다!

항상 주의할 점은 탈출조건은 필수로 써줘야 한다. 꼭 명심하자.