[코딩테스트] 요약

문제 해결 순서

- 문제는 쪼개서 읽기

- 제약사항 파악하기

- 테스트 케이스 고려하기

- 입력값 분석하기

- 핵심 키워드 분석하기

- 데이터 흐름 + 구성 파악하기

 

Pseudo-Code

- 자연어로 작성

- 동작 중심으로 문제 해결 순서로 작성

 

시간복잡도

- 알고리즘이 문제를 푸는 연산횟수와 입력의 관계를 표현

- Big-O Notation: 최악의 경우를 고려한 시간복잡도 표기법

시간복잡도	최대 연산 횟수
n!	10
2^n	20
n^3	200
n^2	3000
n*log(n)	100만
n	1000만
log(n)	10억

 

 

자료형

- 부동소수점 오차주의(sys.float_info.epsilon)

- 데이터 타입은 mutable(list, dict, set)과 immutable(tuple, int, float, str)로 나뉨

 

함수

- lambda expression

- 조기 반환: 코드 실행중 반환

- 보호 구문: 로직 실행전 예외처리

- 합성 함수: 2개 이상의 함수로 새로운 함수를 만듬

 

자료구조

Array

- 접근: O(1)

- 맨 뒤 삽입: O(1)

- 맨 앞 삽입: O(N)

- 1차원 공간(1000만개), 2차원 배열(3000*3000개)

 

List

- 길이: len(list)

- 값 위치 반환: list.index(val)

- 오름차순 정렬: list.sort(reverse=False)

- 값의 개수 반환: list.count(val)

- 뒤집기: list.reverse()

- list comprehension: [val for _ in range(num)]

 

Stack

- FILO(First In Last Out)

- 주요 개념: data[max_size], top, push, pop, isEmpty, isFull

- 진법 변환에 사용

 

Queue

- FIFO(First In First Out)

- 주요 개념: data[max_size], front, rear, push, pop, isEmpty, isFull

- circular queue: front==rear / (rear+1)%N==front

 

Hash

- key와 value로 이루어진 구조

- 단방향 동작

- 탐색 시간: O(1)

- hash function: 인텍스를 만드는 함수

    - 나눗셈법: key % prime; 키를 소수로 나눈 나머지를 인덱스로 사용

    - 곱셈법: (((key % gold)%1)*m; 소수부분을 취해 최대 버킷을 곱한 값을 인덱스로 사용

    - 문자열 해싱: 문자열을 숫자로 변경

- collision

    - chaning: 해싱한 값이 같으면 연결리스트로 저장

    - open addressing: 선형 탐사 방식; 이중 해시 방식

 

Tree

- 주요 개념: node, edge, root, leaf(=terminal), parent, child, sibling, height, level

- 주요 개념: 이진트리(자식노드가 최대 2개)