[Pthython3 코딩테스트 (1)] Intro & Array(배열)

자료구조: 데이터를 저장하고 관리하는 방식

알고리즘: 문제 해결 방법

• 자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화 → BFS, DFS 등등
• 알고리즘 평가 기준
  • 시간 복잡도
  • 공간 복잡도
  • 구현 복잡도
• 실행시간(Running Time)
  • Big-O : 점근 표기법

---

코딩테스트 풀이 순서

1. 문제 이해하기
   • input, output 확인
     • input 값의 특징(정수인가? 값 크기 범위는? 마이너스도 되는건가? 소수인가? 자료형은 문자열인가?)
     • output 값의 특징 (내가 어떤 값을 반환해줘야 하는지, 정해진 형식대로 반환하려면 어떻게 구현할지)
   • input size N 확인
     • 시간복잡도를 계산하기 위한 input size N 또는 M이 무엇인지 확인
   • 제약조건 확인
     • 시간복잡도 제한이 있는지 확인
     • 내가 선택할 수 있는 알고리즘이 무엇이 있는지
   • 예상할 수 있는 오류 파악
     • 상황을 가정하면서 예쌍할 수 있는 오류를 파악한다
     • 입력값의 범위, stack overflow 등
2. 접근 방법
   • 시간복잡도 파악하기
   • 직관적으로 생각하기
     1. 보통 완전탐색으로 시작
     2. 문제 상황을 단순화하여 생각하기
     3. 문제 상황을 극한화하여 생각하기
   • 자료구조와 알고리즘 활용
     1. 대놓고 특정 자료구조와 알고리즘을 묻는 문제도 많음
     2. 자료구조에 따라 선택할 수 있는 알고리즘을 문제에 적용
   • 메모리 사용
     1. 시간복접도를 줄이기 위해 메모리를 사용하는 방법
     2. 대표적으로 해시테이블
3. 코드 설계
   • 코드 설계를 해봤는데, 시간 복잡도가 n^8이 넘을 것 같다고 하면, 빠르게 다른 방법을 찾아봐야 한다.
4. 코드 구현

# 제약조건이 있는 문제

• 정답만 도출하는 문제 vs 시간 복잡도를 고려해야 하는 문제 → 주어진 n 값의 범위를 보고 판단하기

---

LIST

• Array list (배열 기반)
  • Static Array
  • Dynamic Array
• Linked list(Node 기반)

배열의 특성

1. 고정된 저장 공간(fixed-size)
2. 순차적인 데이터 저장(order)

배열: 선언 시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조

Random Access

메모리에 저장된 데이터에 접근하려면 주소값을 알아야 한다. 배열변수는 자신이 할당받은 메모리의 첫 번째 주소 값을 가리킨다. 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능하다.

⇒ 이를 direct access 또는 random access라고 부릅니다.

아무리 긴 배열이더라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있다.

→ 즉, O(1)의 시간복잡도를 갖는다.

Linked List는 메모리상에서 연속적/순차적으로 저장되어 있지 않기 때문에 random access는 불가능하다. n번째 데이터에 접근하기 위해서 array는 1번의 연산만 해도 되지만(O(1)), Linked List는 n번의 연산을 해야 하기 때문에 시간복잡도는 O(n)이 된다.

Static Array의 한계

데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 효율적

But, 선언시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우, 공간이 남아 있지 않아 문제가 발생할 수 있다. 그렇다고 매번 크기가 큰 배열을 선언한다면 메모리 비효율이 발생한다.

→ 이런 문제점을 해결할 수 있는 것이 바로 dynamic array

Dynamic Array

동적배열(dynamic array)은 배열의 크기(size)를 변경(resizing)할 수 있는 배열

동적 배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고, 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열은 메모리에서 삭제(free)한다.

⇒ 이 과정을 resize라고 한다. resize를 한 칸씩 늘린다면 비효율적이므로 일반적으로 2배 큰 크기로 resize 한다. 이를 더블링(Doubling)이라고 한다. resize 덕분에 데이터를 추가 저장할 수 있게 된다.

배열의 시간 복잡도

python의 List → Dynamic Array

배열의 다양한 활용

1. 반복문
2. Sort & Two Pointer
   1. Sort: 파이썬에서 Sort는 O(nlogn)의 시간 복잡도가 걸린다.
   2. Two Pointer: 두 개의 포인터를 통해서 문제를 풀이(주로 정렬과 함께 쓰인다)

 

https://inf.run/3hPE

코딩테스트 [ ALL IN ONE ] - 인프런 | 강의

위의 강의를 수강하고, 추후에 제가 공부할 때 참고하기 위해 정리한 내용입니다.