1. 알고리즘의 성능평가
- 시간복잡도 : 알고리즘의 수행시간
- 공간복잡도 : 알고리즘의 메모리 사용량
- 빅오표기법 : 알고리즘 수행능력을 입력받은 데이터 개수에 따른 연산량, 수행소요시간을 나타내는 방법이다. 시간소요량의 최대값(함수의 상한선)을 기준으로 나타낸다.
※ 빅오표기법 - 데이터 개수가 늘어남에 따라 어떠한 인자, 형태로 소요량이 늘어나는가
O(1) : 상수시간
O(logN) : 로그시간
O(N) : 선형시간
O(N*logN) : 로그선형시간
O(Nⁿ) : n차시간
보통 선형시간, 로그선형시간이면 시간복잡도를 줄일 수 있고 다차 반복 loop에서의 다차시간복잡도를 어떻게 줄일 수 있느냐가 중요하다.
연산횟수가 보통 5억회를 넘어가면 python 기준 5~15초가 소요되고, 통상적으로 수용가능한 소요시간은 3~5초 정도이다.
- 알고리즘 해결 과정 : 컴퓨터적 사고 > 복잡도 분석(*import time을 통해 시작-종료시간 계산도 하나의 방법) > 해결방안/수도코드 > 실코딩
2. 자료형
- 정수형 : 양의정수(자연수), 음의정수, 0
- 실수형
- 지수형 : ne^m = n10^m
- 소수형 : round() 등
3. 연산
- a/b : 나누기, 실수 형태 그대로 결과 출력
- a // b : 몫
- a % b : 나머지
- a ** b : a의 b제곱
4. 리스트(array)
여러개의 데이터를 연속적, 선형으로 담아 처리하기위해 사용하는 자료형
배열(array) 및 연결리스트(linkedlist)와 유사한 기능, table이라고도 일컫는다.
인덱스는 0부터 출발하며, 최초 선언시 list = [] or a = list() 등으로 선언가능
- 인덱싱 : 리스트의 특정한 원소에 접근하는 것, 음의 정수(a[-1], 마지막에서 첫번째 원소로 접근)를 사용하여 인덱싱할 수도 있다.
- 슬라이싱 : 연속적인 위치에 있는 원소에 접근하는 것, a[1,4+1]로 활용가능(첫번째 인덱스부터 4번째 인덱스까지 접근하며, 마지막 인덱스는 접근 인덱스 + 1)
리스트 컴프리헨션, 리스트의 깊은 복사
이중배열을 선언한다고 할 때, 단순히 a = [[0] x N] x M 의 사칙연산 형식으로 선언하면 안된다.
위와 같이 선언할 경우 리스트의 얕은 복사가 진행되는데, [0] X N으로 선언된 1차배열을 계속 같은 메모리 상에서 참조(즉 같은 객체가 그대로 복사)되어, 각 배열 원소값을 바꾸는 것이 불가능(하나만 바꿔도 M행의 배열원소 모두 바뀐다)해진다.
따라서 깊은 복사를 진행해야 하며, 이는 for 반복을 통해 진행한다.
array = [ 0 * N for _ in range (M) ]
위와 같이 깊은 복사를 진행해야 각 배열 행이 다른 메모리 주소를 참조하게 되어(다른 객체들로 생성), 각 원소값을 다른 값으로 적용 및 바꾸는 것이 가능해진다.
- for 반복문을 활용한 array 초기화
array = [ i for i in range(list or number) ]
array = [ i for i in range(list or number) if i % 2 == 0]
※위 경우와 같이 for 반복과 if조건을 같이 기재하는 것도 가능
관련 메소드
- append 원소추가
- sort 오름차순정렬(※sorted라는 별도 메소드 사용가능)
- sort(reverse = True) 내림차순정렬
- reverse 원소순 뒤집기
- insert(n, m) n번째 인덱스에 m원소 삽입하기
- count(값) : 특정값을 가지는 데이터의 수
- remove(값) 특정 값 제거하기
data = [1, 2, 3, 3, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7]
remove_set = [5, 6] (※집합 자료형)
result = [ i for i in data if i not in remove_set]
-> 1, 2, 3, 4, 7
5. 문자열 자료형
- 큰(작은) 따옴표 내부에 작은(큰) 따옴표 사용 가능
- 백슬래쉬 이용 가능 print("Hello 'BUSAN' and \"World\" ?")
※ 백슬래쉬를 이용하여 큰 따옴표 안에 큰 따옴표를 사용가능 - +를 이용해서 문자열 붙이기 등 가능
- 문자열은 인덱싱/슬라이싱은 가능하지만 변경은 불가능하다(Immutable).
6. 튜플 자료형
리스트와 유사하지만 문법적, 활용적으로 차이가 있는 선형배열의 일종.
한번 선언된 튜플 값은 변경할 수 없으며, 리스트가 []로 선언되었다면 튜플은 (), 소괄호 형태로 선언한다.
- 리스트에 비해 공간효율적(메모리를 적게 사용).
- C의 vector, pointer와 같이 서로 다른 성질의 데이터를 묶어서 관리하고자 할 때 많이 사용한다(특히 최단거리 알고리즘에서 (비용, 노드번호) 등으로 저장하는 경우).
- 예를 들어 [(1,5),(57,3)] 이런식으로 저장이 가능하다.
7. 딕셔너리(사전 자료형)
key : value 형식으로 데이터를 저장하는 자료형이며, 이때 key값은 변경불가(Immutable).
내부적인 구조로 hash table을 활용하여 data를 저장한다.
- dict.keys() : 모든 key 값들을 객체형태로 출력
- dict.values() : 모든 value 값들을 객체형태로 출력
- a=dict() : a 딕셔너리 선언
- list(dict.keys()) 등을 활용하면 객체를 리스트형태(배열)로 전환해서 출력할 수 있다.
8. 집합자료형
리스트 등을 이용하여 데이터의 존재여부를 확인하는데 주로 사용하는 자료형
data = set([1, 2, 3, 4, 5])
- set() 함수 이용
- 원소추가 : add()
- 원소제거 : remove()
- 여러개 원소추가 : update([x, y])
9. 입출력
9-1. input()을 이용한 기본 입출력
파이썬에서 자주 사용하는 표준입출력 방법으로, input 함수를 이용하여 데이터를 전달받는다.
- print(list(map(int, input().split())))
→ 문자열로 입력받아 객체상태로 저장된 값을 int형으로 바꿔주고, 이를 list형태로 출력(*split()함수를 통해 공백을 기준으로 데이터 입력)
※ input(),split() 상태 자체는 문자열 상태이다(데이터가 문자열로 입력받고 객체로 저장됨) - a, b, c = map(int, input().split())
→ 공백을 기준으로 데이터를 입력받고, 이를 정수형태로 각 변수에 저장한다.
9-2. sys 라이브러리를 사용한 빠른 입출력
단순히 input 형태가 아닌, 빠르게 데이터를 입력받을 수 있는 sys 라이브러리를 활용할 수 있다.
- import sys
- sys.stdin.readline()
→ 공백을 기준으로 데이터를 입력받을 수 있다. - 입력후 엔터 시 줄바꿈기호가 출력되는데, readline().rstrip()을 통해 이를 제거할 수 있다.
이진탐색, 정렬, graph 등 다양한 입력을 받는데 사용가능
10. 출력
- print()
- print(a, b)
- print(a, end = " ")
- print(str(answer)) ※ answer가 정수형일 경우 srt를 통해 문자열로 전환
※ 출력은 기본적으로 줄바꿈이 되는데, end요소를 넣어주면(위에서는 공백) 자동 줄바꿈을 하지 않도록 설정해줄 수 있다.
- print(f"정답은 {answer}입니다") ※ f-string, 변수를 활용하여 문자열 출력(js의 backtik)
11. 부등식
- 웬만한 표현은 x > 0 and x < 20 이런 식으로, 피연산자가 왼쪽을 향하도록 기재하는 것이 좋다.
12. condition(조건)/loop(반복)
- and, or, not
- x in list
- for i in range(x) : 0부터 x-1까지 반복
- continue : 가장 가까운 반복문을 탈출하고 다음 반복을 실행
- break : 가장 가까운 반복문을 탈출(추가 반복이 필요하다면 continue 사용을 반드시 고려해주어야 한다)
13. return
파이썬은 C(클래스, 구조체 등)과는 달리 함수 자체에서 여러개의 반환값을 전달해줄 수 있으므로 편리하다.
14. lambda 표현식(python lambda)
특정 기능을 수행하는 함수를, 별도의 함수 선언없이 1줄에 표현할 수 있는 기능을 제공한다.
주로 1번 사용하고 마는 함수, 함수의 기능이나 형태가 간단한 경우에 많이 사용하는데, 특히 sorted함수 내부적으로 정렬기준을 명세할때 사용한다.
쉽게 말하면, javascript에서 사용하는 arrow function처럼 간편한(no name, 무명) 함수 정의법이다.
기본적인 lambda 함수 표현식은 아래와 같다.
lambda a,b : a+b(x,y)
- a,b : 인자
- a+b : return 형태/연산
- x,y : 입력값(a,b에 각각 가르키는 형태로 입력받을 수도 있음)
array = [ ('a', 3), ('b', 2), ('c', 1) ]의 리스트에서 정수의 오름차순대로 배열하고자 할 때
- print(sorted(array, key = lambda x : x[1])
※ key는 정렬 기준, lambda의 x원소는 array의 원소임을 이미 내부적으로 특정되어있음 - print(sorted(array, key = my_key)) .. def my_key return my_key[1]
여러 개의 list에 lambda 표현식 사용 가능
- list1 = [1, 2, 3, 4, 5]
- list2 = [3, 4, 5, 6, 7]
result = map(lambda a,b: a+b, list1, list2)
※각 인자 a,b는 자동적으로 list1, list2 내부의 원소를 가리킨다.
15. 코딩테스트에서 많이 활용할 수 있는 라이브러리
- sys(입력)
- heapq(heap, queue 자료구조 .. 다익스트라(최단거리))
- itertools(반복되는 형태의 데이터 처리 .. 순열/조합의 배열 및 완전탐색 출력)
- bisects(이진탐색기능)
- collections(dequeue, counter 기능 제공)
- math(팩토리얼, 제곱근, 최대공약수, 삼각함수 등)
이외 내장함수
- sum(array) (array내부의 원소들을 모두 더한 값 반환)
- min(array) or max(array)
- eval(string) string(보통 수식)을 실제 수자료형의 결과값으로 반환
- array.sort()
16. 순열과 조합
모든 경우의 수를 고려해야하는 경우(완전 탐색), 사용할 수 있는 효과적인 라이브러리가 존재한다.
- itertools(라이브러리)
from itertools import permutations
data = [ 'A', 'B', 'C' ]
result = list(permutations(data, 3))
→ data P 3 .. data 중에 3개를 선택하여 순열의 경우의 수 출력
※ 순열은 r개를 선택해서 순서대로 정렬하는 경우의 수(순서고려)
※ 중복포함 : import product
from itertools import conditions
data = [ 'A', 'B', 'C' ]
result = list(conditions(data, 3))
→ data C 3 .. data 중에 3개를 선택하여 조합의 경우의 수 출력
※ 조합은 r개를 선택하는 경우의 수(순서고려하지 않는다)
※ 중복포함 : import conditions_with_replacement
17. Counter
파이썬 collections의 라이브러리에서 사용할 수 있는, 해당 data의 등장횟수를 세는 도구이다.
파이썬 world cloud에서 사용할 수 있는 간편 기능 중 하나.
- collections
from collections import Counter
counter = Counter(list)
counter['a'] : list에서 원소 a의 개수를 센다.
dict(counter) : counter로 선언한 list를 dict 자료형으로 변환해서 출력한다.
18. math
- math
import math
result = math.gcd(a,b) 최대공약수
result = a * b // math.gcd(a,b) 최소공배수
참조 강의
이코테 2021
https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=1
