[Python]코딩 테스트 준비 (출제 경향 및 준비 방법, Python 문법(1))

코딩 테스트 준비

(이것이 코딩테스트다 2021 강의, 나동빈)

 

IT기업 코딩 테스트 최신 출제 경향

1) 구현

2) BFS/DFS

3) 그리디

4) 정렬

5) 다이나믹 프로그래밍

6) 이진 탐색

7) 최단경로

8) 그래프 경로

 

알고리즘 성능 평가

1) 빅오 표기법이란 ?

 알고리즘의 “효율성”을 평가하기 위한 분석법.

   시간 복잡도(실행시간)와 공간 복잡도(실행공간)로 이루어진다.

  - 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

  - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

  * 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘 ㅇ디ㅏ.

 

2) 빅오 표기법 예시

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

   : 함수의 상한만을 나타내게 됩니다.

  예를 들어 연산횟수가 3N^3 + 5N^2 + 1000000인 알고리즘이 있다고 합니다.

   : 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 0(N^3)만 남게 된다.

출저 : 나동빈 (이것이 코딩테스트다 ) 유투브

 

좀더 세부적인 예제를 들어보자,

시간 복잡도 이해하기 위한 예제,

다음은 N개의 데이터의 합을 계산하는 예제 프로그램다.

array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)
summary = 0 #합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for in array:
	summary += x
    
# 결과를 출력
print(summary)

이 것의 수행 시간은 데이터의 개수 N개의 비례할 것임을 예측 할 수 있다.

  시간 복잡도 : O(N)

 

2중 반복문을 이용하는 프로그램 예제

array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)

for in array:
	for j in array:
    	temp = i*j
        print(temp)
    

이 프로그램의 시간 복잡도 : O(N^2)

 

참고로 모든 2중 반복문의 시간 복잡도가 O(N^2)인 것은 아니다. 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도 까지 고려해야한다.

 

※ 알고리즘 설계 Tip

 - 일반적으로 CPU기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:

   : C언어 기준 통상 1 ~ 3초 시간 소요

   : Python 기준으로 5 ~ 15초 가량의 시간이 소요

    * PyPy의 경우 때때로 C언어보다 빠르게 동작하기도 한다.

 - 0(N^3)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까요 ? 1250억(2500초)

  * 코딩 테스트 문제에서 시간 제한은 통상 1 ~.5초 가량이라는 점에 유의하세요

   : 혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도 라고 생각하고 문제를 푸는 것이 합리적이다.

 

 

요구 사항에 따라 적절한 알고리즘 설계하기

 - 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항) 입니다.

 - 시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다.

  1) N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀수 있다.

  2) N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀수 있다.

  3) N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀수 있다.

  4). N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀수 있다.

 

알고리즘 문제 해결 과정

 1) 일반적인 알고리즘 문제 해결 과정은 다음과 같다.

   1. 지문 읽기 밑 컴퓨터 사고

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

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

  4. 소스코드 설계 및 코딩

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

 

시간 측정 방법

import time
start_time = time.time() # 측정 시작

#프로그램 소스코드
end_time = time.time() # 측정 종료
print("time : ", end_time - start_time) # 수행 시간 출력

 

 

자료형이란 ?

모든 프로그래밍은 결국 데이터를 다루는 행위

  - 자료형에 대한 이해는 프로그래밍의 길에 있어서 첫걸음 이라고 할 수 있다.

파이썬의 자료형으로는 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등이 있다.

  - 파이썬의 자료형은 필수적으로 알아 두어야 한다.

 

1) 정수형(Integer)

 - 정수를 다루는 자료형 (양의 정수, 음의 정수, 0)

※ 코딩 테스트에서 출제 되는 많은 문제들은 정수형을 주로 다루게 됩니다.

# 양의 정수
a = 1000
print(a) # 1000

# 음의 정수
a = -7
print(a) # -7

# 0
a = 0
print(a) # 0


a = 777
a = a + 5
print(a) # 777

 

2) 실수형(Real Number)

 - 소수점 아래의 데이터를 포함하는 수 자료형

  : 파이썬 에서는 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리된다.

  : 소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성 할 수 있다.

# 양의 실수
a = 157.93
print(a) #157.93

# 음의 실수
a = -157.93
print(a) #-157.93

# 소수부가 0일떄 0을 생략
a = 5.
print(a) #5.0

# 정수부가 0일 떄 0을 생략
a = -.7
print(a) #-0.7

