📜 알고리즘

• 알고리즘 : 어떤 문제가 있을 때 그것을 해결하기 위한 여러 동작
• 알고리즘 공부 이유
  • 기본 코드 구현력 높이기
  • 시간 복잡도, 공간 복잡도 학습 – 중요하지만 이해하기 힘듦

:: ✍ 최댓값 찾기

첫번째 방법 (이중for문)

• 각 숫자마다 다른 숫자와 비교해 최대값 확인
• for~else 문은 for문에서 break 발생하지 않았을 경우의 동작을 else에 적어주는 것
• 즉, for문이 끝낼까지 break 발생 안됐다면 else로 고고!

input = [3,5,6,1,2,4]

def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num < compare_num:
                break
        else:
            return num


result = find_max_num(input)
print(result)

두번째 방법 (지정변수)

• 지정할 변수 만들고 배열을 돌아가면서 그 변수와 비교
• max_num이라는 변수 설정 후 이 변수에 가장 큰 값 기록하게끔

input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
    max_num = array[0] # 임의숫자 넣으면서 갈 것이기 때문에 초기값 설정해주는 것
    for num in array:
        if num > max_num:
            max_num = num

    return max_num

result = find_max_num(input)
print(result)

:: ✍ 최빈값 찾기

문자인지 확인하는 방법 : str.isalpha()

# str.isalpha()

print("a".isalpha())    # True
print("1".isalpha())    # False

s = "abcdefg"
print(s[0].isalpha())   # True

알파벳 별 빈도수 리스트 저장

• 저장하기 귀해 길이가 26인 0으로 초기화된 배열 만들기

alphabet_occurrence_array = [0] * 26

아스키 코드 사용해 빈도수 추가

• 문자를 아스키 코드로 변환 : ord()

# ord() 이용해서 아스키 값 받기

print(ord('a'))               # 97
print(ord('a') - ord('a'))    # 97-97 -> 0
print(ord('b') - ord('a'))    # 98-97 -> 1

:: ✍ 각 알파벳별 빈도수 업데이트

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
    	if not char.isalpha():
        	continue # 코드실행 건너뛰기
        arr_index = ord(char) - ord("a") ## 97-97
        alphabet_occurrence_array[arr_index] += 1
        
    return alphabet_occurrence_array
    
print(find_alphabet_occurrence_array("hello my name is sparta"))
# [3, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0]

첫번째 방법

• 각 알파벳마다 문자열 돌면서 몇글자 나왔는지 확인
• 저장한 알파벳 빈도수보다 크다면 그 값을 제일 큰 알파벳으로 저장

input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"] # 각 문자열 비교를 위해
    max_occurrence = 0 # 최고로 많이 나온 횟수를 저장하는 변수
    max_alphabet = alphabet_array[0] # 최고로 많이 나온 알파벳 저장하는 변수

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

result = find_max_occurred_alphabet(input)
print(result)

두번째 방법

• 각 문자열 돌면서 해당 문자가 알파벳인지 확인
• 알파벳이면 그것을 인덱스화 시켜 빈도수 업데이트
• 아스키 코드를 문자로 바꾸는 법 : chr()

input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
        if not char.isalpha():
            continue # 코드실행 건너뛰기
        arr_index = ord(char) - ord("a") # 97-97
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        # index 0 -> alphabet_occurrence 3
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence > max_occurrence:
            max_alphabet_index = index
            max_occurrence = alphabet_occurrence
    print(max_alphabet_index)
    return chr(max_alphabet_index + ord("a"))

result = find_max_occurred_alphabet(input)
print(result)

아스키코드를 인덱스로 바꾸는 방법

처음 a를 0으로 만들기 위해
ord(a)-> 97 - ord(a) = 0

인덱스를 문자로 만드는 방법

0을 a로 만들려면
0 + ord(a)->97 -> chr(97) -> a

chr(97) == 'a'
chr(0 + ord('a')) == 'a'
chr(0 + 97) == 'a'
chr(1 + 97) == 'b'

:: ✍ 시간복잡도 판단하기

• 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계
• array(입력값)의 길이는 보통 N이라고 표현
• 각 줄 실행 = 1번 연산
• 입력값이란?
  • 함수에서 크기가 변경될 수 있는 값

최댓값 찾기 첫번째 방법 시간복잡도 판단

