파이썬 코딩 :: 파이썬 알고리즘, 시간복잡도, Linked list, 이진탐색, 재귀, 백준_TIL#13

■ JITHub 개발일지(TIL : Today I Learned) 13일차

---

□  TIL #13 ::

파이썬 알고리즘, 시간복잡도, 링크드 리스트, 이진탐색, 재귀, 백준

---

1. 파이썬 알고리즘

 1) 알고리즘의 기본 개념

  · 알고리즘이란? 

    어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합이다.

    여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.

 

  · 알고리즘을 다루려면 컴퓨터의 연산방식과 자료 관리 방식을 이해하여야 한다.

   → 시간복잡도 : 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말한다. 시간이 적게 걸리는 알고리즘일 수록 좋기 때문에, 코드 입력값이 늘어나도 계산에 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘인 것이다. 입력값(array)의 길이는 보통 N으로 표현하는데 중첩되어 반복할 수록(N의 x제곱...) 시간은 기하급수적으로 늘어나게 된다.

   → 공간복잡도 : 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다. 저장하는 데이터는 공간을 차지한다. 시간복잡도와 마찬가지로 입력값이 늘어나도 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.

   → 하지만 대부분 알고리즘의 성능은 공간이 아닌 '시간 복잡도'에서 결정되기 때문에 '시간 복잡도'에 더 유의해야 한다.

 

  · 점근표기법(Asymptotic notation)

    알고리즘의 성능을 수학적으로 표기하는 방법, 또는 알고리즘의 '효율성'을 평가하는 방법을 말한다.

    점근표기법의 종류로는 빅 오(Big-O) 표기법, 빅 오메가(Big-Ω) 표기법이 있다. 빅 오 표기법은 최악의 성능이 나올 때, 빅 오메가 표기법은 최선의 성능이 나올 때 어느 정도 연산량이 걸릴지를 표기하며, 보통 보수적인 표기법 빅 오 표기법을 많이 사용한다.

 

  · 어레이(Array)

    크기가 정해져 있는 데이터의 공간이다. 

rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"]

 

  · 링크드 리스트(Linked List)

    기차의 객실이 연결되는 것 처럼, 각 칸에 값이 있고, 다음 칸과 연결이 되어있는 구조이다.

    크기가 정해지지 않은 특성이 있어, 연결고리로 이어주면 늘어나고 줄어들 수 있다.

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

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

 

  · 이진 탐색

    업/다운 게임을 할 때처럼, 특정 숫자를 순서대로 정렬된 Array에서 찾을 때 전체 길이의 중간값을 기준으로 값의 크기를 비교하는 작업을 반복함으로써 탐색속도를 빠르게 하는 것을 말한다. (↔ 순차탐색)

 

  · 재귀 함수

    재귀(Recursion)는 어떤 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 즉, 여기서는 함수가 자기자신을 호출하는 것을 말한다. 재귀함수는 특정 구조가 반복되면서 문제가 축소되는 모습이면 사용할지 검토해봐야하며, 사용시에는 반드시 탈출조건을 주의해야 한다. 탈출조건을 제대로 주지 않으면 무한히 반복하는 오류가 발생할 수 있다. 

2. 파이썬 복습

변수를 선언할 때 메모리 주소가 생성된다. 

아래와 같이 변수를 반복 호출할 경우, 변수가 있는 메모리 주소는 계속 바뀐다.

  id : 메모리 주소

  hex : 16진수

  bin : 2진수로 표현 (32칸이 나옴)

 

  - choice() : 아무 원소를 하나 뽑아주는 함수이다. random 모듈을 임포트해서 사용할 수 있다.

3. 백준 알고리즘

  · 재귀

    마침 알고리즘을 공부하고 있던 도중 재귀문제를 만났다.

    그런데 아래 세 개의 문제는 문제 이해부터가 많이 어렵다. 문제에 대한 이해가 선행되는 것이 필요하다.

    풀이는 하나하나 다시 정리해서 포스팅 할 예정이다. (*근데 예상보다 정답률이 높은 것 같다)

---

■ TIF :: Today I Felt

 - 파이썬 문법 내용을 활용해서 다양한 알고리즘 문제들을 본격적으로 공부하고 있다.

 - 알고리즘 문제를 많이 푸는 것도 도움이 많이 되겠지만, 아직은 부족한 문법에 대한 내용을 더 다지는 것이 필요한 것 같다.

 - 알고리즘 문제는 직접 싸매고 풀면 시간이 엄청 걸린다... 하루 종일 갈 것 같을 때도 있다. (이럴땐 금방 지친다.)

 - 다양한 풀이들을 볼 때는 배우는 점도 훨신 많은 것 같다. 내 것으로 되기가 어려울 뿐...