TIL 22.11.10 / 알고리듬알고리즘알고리thㅡㅁ

쓰옹·2022년 11월 10일

개발자를 향해~~TIL✍

목록 보기

10/87

알고리즘 2주차 수업
아무리 들어도 이해가 잘 안된다.
이론 하나에 하루 써야될것같은데
진도도 빼야되고
주말에 열심히 다시 해봐야겠다

소수 구하기 알고리즘 - 다시 이해가 필요

자료구조

자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. [위키백과]

자료구조 선택 시 고려사항:
삽입시각, 삭제시간, 검색시간, 정렬여부

Array & Linked list

: 선형 자료구조 (linear data structure)

Array 배열

유사한 유형의 데이터를 저장하는 데 사용
크기가 정해진 데이터의 지정 공간. 바꿀 수 없엄
원소: 배열 내 데이터
인덱스: 원소의 순서. 0부터 시작
인덱스를 이용해 즉시접근 가능 == 상수 시간 내에 접근 == $O(1)$ 내에 접근
원소 삽입 or 삭제를 하려면 저장 위치가 연속적이고 고정적이기 때문에
원소 하나하나 다 옮겨야 함
데이터 추가: 새로운 메모리 공간을 할당받아야 함 다시 맨들어야된다 뭐 이런..그런거지
*코딩에서 변수를 옮길 때는 한 번에 하나씩 가능
->최악: $O(N)$ 의 시간복잡도를 가짐

Linked list (리스트)

저장해야 할 데이터의 양을 알 수 없는 경우 사용
크기가 정해지지 않은 데이터의 공간
포인터: 연결고리
노드: 데이터 저장 공간
-필요 정보: 데이터, 포인터
-head node: 맨 처음 node
특정 원소에 접근하려면 포인터를 따라 순차적으로 접근해야함 - > 최악: $O(N)$ 의 시간복잡도를 가짐
원소 삽입, 삭제를 하려면 앞 뒤의 포인터만 변경하면 됨
데이터 추가: 노드만 추가하면 됨
리스트의 크기는 원소 삽입, 삭제에 따라 확대되기도 축소되기도 함
-> $O(1)$ 의 시간복잡도

Array vs LinkedList

	Array	Linked List
특정 원소 조회	$O(1)$	$O(N)$
삽입/삭제	$O(N)$	$O(1)$
데이터추가	새로운 메모리 공간 할당	노드만 추가
정리	데이터에 접근하는 경우가 빈번한 경우	삽입과 삭제가 빈번한 경우

파이썬의 [] list는 array로 구현되어 있지만
동적 배열을 사용해서 배열 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계했다!
파이썬의 배열은 링크드리스트로 쓸 수도 있고 배열로도 쓸 수 있게 만든 효율적인 자료구조다
*동적 배열(dynamic array)은 프로그래밍에서 크기가 고정되지 않은 배열을 의미한다.

링크드리스트 구현

# 클래스 사용하여 링크드리스트 구현
class Node:
    def __init__(self, data): 
        self.data = data
        self.next = None   #노드의 필요 항목: 데이터와 포인터
                           #처음엔 포인터가 없으니 None으로

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)  #클래스 Node의 값을 링크드리스트의 헤드(처음 원소)로 한다

    def append(self, value):   #리스트 붙이는 함수
        cur = self.head        #변수 cur를 헤드부터 시작해서 
        while cur.next is not None:   #포인터가 없는 마지막 항목에 다다를 때까지
            cur = cur.next     #해서 마지막 cur에 새로운 값을 붙여
        cur.next = Node(value)

    def print_all(self):    #노드 값 다 뽑는 함수
        cur = self.head   #역시 헤드부터 시작
        while cur is not None:   #끝까지 도는데
            print(cur.data)  #노드의 데이터 값을 뽑아
            cur = cur.next  #그럼 다음걸로 가서 또 뽑고뽑고뽑고 cur가 None일 때까지 뽑아

    def get_node(self, index):  #노드 찾기
        node = self.head      #역시 시작은 헤드지
        count = 0             #카운트: 인덱스를 저장하기 우히ㅏㄴ 변수
        while count < index:  #카운트가 인데스가 될 때까지
            node = node.next  #다음 노드를 확인하고
            count += 1       #카운트 증가
        return node          #노드 반환

    def add_node(self, index, value):  #원소추가
        new_node = Node(value)         #추가할 노드는 데이터를 갖고있지
        node = self.get_node(index)    #추가할 위치의 노드를 찾아서
        next_node = node.next          #그 노드의 다음값을 변수로 정해놓고
        node.next = new_node           #추가할 위치의 노드의 다음 값에 새 노드를 넣고
        new_node.next = next_node      #새노드의 다음 노드를 원래 추가할 위치에 있던 노드의 다음값을 넣어

    def delete_node(self, index):     #삭제
        if index == 0:                #예외처리) 인덱스가 0일 경우 
            self.head = self.head.next #old헤드를 삭제해야하므로 old헤드다음노드를 new헤드로 설정
            return

        node = self.get_node(index -1) #삭제할 위치의 노드를 찾고
        node.next = node.next.next     #다다음거랑 연결해


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
linked_list.add_node(0, 6)
linked_list.delete_node(1)
linked_list.print_all()

클래스

: 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념
-생성자(Constructor)
:생성시에 호출되는 함수
: 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있다
- (): 생성자(constructor)
- 파이썬에서 생성자 함수의 이름은 __init__ 으로 고정되어 있음

이진(binary)탐색

: 범위를 반으로 줄여 탐색 숫자 탐색

일정한 규칙으로 정렬되어 있을 때만 가능함

#배열에서 최솟값과 최댓값의 중간을 찾고
def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) -1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if array[current_guess] == target:  #타겟이랑 같으면 바로 결과
            return True
        elif array[current_guess] < target:  #타겟보다 작으면
            current_min = current_guess + 1 #중간값에 1을 더한걸 최솟값으로 해서 다시 중간을 찾아
        else:                               #타겟보다 크면
            current_max = curren_guess -1  #중간값에서 1뺀걸 최댓값으로 잡고 다시 중간을 찾지
        current_guess = (current_min + current_max) // 2
#그렇게 타겟이랑 중간값이 같을 때 True
    return False  #아예 없다 하면 False

//: 나눴을 때 소수점을 버려주고 자연수로만 나오게 함

재귀함수

:자기 자신을 호출

재귀함수는 끝나는 지점을 정해야한다. 탈출조건이 있어야함

def count_down(number):
    if number < 0:  #탈출조건
        return 
    print(number) # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!


count_down(60)

팩토리얼 !

# n! = n * (n-1) * (n-2) *...* 1
# (n-1) * (n-2) *...* 1 = (n-1)!
# n! = n * (n-1)!

def factorial(n):
    if n == 1:  #역시 탈출조건
        return 1
    return n * factorial(n-1)

회문 검사

회문(palindrome): 거꾸로 읽어도 똑같음 ex)토마토, 기러기, 스위스, 역삼역, ~~우영우(?)~~

input = "abcba"

def is_palindrome(string):
    n = len(string)
    for i in range(n):
        if string[i] != string[n- 1 -i]:
            return False

    return True

print(is_palindrome(input))

#재귀함수 이용하여 코드 작성
input = "abcba"

def is_palindrome(string):
  if len(string) <= 1:
      return True

  if string[0] != string[-1]:
      return False

  return is_palindrome(string[1:-1])
#abcba
#bcb
#c
print(is_palindrome(input))