• array의 길이 X array의 길이 X 비교 연산 1번 만큼의 시간
• 즉, N2 만큼의 시간

for num in array: # array 길이 만큼 아래 연산 실행
    for compare_num in array: # array 길이 만큼 아래 연산 실행
        if num < compare_num: # 비교 연산 1번 실행
            break
    else:
        return num

최댓값 찾기 두번째 방법 시간복잡도 판단

• max_num 대입 연산 1번
• array의 길이 X (비교 연산 1번 + 대입 연산 1번)
• 즉, 2N + 1 만큼의 시간

max_num = array[0] # 연산 1번 실행
for num in array: # array의 길이만큼 아래 연산 실행
    if num > max_num: # 비교 연산 1번 실행
        max_num = num # 대입 연산 1번 실행

return max_num

첫번째 : N2 | 두번째 : 2N + 1

• N이 커질수록 큰 차이가 남
• N의 지수 먼저 비교

∴ N의 지수 비교 후 시간 복잡도 분석

• 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악
• 상수의 연산량이 필요하다면, $1$ 만큼의 연산량이 필요하다고 하면 됨

:: ✍ 공간복잡도 판단하기

• 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계
• 입력값이 2배로 늘어났을 경우 문제를 해결하는데 걸리는 공간은 몇배로 늘어나는지 보는 관계
• 연산에서 공간으로 가는 것일 뿐 시간복잡도와 유사함

최빈값 첫번째 방법 공간복잡도

• 저장한 알파벳 빈도 수가 크다면 그 값을 저장 후 제일 큰 알파벳으로 저장
• 저장하는 데이터 양 각 1개의 공간 사용
• alphabet_array 길이 = 26
• max_occurrence, max_laphabet, occurrence 변수 = 3
• 즉, 29개의 공간 필요

alphabet_array = ["a", "b", "c", ..., "x", "y", "z"]# 26개 공간 사용
max_occurrence = 0 # 1개 공간 사용
max_alphabet = alphabet_array[0] # 1개 공간 사용

for alphabet in alphabet_array:
    occurrence = 0 # 1개 공간 사용

최빈값 두번째 방법 공간복잡도

• 각 알파벳 빈도수 저장 후 빈도수 가장 많은 알파벳 인덱스 값 반환
• alphabet_array 길이 = 26
• arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
• 즉, 30개 공간 필요

alphabet_occurrence_array = [0] * 26 # 26개 공간
for char in string:
    if not char.isalpha():
        continue # 코드실행 건너뛰기
    arr_index = ord(char) - ord("a") # 1개 공간 # 97-97 
    alphabet_occurrence_array[arr_index] += 1

max_occurrence = 0 # 1개 공간
max_alphabet_index = 0 # 1개 공간
for index in range(len(alphabet_occurrence_array)):
    # index 0 -> alphabet_occurrence 3
    alphabet_occurrence = alphabet_occurrence_array[index] # 1개 공간

    if alphabet_occurrence > max_occurrence:
        max_alphabet_index = index
        max_occurrence = alphabet_occurrence

공간복잡도 보다는 시간 복잡도를 더 신경 쓰는 것이 좋음

• 공간복잡도의 크기는 상수이기 때문에 큰 상관이 없음
• 그러므로 바로 시간 복잡도 비교하는 것이 좋음

최빈값 첫번째 시간복잡도

• alphabet_array 의 길이 X 대입 연산 1번 = 26 X 1
• alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번) = 26 X N X 2
• alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번) = 26 X 3
• 즉, 26 X ( 1 + 2 X N + 3 ) = 52N + 104

for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
     occurrence = 0                  # 대입 연산 1번 실행
     for char in string:             # string 의 길이만큼 아래 연산이 실행
         if char == alphabet:        # 비교 연산 1번 실행
             occurrence += 1         # 대입 연산 1번 실행 

     if occurrence > max_occurrence: # 비교 연산 1번 실행
         max_alphabet = alphabet     # 대입 연산 1번 실행
         max_occurrence = number     # 대입 연산 1번 실행

최빈값 두번째 시간복잡도

• string의 길이 X (비교 연산 1번 + 대입 연산 2번)
• 대입 연산 2번
• alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
• 즉, N X (1 + 2) + 2 + 26 X (1 + 3) = 3N + 106

