Problem Solve 정리 (플랫폼, Python)

해당 글은 `파이썬 알고리즘 인터뷰 (박상길 저)` 를 읽은 후 정리한 내용들을 축약한 내용임을 밝힙니다.

 

코딩 인터뷰

코딩인터뷰: 기술 직군 채용을 위한 기술 문제 중심의 개발 인터뷰

마이크로 소프트가 처음 개척한 것으로 알려져 있음.

 

코딩 인터뷰를 위한 온라인 테스트 플랫폼

• 해커랭크
  • 해외에서도 가장 유명한 기업들의 코딩 테스트 플랫폼
• 코딜리티
  • 영구에서 서비스하는 플랫폼, 좀더 코딩 테스트에 가까운 서비스.
• 리모트 인터뷰
  • 코딩 인터뷰에 특화된 플랫폼
• 프로그래머스
  • 국내 서비스, 주로 대기업 공채처럼, 특정 시간에 많은 인원이 대규모로 진핸하는 이벤트에는, 빠르게 장애 대응을 할 수 있는 국내 플랫폼이 많이 활용되는 편임.
• 백준
  • 국내 사이트, 코딩 테스트 플랫폼이라기 보다는 개인용 문제 풀이 서비스에 가까움
• 리트코드
  • 해외 사이트, 해외 개발자들이 PS를 많이 진행하는 플랫폼

각 플랫폼 별로 문제 풀이 정책, 답변 제출 방법등 에서 상이한 부분이 다수 존재하므로, 특정 회사의 코딩테스트를 보기 전에 미리 플랫폼을 파악하고, 문제풀이에 임하는 것이 좋다.

또한, 반복되는 코드들에 대해서는 자신만의 코드 스니펫을 관리하는 것이 여러모로 유리함.

 

파이썬에 대하여

네덜란드의 컴퓨터과학자 귀도 반 로섬(Guido Van Rossum)이 크리스마스 프로젝트로 새로 만들어낸 언어

원칙은 다음과 같았다.

1. 읽기 쉬워야한다.
2. 사용자가 원하는 모듈 패키지를 만들 수 있어야 한다. (이는 ‘pip’이라는 기능을 통해 사용할 수 있다.)

파이썬에 대한 깊은 이해가 필요하다.

딕셔너리의 순서가 유지된다라고 알고 있거나, 각종 자료구조에 대한 특성을 알지 못하는 경우에 고전을 면치 못할 수 있다.

알아두어야 할 문법 리스트

• 인덴트: 각종 IDE를 이용하면 쉽게 지킬 수 있다. 파이썬의 대표적인 특징이기도 한 인덴트는, 공식 가이드인 PEP 8에 따라 공백 4칸을 원칙으로 한다.
• 네이밍 컨벤션
• 타입 힌트
• 리스트 컴프리헨션
• 제너레이터
• range
• enumerate
• // 나눗셈 연산자
• print
• pass
• locals

파이썬 문법

파이썬은 모든것이 객체이다. 이중에서도 크게 불변 객체와 가변 객체로 구분할 수 있는데,

다음과 같다.

• 파이썬 자료형의 종류
  • 숫자
    1. 정수형
       1. 정수
       2. 불리언
    2. 실수
  • 매핑
    1. 딕셔너리
  • 집합
    1. 집합
  • 시퀀스
    1. 불변
       1. 문자열
       2. 튜플
       3. 바이트
    2. 가변
       1. 리스트

클래스설명불변 객체

클래스	설명	불변객체
bool	부울	O
int	정수	O
float	실수	O
list	리스트	X
tuple	리스트와 튜플의 차이는 불변 여부이며 이외에는 거의 동일히다. 튜플은 불변이므로 생성할 때 설정한 값은 변경할 수 없다.	O
str	문자	O
set	중복된 값을 갖지 않는 자료형	X
dict	딕셔너리	O

빅오, 자료형

빅오(O, big-O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

점근적 실행 시간( Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법이다.

여기서 말하는 점근적 실행 시간이란 n이 무한대에 가까워질 때, limit 함수의 실행시간 추이를 말한다.

따라서 관심의 대상은 ‘큰 입력’이다.

예) 비행기로 엄청난 양의 정보나르기, 컴퓨터로 엄청난 양의 정보 전송하기.

 

빅오 notation	종류
O(1)	해시 테이블의 조회 및 삽입
O(log n)	이진검색
O(n)	비정렬 리스트 최댓값, 최솟값 찾기
O(n log n)	병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘, 적어도 모든 수에 대해 한번 이상은 비교해야하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n logn)보다 빠를 수 없음.
O(n^2)	버블 정렬과 같은 비효율적인 정렬 알고리즘 등
O(2^n)	피보나치 수를 재귀로 계산하는 알고리즘 등
O(n!)	외판원 문제(브루트 포스)

 

문제 풀이 유형

자주 출제되는 유형에는 구현, 완탐, DP 등이 있다.

추가적으로 트리, 자료구조 문제등이 출제되기도 한다.

 

필자는

[유형] 문제 제목 (사용 자료구조 들)

로 제목을 분류해보려고 한다.