20230410 TIL - 자료구조, 알고리즘, 코딩테스트

ohyujeong·2023년 4월 10일
0

TIL

목록 보기
1/27
post-thumbnail

📖 오늘의 학습

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

자료구조

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'])
  • 순차적으로 배열에 있는 모든 원소를 탐색
  • 모든 원소가 정렬이 되어있다는 가정 하에 탐색이 유효함
  • 최소, 최대값의 중간값을 설정하고 이와 비교한 후 반 씩 잘라내서 비교함
  • 선형탐색보다 훨씬 빠르다

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

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을 알고는 있었지만 그동안은 문제를 풀면서 대략적으로만 떠올렸었는데 코드의 효율성을 높이려면 좀 더 정확한 복잡도를 계산해야겠다고 느꼈다.
profile
거친 돌이 다듬어져 조각이 되듯

0개의 댓글