for char in string:  # string 의 길이만큼 아래 연산이 실행
    if not char.isalpha():  # 비교 연산 1번 실행
        continue
    arr_index = ord(char) - ord('a')  # 대입 연산 1번 실행 
    alphabet_occurrence_list[arr_index] += 1  # 대입 연산 1번 실행 

max_occurrence = 0  # 대입 연산 1번 실행 
max_alphabet_index = 0  # 대입 연산 1번 실행 
for index in range(len(alphabet_occurrence_list)):  # alphabet_array 의 길이(26)만큼 아래 연산이 실행
    alphabet_occurrence = alphabet_occurrence_list[index]  # 대입 연산 1번 실행 
    if alphabet_occurrence > max_occurrence:  # 비교 연산 1번 실행 
        max_occurrence = alphabet_occurrence  # 대입 연산 1번 실행 
        max_alphabet_index = index  # 대입 연산 1번 실행 

1. 뒤에 상수는 버리고 N만큼 시간 작동한다고 말하기
2. 공간을 희생해서라도 시간복잡도 좋게 만들기

:: ✍ 점근표기법

빅오표기법 – 최악의 성능 나올 때 어느정도 연산량이 걸릴지
빅오메가 표기법 – 최선의 성능이 나올 때 까지 어느 정도의 연산량이 걸릴지

빅오 O(N)이면 빅오메가는 Ω(1)

• 알고리즘 성능을 수학적으로 표기
• 알고리즘 효율성 평가 방법
• 어떤 함수의 증가 양상을 다른 함수와 비교로 표현하는 방법
• N정도라고 칭하며 분석했던 것이 점근표기법의 일종

배열에서 특정요소 찾기

• 특정 숫자 존재한다면 true, 아니라면 false
• 배열을 돌면서 비교

input = [3, 5, 6, 1, 2, 4]


def is_number_exist(number, array):
    for element in array:  # array의 길이만큼 아래 연산 실행
        if number == element: # 비교 연산 1번 실행
            return True # N * 1 = N만큼

    return False


result = is_number_exist(3, input)
print(result)

N번만큼의 시간복잡도를 가짐
운이 좋으면 1번의 연산으로 답을 찾을 수 있지만,
찾고자 하는 것이 제일 마지막에 있다면,
마지막 원소 끝까지 찾다가 겨우 결과값 반환하게 됨

알고리즘 성능은 항상 동일한 것이 아니라 입력값에 따라 달라질 수 있는 것

• 거의 모든 알고리즘은 빅오표기법으로 분석
  • 개발자는 항상 최악의 경우를 대비해야하기 때문에

꼭 기억해야할 것

1. 입력값에 비례해서 얼마나 늘어날지 파악할 것
   • 1? N? N2?
2. 공간보다는 시간복잡도를 더 줄이기 위해 고민할 것
3. 최악의 경우 얼마나 시간 소요될지 고민할 것

:: ✍ 알고리즘 더 풀어보기

곱하기 or 더하기

다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 
왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 
숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 
결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 

(단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.)

• 모두 곱하는 것보다는 1이나 0과 같은 숫자는 더하는 것이 좋음
• ∴ 1이하는 더하고 나머지는 곱하기
• 0 + 3 X 5 X 6 + 1 X 2 X 4

input = [0, 3, 5, 6, 1, 2, 4]


def find_max_plus_or_multiply(array):
    multiply_sum = 0 # 0으로 설정했기 때문에 여기도 고려해야 함 
    for num in array:
        if num <= 1 or multiply_sum <= 1:
            multiply_sum += num
        else:
            multiply_sum *= num
    return multiply_sum


result = find_max_plus_or_multiply(input)
print(result)

위 함수의 복잡도는 O(N) = N
함수 구문 하나하나를 보지 않더라도, 1차 반복문이 나왔고, array 의 길이 만큼 반복하기 때문

반복되지 않는 문자

다음과 같이 영어로 되어 있는 문자열이 있을 때, 
이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 
만약 그런 문자가 없다면 _ 를 반환하시오.

• 최빈값 구하기와 동일하게

input = "abadabac"


def find_not_repeating_character(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))
			# 알파벳으로 전환해야하기 때문에 index 그대로 넣으면 안됨
            
    # print(not_repeating_character_array) 
	# 여기서 하면 알파벳 순서대로 반환, c와 d가 모두 다 나옴 


    for char in string: # 알파벳 순서가 아닌 들어온 문자열 순서에 맞게 반환
        if char in not_repeating_character_array:
            return char

    return "_"


