📖 오늘의 학습

• 자료구조 : 배열
• 알고리즘 : 정렬, 탐색, 재귀
• 특강 : 코딩테스트 & 코딩인터뷰에 관한 특강

---

자료구조

1. 선형배열 (Linear Arrays)

• 데이터를 선형으로 저장
• 인덱스(index)를 통해서 배열에 있는 요소에 접근
• 자료형이 하나로 고정되어 있음

Python의 List

• 다른 언어랑은 달리 자료형에 제약이 없고 변수 선언 시 길이를 정해주지 않아도 됨
• 아래 두 연산은 모두 끝에 원소를 붙이는 것이기 때문에 포인터 이동이 필요하지 않아 연산이 빠름
  .append(e) : 맨 끝에 원소 하나를 붙인다
  .pop() : 맨 끝의 원소 하나를 꺼낸다
• 아래 연산들은 인덱스를 정하고 포인터 이동이 일어나기 때문에 배열의 길이에 비례하여 시간이 걸림
  .insert(i, e) : i위치에 e원소를 넣는다
  del 삭제할원소 : 원소를 삭제한다
  .index(e) : 원소의 인덱스 반환한다.

알고리즘

1. 정렬 (Sort)

• Python의 List는 정렬 내장함수sorted()와 List의 정렬 메소드.sort()를 제공한다.
  - sorted() : 정렬 대상인 List를 변경하지 않고 새로운 정렬된 List를 반환
  - .sort() : 정렬 대상을 정렬된 List로 변경함
  

정렬기준 변경

• key 파라미터에 정렬 기준을 설정한다. 대부분 lambda로 설정함
  reverse True일 때 내림차순, False일 때 오름차순(default값)

*cities 라는 도시 이름 리스트가 있다고 가정함

# 1. 도시이름 길이로 오름차순 정렬
cities = sorted(cities, key=lambda x: len(x))

# 2. 도시이름 길이로 내림차순 정렬
cities = sorted(cities, key=lambda x: len(x), reverse=True)

• hash에 해당하는 Python의 dict가 list의 원소로 있을 때도 동일하게 정렬이 가능하다.

*cities 라는 {도시 이름:인구 수} 딕셔너리가 있다고 가정함

# 1. 도시의 인구 수로 오름차순 정렬
cities = sorted(cities, key=lambda x: x['population'])

# 2. 도시의 인구 수로 오름차순 정렬 (x 앞에 -(마이너스) 붙여주면 됨!)
cities = sorted(cities, key=lambda x: -x['population'])

2. 탐색 (Search)

선형탐색 (Linear Search)

• 순차적으로 배열에 있는 모든 원소를 탐색

이진탐색 (Binary Search)

• 모든 원소가 정렬이 되어있다는 가정 하에 탐색이 유효함
• 최소, 최대값의 중간값을 설정하고 이와 비교한 후 반 씩 잘라내서 비교함
• 선형탐색보다 훨씬 빠르다

👉 이진탐색이 선형탐색보다 빠르지만 정렬이 되어야한다는 조건이 있기 때문에 정렬에 드는 비용이 크거나 여러번에 배열을 탐색할 것이 아니라면 선형탐색이 더 나을 때도 있다.

3. 재귀 (Recursive)

• 같은 알고리즘을 반복적으로 사용하여 문제를 푸는 방식
• 종결조건(trivial case)를 반드시 명시하여야 함. 그렇지 않으며 무한루프
• 직관적으로 이해하기 좋지만 효율이 다른 알고리즘에 비해 그닥 좋지 않음

재귀 알고리즘 이용한 이분탐색

def recursive_bin(L, x, l, u):
    if l > u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return recursive_bin(L, x, l, mid - 1)
    else:
        return recursive_bin(L, x, mid + 1, u)

4. 알고리즘의 복잡도

• 시간복잡도 : 문제풀이에 소요되는 시간이 얼마나 걸리는가?
  - 주로 big-O notation으로 표기함
• 공간복잡도 : 문제풀이에 소요되는 메모리가 얼마인가?

---

📝 주요메모사항

1. Function과 Method의 차이

Function

• 독립적으로 호출이 가능
• Object에 종속되어 있지 않아 class를 선언하지 않아도 됨
• 파라미터로 주어진 데이터만 사용이 가능

Method

• 클래스명을 명시하여야 호출이 가능함
• Method가 속한 클래스의 인스턴스의 값들에 접근이 가능함

2. 코딩테스트

• 최소한의 문제해결 능력을 확인하기 위한 수단
• 문제를 분석하고 해결방법 착안 -> 코드로 구현하면 끝!
• 주 목적은 코딩테스트를 준비하는 과정에서 공부하게 되는 것들(자료구조, 알고리즘, 클린코드 등등)
• 악기 다루는 것과 같아 반복적인 학습하면 된다 (너무 무서워하지 말자~)

---

😵 공부하면서 어려웠던 내용

• 재귀알고리즘은 매번 알고리즘을 공부할 때마다 마주치지만 직관적으로 아는 내용을 정확히 풀어서 코드로 구현하는 것이 어려웠다.
• big-O notation을 알고는 있었지만 그동안은 문제를 풀면서 대략적으로만 떠올렸었는데 코드의 효율성을 높이려면 좀 더 정확한 복잡도를 계산해야겠다고 느꼈다.