1.추가

① 목표

• linked list 처음 또는 중간에 node 1개를 추가하기

② 전략

- 큰 그림

• 순서(index)와 값(value)을 활용해서 새로운 노드를 삽입하기

- 방법

1) 추가될 위치 접근: index-1번째 노드에 접근하기
2) 새로운 노드 할당: new_node 변수에 할당하기
3) 기존 노드 임시 변수 할당: next_node 변수에 할당하기
4) index-1번째 노드와 새로운 노드 연결하기
5) 새로운 노드와 기존 노드 연결하기

③ 그림

• 위 전략을 그림으로 나타내면 아래와 같음
  

④ 코드

    def add_node(self, index, value):       # 전략: index-1번째와 index번째 node를 분리하고, 그 사이에 새로운 node를 입력한다.

        new_node = Node(value)              # 2) 새로운 노드 할당하기
        if index == 0:						# 0번째 추가 시
            new_node.next = self.head       # head를 새로운 노드 다음에 연결한다.
            self.head = new_node  	    # 새로 추가된 노드를 head로 설정한다.
            return


        node = self.get_node(index - 1)     # 1) index-1번째 index에 접근한다.
        next_node = node.next               # 3) index번째 이후 node(줄줄이 사탕)를 next_node 변수에 저장한다.
        node.next = new_node                # 4) index -1 번째 노드와 새로운 index를 연결한다.
        new_node.next = next_node           # 5) 새로운 노드와 index번째 이후 node를 모두 연결한다.

2.삭제

① 목표

• linked list 처음 또는 중간에 위치하는 노드 삭제하기

② 전략

- 큰 그림

• index+1번째 이후 노드를 index-1번째 노드에 연결하기

- 방법

1) 삭제 노드 접근: index-1번째 노드에 접근하기
2) 기존 노드 임시 변수 할당: next_node 변수에 할당하기
3) index-1번째 노드와 기존 노드 연결하기

③ 그림

• 위 전략을 그림으로 나타내면 아래와 같음
  

④ 코드

 def delete_node(self, index): 		# 전략: index-1번
        if index == 0:			# 0번째 삭제 시
            self.head = self.head.next  # head 노드를 head 다음 노드로 설정하기
            return

        node = self.get_node(index-1)  # 1) index-1 번째 노드에 접근하기
        node.next = node.next.next     # 2), 3) index-1의 다음다음(index+1)번째의 노드를 index-1+1번째 노드로 할당하기

3.이진탐색

① 개념

• 비유하자면 '갯수가 n인 array의 절반에 해당하는 n/2번째 수(n이 홀수인 경우는 n//2)를 확인하여 목표 숫자를 찾는 방법'이라고 말할 수 있다.

② 활용

- 목표:

• 1부터 20까지 숫자 중 18 찾기

- 전략:

1) 큰그림

• 최솟값과 최댓값을 설정하고, 이 둘의 평균값(//2)을 목표하는 값(11)인지 맞추어보기

2) 방법(슈도코드)

2-1) 최댓값, 최솟값 할당하기
2-2) 예측값 할당하기
2-3) 최솟값이 최댓값보다 같거나 작을 때까지(while)
2-4) (while) 만약 예측값이 목표값과 같다면(if)
2-5) (while, if) True를 반환하라
2-6) (while) 만약 예측값이 목표값보다 작으면(elif)
2-7) (while, elif) 최솟값 = 예측값 + 1
2-8) (while) 만약 예측값이 목표값보다 크면(else)
2-9) (while, else) 최댓값 = 예측값 - 1
2-10) (while) 예측값을 다시 절반으로 나누기

find_target = 18
find_number = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]


def is_existing_target_number_binary(target, array):  
    cur_min = 0					    # 2-1) 최솟값 할당하기
    cur_max = len(array) - 1			    # 2-1) 최댓값 할당하기
    cur_guess = (cur_min + cur_max) // 2	    # 2-2) 예측값 할당하기
    

    while cur_min <= cur_max:			    # 2-3) 최솟값이 최댓값보다 같거나 작을 때까지(while)
        if array[cur_guess] == target:      	    # 2-4) (while) 만약 예측값이 목표값과 같다면(if)
            return True 			    # 2-5) (while, if) True를 반환하라

        elif array[cur_guess] < target:  	    # 2-6) (while) 만약 예측값이 목표값보다 작으면(elif)
            cur_min = cur_guess + 1		    # 2-7) (while, elif) 최솟값 = 예측값 + 1
            
        else:					    # 2-8) (while) 만약 예측값이 목표값보다 크면(else)
            cur_max = cur_guess - 1		    # 2-9) (while, else) 최댓값 = 예측값 - 1
        cur_guess = (cur_min + cur_max) // 2	    # 2-10) (while) 예측값을 다시 절반으로 나누기
    return False


result = is_existing_target_number_binary(find_target, find_number)
print(result)

4. 배운점

① 변화하는 것과 고정된 것을 기억하자

• 코드를 만들다보면 머리가 뒤죽박죽 될 때가 있다. 그 주범은 변화하는 변수와 고정된 변수가 섞이기 때문이다.
• 고정된 변수가 고정되고, 변하는 변수가 고정된다면 제대로 된 코드를 만들리 만무하다.
• 해결책은 간단하다. 외부화하여 기억하는 것이다. 머리로 기억하는 것이 아니라 주석처리를 해서 필요할 때마다 본다.
• 이렇게 한다면 에너지를 기억하는데 사용하지 않고, 코드의 흐름을 머릿속으로 구현해내는데 더욱 집중할 수 있다.

② 비교 시 변수를 떠올리자

• 언제까지 어떤 연산을 하라는 전제를 달기 위해서 while, if, elif 문을 사용한다.
• 이 때, 구문에 조건을 달아줘야 하는데, 코드 목표를 고려하여 변화하는 변수와 고정된 변수를 상기하여 조합해보자.
• 만약 필요한 변수가 선언되지 않았다면 인위적으로 변수를 선언하자.

③ 쉬운 것부터 세 바퀴는 돌아보자

• for, if, while 문 등 반복되거나 조건이 붙는 구문에서는 가장 간단한 예시로 3바퀴 돌려보자.
• 돌려보자는 의미는 나의 머리로 직접 계산을 해보자는 것이다.
• 그 후 각 줄(line)의 계산 결과를 코드 옆에 주석 표시 후 적어두자
• 만약 3바퀴 돌린 후 내가 예상한 결과가 나온다면 컴퓨터로 실행해보자
• 이렇게 하는 것이 가장 효과적으로 코드를 작성하는 방법 인 것 같다.