[알알알] week02 개념

스파르타코딩클럽  - 알고보면알기쉬운알고리즘 내용 정리

 

배열(Array) - 캡슐호텔

(1) 특징

• 크기가 정해진 공간. 바꿀 수 없다
• 즉시 원소에 접근 가능(상수 시간 내에 접근 가능 On(1). room[0] < 0부터 시작하는 '인덱스' 
• 원소를 삽입/ 삭제할 경우 모든 원소를 옮겨야 함. 배열의 길이만큼 옮겨야 함 => O(N) 복잡도를 가짐.
• 원소를 새로 추가하려면, 새로운 공간을 할당해야 함. = 비효율적

링크드 리스트(Linked list) - 화물 열차

(1) 특징

• 리스트 - 크기가 정해지지 않은 데이터 공간. 연결고리로 이어주면 자유자재 늘어날 수 있음
• 연결고리를 따라 탐색. 최악의 경우 모든 칸 O(N)의 시간 복잡도
• 연결고리 - 포인터, 화물칸 - 노드
• 삽입/ 삭제의 경우 앞 뒤 포인터만 변경하면 됨 => O(1)의 시간 복잡도
• head node만 들고 있음 next를 통해서 다음 노드 접근해야함!

(2)

링크드 리스트 원소 추가

1. 현재 노드의 다음 노드를 새로운 노드와 연결합니다.

새로운 노드의 다음 노드를 새로운 노드와 연결합니다.

현재 노드를 구하기 위해서는 get_node를 이용하기.

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
삽입 삭제	O(N)	O(1)
데이터 추가	기존 공간 다 차면 새 메모리 할당 받아야함	동적 추가 가능
정리	데이터 접근 용이	삽입 삭제 용이

클래스

같은 속성, 기능을 가진 객체를 묶어서 정의할 수 있다. 

클래스 (동물) - 객체 (강쥐)

 

__int__ (생성자) :  객체 생성시 데이터 넣거나 원하는 행동 실행가능

class Person:

          def __init__(self, param_name): #self : 객체 자기자신

                 print("hihihi", self)

                 self.name = param_name #객체의 name에 변수 저장

 

        def talk(self): # 클래스 내부 함수 = 메소드(method)

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

 

이진 탐색

업다운 게임: 최소값 + 최대값 // 2와 타겟 비교

만약 타겟이 시도값보다 크다면 최소값은 시도값 + 1

시도값보다 작다면 최대값은 시도값 - 1

 

이진 탐색의 시간 복잡도

1번 탐색 = N / 2

2번 탐색  = N / 3

...

k번 탐색 = N / k

 

N / 2^k = 1 -> k = log2 N

이진탐색을 위해서는 시간 복잡도가 O(logN)만큼 걸린다 ! < 상수 제외함

 

재귀함수

자기자신을 참조하는 함수

간결하고 효율성 있는 코드 작성 가능!

하지만 무한정 돌아가니 탈출 조건을 만들어야 함!

 

팩토리얼

1부터 정수 N까지 정수를 모두 곱한 것!

Factorial(n) = n * Factorial(n-1) 

Factorial(n-1) = (n-1) * Factorial(n-2)

...

Factorial(1) 1

 

ex : 4 ! = 4 * 3* 2* 1 = 4* 3!

 

def factorial(n):

            if n == 1:

                  return 1

            return n * factorial(n - 1)

 

회문

토마토 등 맨끝과 맨 앞의 숫자가 같은 것.

abcba < 요것도!

 

def is_palindrome(string):

           return is_palindrome(string[1:-1])

 

탈출 조건

• 문자열의 길이가 1보다 작을 때(토마토면 "마"만 남을 경우)
• 맨 첫문자 != 맨 마지막 문자 (회문 아님)