[Python] 이코테 Coding test (1)

참고
[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

 

• 코딩테스트는 알고리즘을 얼마나 간결하게 작성하느냐를 테스트하는 것
• 이를 복잡도, 알고리즘의 성능의 척도로 평가한다고 한다

 

0. 복잡도

• 빅오(Big-O) 표기법을 사용, O(N)으로 표기
  • 시간 복잡도: 연산의 횟수
  • 공간 복잡도: 메모리의 양

 

 

< 파이썬 문법 공부(A부록이용) >

1. 수 자료형

• 정수형
• 실수형
  • 소수점 값을 비교하는 작업이 필요할때는 round() 함수를 이용
  • round(실수형데이터, 반올림하고자 하는 위치 -1)

a = 0.3 + 0.6
print(round(a, 4))

📢 0.9

• 지수표현방식
  • 최단 거리를 무한(INF)으로 설정하곤 한다. 최단 경로로 가능한 최댓값이 10억 미만이라면 무한(INF)을 표현할 때 10억을 이용

# 10억의 지수표현방식
a = 1e9

📢 10000000000.0

 

2. 리스트(List) 자료형

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

# 빈 리스트 선언 방법1
a = list()
print(a)

# 빈 리스트 선언 방법2
a = []
print(a)

 

2.1 1차원 리스트 선언

• 모든 값이 0인 1차원 리스트 초기화

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

 

2.2 리스트 컴프리헨션(List Comprehension)

•  리스트를 초기화하는 방법 중 하나

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

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

 

2.3 2차원 리스트 선언

# n * m 크기의 2차원
n=4
m=3
arrary = [m * [0] for _ in range(n)] 

📢[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 사용

특정한 크기를 가지는 2차원 리스트를 초기화 할 때는 리스트 컴프리헨션을 이용해야 한다

 

 

2.4 리스트 관련 기타 메소드(method)

method	사용법	설명	시간 복잡도
append()	변수명.append()	리스트에 원소를 하나 삽입	O(1)
sort()	변수명.sort()	오름차순 정렬	O(NlogN)
sort(reverse = True)	변수명.sort(reverse = True)	내림차순 정렬	O(NlogN)
reverse()	변수명.reverse()	리스트의 원소순서를 뒤집는다(내립차순, 오름차순)	O(N)
insert()	insert(삽입 할 위치 인덱스, 삽입 값)	특정한 인덱스 위치에 원소를 삽입	O(N)
count()	변수명.count(특정 값)	리스트에서 특정한 값을 가지는 데이터의 개수를 셀때 사용	O(N)
remove()	변수명.remove(특정 값)	특정한 값을 갖는 원소를 제거하는데, 여러 개면 하나만 제거	O(N)

시간복잡도 O(N)이 소요

• insert(): append()를 사용
• remove(): not in

array = [ 1, 2, 3, 4, 5]
remove_set = {1, 2}

# remove_set에 포함되지 않은 값만을 저장
result = [i for i in array if i not in remove_set]

📢 [3, 4, 5]

 

3. 튜플(Tuple) 자료형

리스트와 거의 비슷하지만

1. 튜플은 한 번 선언된 값을 변경 할 수 없다.
2. 리스트는 대괄호([ ])를 사용하지만, 튜플은 소괄호(( ))를 사용한다.

🔔 원소의 대입(Item Assignment)이 불가능하다

# 잘못된 코드
a = (1, 2, 3, 4)
a[1] = 2 #튜플은 변경 불가능

• 그래프 알고리즘을 구현 할 때 자주 사용(다익스트: 최단 경로 알고리즘)
  • 최단경로를 찾아주는 알고리즘의 내부에서는 우선순위 큐를 이용하는데 우선순위 큐에 한 번 들어간 값은 변경되지 않는다. 우선선위 큐에 들어가는 데이터를 튜플로 구성하여 소스코드를 작성한다.

 

4. 사전(Dictionary) 자료형

• 키(Key) 와 값(Value)의 쌍을 데이터로 가지는 자료형
  • 변경 불가능한 데이터를 키로 사용
  • 해시 테이블(Hash table)을 이용하므로 기본적으로 데이터의 검색 및 수정에 있어 O(1)의 시간에 처리 할 수 있다.

#선언 방법1
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['수박'] = 'Watermelon'
📢 {'사과': 'Apple', '바나나': 'Banana', '수박': 'Watermelon'}

#선언 방법2
data = {'사과': 'Apple', '바나나': 'Banana', '수박': 'Watermelon'}
📢 {'사과': 'Apple', '바나나': 'Banana', '수박': 'Watermelon'}

• 키와 값을 별도로 뽑아내기 위한 함수
  • keys()
  • values() 

key_list = data.keys()
value_list = data.values()

print(key_list)
📢 dict_keys(['사과', '바나나', '수박'])

print(value_list)
📢 dict_values(['Apple', 'Banana', 'Watermelon'])

 

5. 집합(Set) 자료형

1. 중복을 허용하지 않는다.
2. 순서가 없다.

• 리스트, 튜플
  • 순서가 있다.
  • 인덱싱을 통해 자료형의 값을 얻을 수 있었다.
• 사전 자료형, 집합 자료형
  • 순서가 없다.
  • 인덱싱으로 값을 얻을 수 없다는 특징이 있다.
    •  특정한 데이터가 이미 등장한 적이 있는지 여부를 체크할 때 매우 효과적

# 선언 방법 1
data = set([1, 2, 3, 4, 5])

# 선언 방법 2
data = {1, 2, 3, 4, 5}

📢 {1, 2, 3, 4, 5}

 

5.1 집합 자료형 관련 함수

• add(): 하나의 집합 데이터에 값을 추가
• update(): 여러 개의 값을 한꺼번에 줄 때 사용
• remove(): 특정한 값을 제거 할 때 사용

이때 add(), remove()는 모두 시간 복잡도가 O(1)이다.

 

data = set([1, 2, 3])

data.add(4)
📢 {1, 2, 3, 4}

data.update([5, 6])
📢 {1, 2, 3, 5, 6}

data.remove(3)
📢 {1, 2}