result = find_not_repeating_character(input)
print(result)

항상 고민할 것

1. 문제가 찾는 조건이 어떤 것인지
2. 내가 구현한 것은 어떤 조건을 통해 값을 내려주는 것인지

:: ⭐ 문제가 이해가지 않을 때

1. 바로 코드 작성하기 보다는 문제의 다른 예시를 떠올리며 규칙성 생각해보기
2. 배웠던 자료구조를 활용하면 어떨지 생각해보기
3. 문제 특징 하나하나 글로 적어보기

:: 🤢 숙제

정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

input = 20


def find_prime_list_under_number(number):
    prime_list = []

    for n in range(2, number + 1):
        for i in prime_list:
            if n % i == 0 and i * i <= n:
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

0과 1로만 이루어진 문자열이 주어졌을 때, 
이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 
할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 
뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 

예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 
한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 
주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0
    count_to_all_one = 0

    if string[0] == '0':
        count_to_all_one += 1
    elif string[0] == '1':
        count_to_all_zero += 1

    for i in range(len(string) - 1):
        if string[i] != string[i + 1]:
            if string[i + 1] == '0':
                count_to_all_one += 1
            if string[i + 1] == '1':
                count_to_all_zero += 1

    return min(count_to_all_one, count_to_all_zero)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

2주차 배울 내용 미리보기

어레이와 링크드리스트

• 어레이
  • 순차적으로 데이터 저장
• 링크드리스트
  • 다음 node라고 불리는 공간에 데이터 저장
  • 그 다음 공간을 지목하는 포인터라는 공간이 있음

이진탐색과 재귀 함수

• 이진탐색
  • 반을 쪼개고 탐색하고, 반을 쪼개고 탐색하는 방식
• 순차탐색
  • 각각 하나하나하나 탐색
• 재귀함수
  • 자기 자신을 부르는 함수

:: ✍ 어레이와 링크드리스트

Array – 배열

• 캡슐호텔
• 배열의 크기는 정해진 데이터 공간이기 때문에 한번 정해지면 바꿀 수 없음
  • 소녀시대 8명 전원 숙박
• 배열은 각 원소에 즉시 접근 가능
  • 웰컴 드링크 전달
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 함
  • 서현 자리이동
• 원소 새로 추가하려면 새로운 공간 할당해야 함
  • 매니저 오니 방 하나달라함, 방 9개짜리 새로 건설
• 원소를 새로 추가하기에는 매우 비효율적인 자료구조

Linked List

• 화물열차
• 크기가 정해지지 않은 데이터의 공간이므로 연결고리만 이어주면 자유자재임
• 특정원소에 접근하려면 연결고리 따라 탐색해야 함
  • 맨 끝 우편 칸으로 이동
• 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됨
  • 흑연칸 넣고 밀가루칸 버리기

연결고리 : 포인터
화물칸 : 노드

Array와 LinkdeList 차이점

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

파이썬의 배열은 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조

:: ✍ 클래스

• 파이썬 생성자 함수는 무조건 init
• self는 자기 자신을 의미
• 클래스 내부의 함수는 메소드(method) 라고함

class Person:
    # pass # 빈 클래스로 두겠다는 의미
    def __init__(self, param_name):  # self는 자기자신
        print("메렁", self)
        self.name = param_name  # name이라는 변수에 param_name 저장하겠다는 의미


    def talk(self):
        print("안녕하세요. 저는", self.name, "입니다.")

person_1 = Person("유재석")  # Person()은 Person클래스를 통해 새로운 객체를 만들겠다는 것
print(person_1.name)
person_1.talk()
print(person_1)
# <__main__.Person object at 0x000001EDF9ACEAD0> 주소값: AD0
## at 뒤는 객체 공간 주소값
person_2 = Person("박명수")
print(person_2.name)
person_2.talk()
print(person_2)
# <__main__.Person object at 0x000001EDF9ACEB30> 주소값: B30
## at 뒤는 객체 공간 주소값

:: ✍ LinkedList 구현 및 문제

솔직히 이해가 안되서 정리 안하면서 봄
내일 오전 중으로 다시 한번 더 보기

• 노드에 필요한 정보
  • 칸에 있는 데이터 뭔지
  • 다음 칸이 뭔지