파이썬에서는 e나 E를 이용한 지수 표현 방식을 이용할 수 있다

 - e나 E다음에 오는 수는 10의 시부를 의미.

 - 예를 들어, 1e9라고 입력하게 되면, 10의 9제곱(1,000,000,000)이 된다.

지수 표현 방식은 임의의 큰 수를 표현 하기 위해 자주 사용된다.

최단 경로 알고리즘에서는 도달 할 수 없는 노드에 대하여 최단 거리를 무한(INF)로 설정 하곤 한다.

이때 가능한 최댓 값이 10억 미만이라면 무한(INF)의 값으로 1e9를 이용 할 수 있다.

 

a = 1e9
print(a) # 1,000,000,000

a = 75.25e1
print(a) #752.5

a = 3954e-3
print(a) 3.954

 

오늘날 가장 널리 쓰이는 IEEE754표준에서는 실수형을 저장하기 위해 4바이트, 혹은 8바이트의 고정된 크기의 메모리를 할당하므로, 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가진다.

 

예를들어 10진수 체계에서는 0.3과 0.6을 더한 값이 0.9로 정확히 떨어지나, 2진수에서는 0.9를 정확히 표현할 수 있는 방법이 없다.

다음 코드를 통해 확인해보자,

 

a = 0.3 + 0.6
print(a)

if a == 0.9:
    print(True)
else:
    print(False)

실행하면 False가 출력된다

 

이럴때는 round()함수를 이용할 수 있으며, 이러한 방법이 권장이 된다.

a = 0.3 + 0.6
print(a) #0.8999999999999999
print(round(a,4))  #0.9
if round(a, 4) == 0.9:
    print(True) # True 출력
else:
    print(False)

이렇게 round()함수를 사용하면 정상적으로 0.9를 표현 할 수 있다.

 

수 자료형에 대하여 사칙 연산과 나머지 연산자가 많이 사용된다.

단 나누기 연산자(/)를 주의해서 사용해야 한다.

  - 파이썬은 나누기 연산자(/)는 나눠진 결과를 실수형으로 반환함

다양한 로직을 설계할 때 나머지 연산자(%)를 이용해야 할 때가 많다.

  - 예시: a가 홀수인지 체크해야 하는 경우

파이썬에서는 몫을 얻기 위해 몫연산자(//)를 사용한다.

이외에도 거듭 제곱 연산자(**)를 비롯해 다양한 연산자들이 존재한다.

 

a = 7
b = 3

#나누기
print(a / b) 2.3333333333333335
#나머지
print(a % b) # 1
#몫
print(a//b) # 2
#거듭 제곱
print(a ** b) # 343
print( a ** 0.5) # 2.6457513110645907

 

리스트 자료형

 

1)여러개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형

  - 사용자 입장에서 C나 자바에서의 배열(Array)의 기능 및 연결 리스트와 유사한 기능을 지원함

  - C++ 의 STL vector와 기능적으로 유사하다.

  - 리스트 대신에 배열 혹은 테이블이라고 부르기도 한다.

2) 리스트 초기화

  - 리스트는 대괄호안에 원소를 넣어 초기화하며, 쉼표(,)로 원소를 구분함

  - 비어 있는 리스트를 선언하고자 할 때는 list()혹은 간단히 []를 이용할 수 있다.

  - 리스트 원소에 접근할 때는 인덱스(index)값을 괄호에 넣습니다 ※ 인덱스는 0부터 시작

 

# 직접 데이터를 넣어 초기화
a = [1,2,3,4,5,6,7,8,9] 
print(a) # [1, 2, 3, 4, 5, 6, 7, 8, 9]

#네 번쨰 원소만 출력
print(a[3]) # 4

#크기가 N이고, 모든 값이 0인 1차원 리스트 초기화
n = 10
a = [0] * n
print (a) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

인덱스 값을 입력하여 리스트의 특정한 원소에 접근하는 것을 인덱싱(Indexing)이라고 한다.

 - 파이썬의 인덱스 값은 양의 정수와 음의 정수 모두 사용할 수 있다

 - 음의 정수를 넣으면 원소를 거꾸로 탐색하게 된다.

a = [1,2,3,4,5,6,7,8,9] 

#여덟 번쨰 원소만 출력
print(a[8]) # 8

# 뒤에서 첫 번째 원소 출력
print(a[-1]) # 9

# 뒤에서 세 번쨰 원소 출력
print(a[-3]) # 7

# 네 번째 원소 값 변경
a[3] = 7
print(a) # [1, 2, 3, 7, 5, 6, 7, 8, 9]

