Python Algorithm Interview 01 - 기초

파이썬 알고리즘 인터뷰 1~4장을 학습하며 작성한 글입니다.

Python의 특징

Python을 선택한 이유이자 장점

1. 짧은 코드

• 실제 카카오 공채 코딩 테스트에서 평균적으로 Java는 C++보다 5~6라인, Javascript는 Java에 비해 10라인, Python은 Javascript보다 짧았다. Python의 라인 수은 C++의 60% 수준이다.
• 여러 코딩 테스트를 경험해 보니, 주어진 시간 내에 문제를 풀어야 해 코드를 작성하는 시간도 중요하다고 느꼈다.

2. 쉬운 난이도

• 처음 코딩은 파이썬으로 접했고, 비전공자로 간단한 문법만 알아도 쉽게 이해할 수 있었다.
• 혹시라도 면접에서 코드를 작성하거나 설명할 일이 있다면, 수도 코드를 대신해 사용하기 좋을 정도로 쉽다.

3. 높은 유연성

• Java나 C++과 달리 매번 자료형은 엄격하게 선언할 필요가 없다.
• 빠르게 알고리즘을 구현해야 하는 코딩 테스트에서 높은 유연성은 생산성에 큰 도움이 된다.

Python의 단점

1. 느린 속도

• 여러 언어의 속도를 비교한 그래프에서 파이썬이 아래서 4번째이다.
• 동적 타이핑 언어
  • 개발자가 자료형을 정해주지 않아도, 자동으로 할당
  • 컴퓨터의 연산 증가로 속도 저하 

2. 지원하지 않는 경우

• 현재 다니고 있는 NHN을 비롯해 배달의민족 등 일부 기업에서는 Python으로 응시가 불가하다.
• SSAFY 과정 중 Java로 알고리즘 공부를 했기에 모의 A형, NHN 코딩테스트에는 Java로 응시했다.
• 희망했던 기업 대부분이 Python을 지원했기에 큰 문제는 아니라 판단했다.

유용한 기초 문법

숫자 최댓값

sys 라이브러리 사용

sys.maxsize

float의 최댓값

float("inf")

math의 무한대

math.inf  # python 3.5 이상만 가능

입력받기

표준 입력

input()

sys 라이브러리

sys.stdin.readline()

빅오 big-O

• 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법
• 시간 복잡도와 공간 복잡도를 표현

표기법	설명
O(1)	입력값이 커져도, 실행 시간은 일정
O(logn)	이진 검색
O(n)	선형 시간 알고리즘, 리스트의 최대 혹은 최솟값 찾기
O(nlogn)	병합 정렬 등의 효율적인 정렬 알고리즘
O(n²)	버블 정렬 등의 비효율적인 정렬 알고리즘
O(2ⁿ)	피보나치 수를 재귀로 계산
O(n!)	입력값이 조금만 커져도 다항 시간 내 계산 어렵

분할 상환 분석
최악의 경우만 고려하는 것이 지나치게 비관적이라는 이유로 등장.
최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도 계산.

동적 배열의 더블링
기존 할당된 배열 크기를 초과해 데이터를 추가한 경우, 기존 크기의 두 배에 해당되는 배열을 선언하고 기존 데이터를 옮기는 방식

시간 복잡도

• O(n³)이고, n이 500 : 1초
• O(n²)이고, n이 2,000 : 1초
• O(nlogn)이고, n이 100,000 : 1초
• O(n)이고, n이 10,000,000 : 1초

공간 복잡도

• int list[1,000] : 4KB
• int list[1,000,000] : 4MB
• int list[2,000][2,000] : 16MB

Python의 자료형

숫자

• Python3부터 int가 임의 정밀도 지원 (고정 정밀도 정수형은 미지원)
• 정수형은 int와 bool로, bool은 int의 서브 클래스

임의 정밀도 정수형
무제한 자릿수를 제공하는 정수형. 정수를 여러 숫자의 배열로 간주.
계산 속도 저하. 단순한 구조. 잘못된 계산 오류 방지

시퀀스

• 순서가 있는 나열
• 가변(str, tuple, bytes), 불변(tuple)

객체

• 모든 것이 객체
• 불변 객체 bool, int, float, tuple, str
• 가변 객체 list, set, dict

 is 는 객체의 주소값, id()를 비교
 == 은 값을 비교 (None은 값 자체가 없기에, ==로 비교 불가)

그 외

• 매핑: 키와 자료형으로 구성 (dictionary)
• 집합: 중복된 값을 갖지 않는 자료형, 순서 X
• Python은 원시 타입의 속도를 포기하고, 기능성과 편의성을 택한 언어