• LinkedList 는 head node 만 딱 들고 있음
  • 맨 앞 칸만 가지고 있음 됨

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]

LinkdeList append 함수 만들기

• 노드들을 하나하나 치면 비효율적
  ∴ 링크드리스트로 해결
• 맨 뒤에 새로운 값 추가하려면 맨 뒤 노드까지 가야함
  1. head 따라 이동 but, head 변경할 수 없으니 cur이라는 변수에 this.head 추가
     • cur = this.head
  2. 이제 이동을 시키려면 this.head 추가한 cur의 다음으로 이동해야함
     • cur = cur.next
  3. 맨 뒤의 노드라는 소리는 cur.next가 None이라는 것

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)  # head 에 시작하는 Node 를 연결합니다.

    def append(self, value):     # LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결합니다.
        cur = self.head         
        while cur.next is not None: # cur의 다음이 끝에 갈 때까지 이동합니다. 
            cur = cur.next          
        cur.next = Node(value)


linked_list = LinkedList(5)
linked_list.append(12)
# 이렇게 되면 5 -> 12 형태로 노드를 연결한 겁니다!
linked_list.append(8)
# 이렇게 되면 5 -> 12 -> 8 형태로 노드를 연결한 겁니다!

모든 원소 출력하기

• 노드를 따라가며 값 출력해야 함
  1. head에 저장되어있는 노드를 cur 라는 변수에 담고, cur 의 data를 출력
  2. cur의 next 값을 cur 에 대입하고 그 값을 출력
  3. cur 이 None 이 아닐때까지 반복

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

append 함수 + 모든 원소 출력하기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

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

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.print_all()

원소 찾기

• 노드 따라가며 값을 찾아야함
  1. head에 저장되어있는 노드를 node 라는 변수에 담기
  2. count 라는 인덱스를 저장하기 위한 변수를 저장
  3. count 가 index 가 될 때까지 node의 next 값을 node 에 대입하고 count 를 증가
     (이 때, while 문 내부에서 1씩 더해주니까 작을때까지로 조건 넣음)
  4. node 를 반환

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

원소 추가

• next_node 라는 변수에 현재 노드와 연결된 노드 저장
  1. 현재 노드의 다음 노드를 새로운 노드와 연결
  2. 새로운 노드의 다음 노드를 이전에 저장해둔 노드에 연결

def add_node(self, index, value):
    new_node = Node(value)
    node = self.get_node(index - 1)
    next_node = node.next
    node.next = new_node
    new_node.next = next_node

원소삭제

• 포인터를 다음 다음 칸으로 연결
• 어느때나 -1하는 코드가 있으면 0의 경우 원하지 않는 동작하게 됨
  • 예외 처리 해줘야 함

def delete_node(self, index):
	if index == 0:
        self.head = self.head.next
        return
    node = self.get_node(index - 1)
    node.next = node.next.next

:: ✍ 링크드리스트 문제

Q.  다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오. 

	예를 들어 아래와 같은 링크드 리스트를 입력받았다면,
	각각 678, 354 이므로 두개의 총합
	678 + 354 = 1032 를 반환해야 한다.

	단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.

• 헤드 따라가며 자릿수 맞게 +
• 자릿수에 맞게 더하기 위해 총액에서 10을 곱한 다음에 현재 노드의 값 더하기

linked_list_1 = [6] -> [7] -> [8]
linked_list_2 = [3] -> [5] -> [4]

def get_linked_list_sum(linked_list_1, linked_list_2):
		sum_1 = 0
    head_1 = linked_list_1.head
    while head_1 is not None:
        sum_1 = sum_1 * 10 + head_1.data
        head_1 = head_1.next

    sum_2 = 0
    head_2 = linked_list_2.head
    while head_2 is not None:
        sum_2 = sum_2 * 10 + head_2.data
        head_2 = head_2.next

    return sum_1 + sum_2
    
# 비슷한 변수, 중복되는 로직이 많으므로
# 아래 와 같이 하면 코드 간결성 높아짐

def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = _get_linked_list_sum(linked_list_1)
    sum_2 = _get_linked_list_sum(linked_list_2)

    return sum_1 + sum_2


def _get_linked_list_sum(linked_list):
    sum = 0
    head = linked_list.head
    while head is not None:
        sum = sum * 10 + head.data
        head = head.next
    return sum

요세푸스 문제