3)리스트에서 연속적인 위치를 갖는 원소들을 가져와야할 때는 슬라이싱(Slicing)을 이용한다.

 - 대괄호 안에 콜론(:)을 넣어서 시작 인덱스와 끝 인덱스를 설정 할 수 있다.

 - 끝 인덱스는 실제 인덱스보다 1을 더 크게 설정한다.

a = [1,2,3,4,5,6,7,8,9] 

# 네 번쨰 원소만 출력
print(a[3]) # 4

# 두 번째 원소 부터 네 번째 원소 까지
print([a[1:4]])  # [2, 3, 4]

4)리스트컴프리헨션

 - 리스트를 초기화 하는 방법 중 하나로 대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화할수 있다.

array = [i for i in range(10)]
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = [i for i in range(20) if i%2 == 1]
print(array) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]


# 1부터 9 까지의 수들의 제곱 값을 포함하는 리스트
array = [i * i for i in range(1,10)]
print(array) # [1, 4, 9, 16, 25, 36, 49, 64, 81]

- 리스트 컴프리헨션과 일반적인 코드 비교하기

 <코드 1.  리스트 컴프리헨션> 

# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = [i for i in range(20) if i%2 == 1]
print(array) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

<코드 2.일반적인 코드>

# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = []
for i in range(20):
	if i%2 == 1:
    	array.append(i)
print(array) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 - 리스트 컴프리헨션은 2차원 리스트를 초기화 할 때 효과적으로 사용할 수 있다.

 - 특히 N X M크기의 2차원 리스트를 한번에 초기화 해야할 때 매우 유용하다.

  : 좋은 예시 - array = [[0] * m for _ in range(n)]

 - 만약 2차원 리스트를 초기화할때 다음과 같이 작성하면 예기치 않은 결과가 나올 수 있다.

  : 잘못된 예시 - array = [[0] * m] * n ※ 위 코드는 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식 됨.

 

예제를 통해서 알아보자,

좋은 예)

# N X M 크기의 2차원 리스트 초기화
n = 4
m = 3
array = [[0] * m for _ in range(n)]
print(array) # [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

array[1][1] = 5 
print(array) # [[0, 0, 0], [0, 5, 0], [0, 0, 0], [0, 0, 0]]

나쁜 예) ※전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식

# N X M 크기의 2차원 리스트 초기화
n = 4
m = 3
array = [[0] * m] * n
print(array) # [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

array[1][1] = 5 
print(array) # [[0, 5, 0], [0, 5, 0], [0, 5, 0], [0, 5, 0]]

※ ' _ (언더바)' 는 언제 사용하나요?

  - 파이썬에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할때 언더바(_)를 자주 사용한다.

#코드 1 (1부터 9까지의 자연수를 더하기)
summary = 0
for i in range(1, 10):
	summary += i
print(summary)

#코드 2 "Hello World"를 5번 출력하기
summary = 0
for _ in range(5):
	print("Hello World")

 

출저 : 나동빈 유투브 이코테 2021

리스트 관련 메서드를 활요한 예제

 

a = [1,4,3]
print("기본 리스트 : ", a) # 기본 리스트 :  [1, 4, 3]

# 리스트에 원소 삽입
a.append(2)
print("삽입 : ", a) # 삽입 :  [1, 4, 3, 2]

# 오름 차순 정렬
a.sort()
print("오름차순 정렬 : ", a) # 오름차순 정렬 :  [1, 2, 3, 4]

# 내림 차순 정렬
a.sort(reverse=True)
print("내림차순 정렬 : ", a) # 내림차순 정렬 :  [4, 3, 2, 1]

# 리스트 원소 뒤집기
a.reverse()
print("원소 뒤집기 : ", a) # 원소 뒤집기 :  [1, 2, 3, 4]

#특정 인덱스에 데이터 추가
a.insert(2, 3)
print("인덱스 2에 3 추가 : ", a) # 인덱스 2에 3 추가 :  [1, 2, 3, 3, 4]

# 특정 값인 데이터 개수 세기
print("값이 3인 데이터 개수", a.count(3)) # 값이 3인 데이터 개수 2

# 특정 값 데이터 삭제
a.remove(1)
print("값이 1인 데이터 삭제 : ", a) # 값이 1인 데이터 삭제 :  [2, 3, 3, 4]

 

리스트에서 특정 값을 가지는 원소를 모두 제거하기

a = [1,2,3,4,5,5,5,5]

remove_set = {3, 5} # 집합 자료형

#remove_set에 포함 되지 않은 값만을 저장
result = [i for i in a if i not in remove_set]
print(result) # [1, 2, 4]