[이코테] 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

동빈좌의 유튜브를 보며, 파이썬 알고리즘 공부하기

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

---

알고리즘 성능 평가

복잡도가 낮을수록 더 좋은 알고리즘이다!

그냥 소스 코드가 복잡해보인다. 와는 다른 얘기이다.

성능적인 측면에서의 복잡도를 이야기 하는 것이다.

시간복잡도

특정한 크기의 입력에 대해서 수행 시간 분석

공간복잡도

특정한 크기의 입력에 대해서 메모리 사용량 분석

 

빅오 표기법

가장 빠르게 증가하는 항만을 고려하는 표기법.

(알고리즘 푸는 입장에서는 위와 같이 이해해도 상관없다고 한다.)

 

계수는 무시한다

 

많이 사용되는 용어들이니까 정리해두면 좋다고 함. (그래서 정리함)

 

리스트 객체를 array에 할당해주고,

for문에서 모든 데이터를 하나씩 다 확인을 하니까,

수행시간은 데이터의 개수인 N개에 비례할 것이다.

그래서 O(N) = 선형 시간 이다.

 

그러면 for문이 두 번 겹쳐져있으면 어떻게 될까

O(N^2)이다. 근데 모든 2중 반복문이 O(N^2) 인 것은 아니라고 한다.

반복문 안에 함수가 있다면, 함수의 수행시간까지 계산을 해야된다. (더 늘어날 가능성이 있다는 얘기)

 

python은 1초에 2000만번 정도의 계산을 할 수 있다고 생각하고 접근하자!

근데 서버마다 다르니까 유의해야한다!

 

동빈좌가 실제로 문제를 풀 때 적용을 하는 방법이다.

많은 문제를 풀어보면서 스스로 감을 찾아가는 것이 바람직하다.

 

문제 푸는 과정

1. 지문 읽기 및 컴퓨터적 사고

- 요기에서는 어떤걸 풀고, 요기에서는 어떻게 풀 것인지 대략적인 생각을 하고있는다.

 

2. 요구사항(복잡도) 분석

 

3. 문제 해결을 위한 아이디어 찾기

 

4. 소스코드 설계 및 코딩

 

대부분의 문제 출제자들은 핵심 아이디어를 캐치하면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제를 한다.

동빈좌도 문제를 내보았고, 문제를 낸 사람과 대화를 한 결과 나온 얘기라고 한다.

 

---

자료형

자료형에 대한 이해는 프로그래밍 길에 있어서 첫 걸음이다.

 

정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등등

 

파이썬에서는 기본적으로 제공하는 자료형이 가지고 있는 기능이 매우 다양하고 강력하니까

다른 프로그래밍 언어들과 비교했을 때 보다 다양한 종류 자료형을 작성할 수 있다!

 

정수형

너무 간단해서 넘어감

(강의에서는 자세함)

 

실수형

앞에 0을 생략하거나 뒤에 0을 생략하는 구문도 있다는 것!

 

 

어제 알고리즘 문제를 풀 때 기억나는게 INF 로 표시하는 게 있었는데

1e9로 표현할 수 있다는 것을 새로 배운다!

 

정확히 실수 정보를 표현하지 못한다.

(4바이트나 8바이트 등, 고정된 크기의 메모리를 가지므로)

그래서 round 함수를 이용해서 소수점 아래 몇자 까지 보장할건지 나타낼 수 있다.

 

파이썬은 나누기 연산( / )을 수행했을 때 나머진 결과를 실수형으로 반환하기 때문에 주의해야 한다.

만약 몫을 얻고싶으면 몫 연산자( // )를 사용

거듭 제곱( ** ), 나머지 연산 ( % ) 등등 많다.

 

리스트

기본적인 리스트 내용

리스트 컴프리헨션을 이용하면 네 줄이 나올 코드를 한 줄로 줄일 수 있다!

 

array = [ [0] * m for _ in range(n) ]

에서 [0]을 m번만큼 한 줄로 정의하겠다.

그걸! n번 반복하겠다 라는 뜻임

그래서 n * m 이 되는 것!

언더바( _ )는 반복을 위한 변수의 값을 무시할 때 자주 사용한다.

 

알고리즘에서 가장 많이 사용되는 메소드들을 보여줌 !

 

문자열

문자열 기본

튜플

튜플 = constant ( )

리스트 = variable [ ]

 

튜플은 그럼 언제 사용할까?

1. 서로 다른 성질의 데이터를 묶어서 관리할 때

ex ) 최단 경로 알고리즘에서 (비용, 노드 번호)의 형태로 튜플 자료형을 사용

      또는 (학번, 이름) 형태

2. 집합 자료형(dict)에서 해싱의 키 값으로 사용할 때

ex ) 튜플은 변경이 안되니까, key 값으로 사용이 된다.

3. 또는 리스트보다 메모리를 효율적으로 사용해야 할 때

 

사전

사전 자료형 기초

생성 및 key value 넣기

 

집합 자료형

맨 밑에 줄은 사전 자료형과 동일하다!

 

set은 중복되는 값은 없어진다.

 

합집합, 교집합, 차집합 등의 연산을 제공한다!

---

입출력

각 원소에 특정한 함수를 적용하고 싶으면 map을 사용하자,

map(type, function) = type은 변수의 타입, function은 말그대로 하나의 원소에 적용할 함수를 의미한다.

 

list(map(int, input().split())) (많이 사용된다)

사용자로부터 받은 데이터를 띄어쓰기로 나누는데 그걸 int형으로 변환하고 list로 반환한다.

 

a, b, c = map(int, input(),split())

들어오는 데이터의 개수가 정해져 있을 때

 

import sys

sys.stdin.readline().rstrip()

input()보다 더 빨리 받아야 할 때

rstrip()을 이용해 줄 바꿈 기호를 없애주어야 한다.

 

print의 줄바꿈을 원하지 않으면 end 속성을 사용하자!

---

실전에서 유용한 표준 라이브러리

 

1. 자주 사용되는 내장 함수

- sum( )

- min( )

- max( )

- eval( )

- sorted( ), reverse=True를 넣으면 내림차순

- sorted( ) with key

    -  sorted(array, key=lambda x : x[1], reverse=True)

    - array에서 두번째 인덱스를 기준으로 정렬한다.

 

2. 순열과 조합

itertools 라이브러리를 사용하면 좋다.

 

순열

 

조합

Counter 라이브러리

 

math 라이브러리