[TIL] 자료구조/알고리즘 풀기 (1)

이원진·2023년 4월 10일
TIL데브코스알고리즘
0

데브코스

목록 보기
1/54
post-thumbnail

학습 주제

  1. 자료구조 & 알고리즘

  2. 선형 배열(Linear Array)

  3. [특강] 코딩 테스트 & 면접 대비

  4. 정렬(Sort) & 탐색(Search)

  5. 재귀(Recursive) 알고리즘

  6. 알고리즘의 복잡도


1. 자료구조 & 알고리즘

  • 자료구조: 데이터와 해당 데이터에 적용할 수 있는 연산의 집합

  • 알고리즘

    • 사전적 정의: 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합

    • 프로그래밍 관점에서의 정의: 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택


  • 문제마다 최적의 해법이 다르기 때문에 다양한 자료구조와 알고리즘을 아는 것이 중요


2. 선형 배열(Linear Array)

  • 배열: 같은 종류의 데이터를 순서대로 나열한 것

  • 파이썬에서는 리스트를 사용

    • 숫자뿐 아니라 모든 타입의 데이터 나열 가능

    • 서로 다른 타입의 데이터도 하나의 리스트에 나열 가능

    • 탐색: index(value)

    • 추가: append() / 추출: pop(index) / 삽입: insert(index, value)

      • pop()에 아무런 매개변수 없을 시 마지막 항목 추출

  • 인덱스는 0부터 시작


3. [특강] 코딩 테스트 & 면접 대비

  • 코딩테스트: 최소한의 문제 해결 능력 검증하기 위해 문제 제시

  • 코딩인터뷰: 직무에 필요한 배경지식을 갖췄는지 검증

    • 생각한 바를 논리적으로 올바르게 전달할 수 있는지 검증

  • 코딩 테스트 대비 방법

    1. 구현 능력 갖추기

    2. 기본적인 자료구조 이해

    3. 기초 알고리즘 및 시간/공간 복잡도 이해

    4. 현실 문제를 해결하기 위한 알고리즘 적용 해법 착안 사고 훈련

    5. 제한 시간 내에 오류 없이 코드 작성 및 디버깅할 수 있는 능력 훈련

      -> 결국, 문제를 많이 풀어봐야 함


  • 알고리즘을 외우려고 하지 말고, 생각의 흐름을 이해하고 따라가려고 해야 함

  • 짧은 코드가 빠른 코드를 의미하지 않으며, 작성한 코드가 어떻게 실행되는지 이해해야 함

  • 파이썬 내부적으로 동작하는 방식에 따라 같은 연산도 효율이 다를 수 있음


4. 정렬(Sort) & 탐색(Search)

  • 파이썬 리스트의 정렬

    1. sorted()

      • 내장 함수(built-in function)

      • 정렬된 새로운 리스트 반환

    2. sort()

      • 리스트의 메서드

      • 해당 리스트를 정렬

    • 역순으로 정렬
      ls.sort(reverse = True)

    • key와 lambda 함수를 사용해 정렬 기준 설정
      ls.sort(key = lambda x : len(x))

  • 문자열로 이루어진 리스트의 경우, 길이 순이 아닌 사전순으로 정렬

  • 선형 탐색(Linear Search)

    • 리스트의 길이에 비례하는 시간 소요(선형 시간, O(N))

  • 이진 탐색(Binary Search)

    • 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
      -> 크기 순으로 정렬되어 있다는 성질을 이용

    • 한 번 비교가 일어날 때마다 리스트를 반씩 줄임(divide & conquer)
      -> O(log N)

5. 재귀(Recursive) 알고리즘

  • 재귀: 하나의 함수에서 자신을 다시 호출해 작업을 수행하는 것

    • 생각보다 많은 문제를 재귀적으로 해결할 수 있음

  • 반복적으로 구현 가능한 문제는 재귀적으로도 구현 가능

  • 종료조건(trivial case)을 반드시 정의해야 함

    • 정의하지 않을 경우, 재귀 깊이(recursion depth) 관련 에러 발생할 수 있음

  • n! 을 구하는 문제는 반복적 혹은 재귀적으로 구현할 경우 시간복잡도가 O(N)이지만, "N(N + 1) // 2" 라는 수식을 이용할 경우 O(1)에 해결 가능

    • 수학적으로 접근했을 때 효율적으로 해결 가능한 경우도 있음

  • 재귀적 기법보다 반복적 기법이 시간복잡도 측면에서 효율적

    • 재귀는 호출하고 반환하는 데 추가적으로 시간이 소요되기 때문

  • 팩토리얼은 아래와 같이 라이브러리를 통해 간단하게 구할 수 있음

    from math import factorial
result = factorial(10)

6. 알고리즘의 복잡도

  • 복잡도: 코드가 얼마나 복잡한지가 아닌 자원을 얼마나 필요로 하는지를 의미

  • 시간 복잡도(Time Complexity)

    • 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

    • 최선의 경우, 평균, 최악의 경우 중 최악의 경우가 가장 중요

    • Big-O Notation으로 표현
      O(1), O(log N), O(N), ...

      • 계수보다는 차수가 중요

  • 공간 복잡도(Space Complexity)

    • 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

메모

  • 재귀적, 반복적으로 이진 탐색을 구현할 때 start와 end의 값이 같은 경우도 고려해야 함
    -> 즉, start > end 인 경우에 종료
profile
이원진
다음 포스트

[TIL] 자료구조/알고리즘 풀기 (2)

0개의 댓글