코딩 테스트 개요와 파이썬 문법 기초1 (자료형)

Youtube  '동빈나' - [이코테 2021 강의 몰아보기] 영상을 보고 복습하는 글입니다.

1. 알고리즘 코딩테스트에 대한 이해

ㄱ. 알고리즘 코딩테스트 유형 분석

구현 > 그리디 > BFS/DFS > (정렬=다이나믹 프로그래밍>이진 탐색>최단 경로>그래프 이론)

 

ㄴ. 알고리즘 성능 평가

▶복잡도 (함수의 성능적인 측면에서의 복잡도)

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

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

▶빅오 표기법(Big-O Notation)

  가장 빠르게 증가하는 항만을 고려하는 표기법 (차수가 가장 큰항만 남김)

  ex) 3N^3 + 5N^2 + 1,000,000 -> O(N^3)으로 표현.

 

ㄷ. 알고리즘 문제 해결 과정

⑴ 지문읽기 및 컴퓨터적 사고 : 문제를 잘게 분해. 각 과정에서 무엇이 필요할지 고민.

⑵ 요구사항(복잡도) 분석 : 문제를 최대한 간결하게 정의. 

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

⑷ 소스코드 설계 및 코딩

 

* 일반적으로 핵심 아이디어를 캐치하면, 간결하게 소스코드를 작성할 수 있는 형태로 문제가 출제됨.

* 소스코드를 먼저 작성하려 하기보다, 문제를 잘 이해하고 정의해서 이 문제를 창의적이고 확실하게 풀 수 있다는 확신이 생긴 후에 푸는게 결과적으로 실수를 줄이고, 빠르게 풀 수 있을 것임.

 

ㄹ. 수행 시간 측정 소스코드 예제

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

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

 

2. 파이썬 문법 기초1 (자료형)

ㄱ. 자료형

▶모든 프로그래밍은 결국 데이터를 다루는 행위이므로, 자료형에 대한 이해는 필수!

▶파이썬의 자료형 : 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등

 

ㄴ. 정수형

▶정수를 다루는 자료형 (양의 정수, 음의 정수, 0이 포함)

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

# 음의 정수
a = -7

# 0
a = 0
print(a)

ㄷ. 실수형

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

▶5.0 혹은 0.7은 5. 혹은 .7로 표현 가능.

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

# 소수부가 0일 때 0을 생략
a = 5.
print(a)	# 5.0이 출력

# 정수부가 0일 때 0을 생략
a = .7
print(a) 	# 0.7이 출력

ㄹ. 지수 표현 방식

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

▶임의의 큰 수를 표현하기 위해 자주 사용되는 방식.

▶실수형 데이터로서 처리됨.    >>정수형으로 처리하기 위해서 a = int(1e9) 로서 처리하는 것이 좋음.

▶e나 E 다음에 오는 수는 10의 지수부를 의미.

  ex) 2e9 = 2 * 10^9 (2,000,000,000)

유효숫자e지수 = 유효숫자 X 10^지수

# 1,000,000,000의 지수 표현 방식
a = 1e9
print(a)

# 752.5
a = 75.25e1		# 75.25 * 10^1
print(a)

# 3.954
a = 3954e-3		# 3954 * 10^(-3)
print(a)

Q. 왜 정수형으로 바꿔주는 것이 좋을까?

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

ex) 10진수 체계에서 0.3+0.6 = 0.9로 정확히 떨어지지만, 2진수에서는 0.9를 정확히 표현할 수 없음. 미세한 오차 발생.

a = 0.3 + 0.6
print(a)			# 0.899999999999 출력

if a == 0.9:
	print(True)
else:
	print(False)		# False 출력

개발 과정에서 실수 값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수 있음. 이를 해결하기 위해, 

round() 함수를 이용. 반올림 목적으로 사용.

ex) 123.456을 소수 셋째 자리에서 반올림 -> round(123.456,2) = 123.46

 

ㅁ. 수 자료형의 연산

▶수 자료형에 대해서 사칙연산과 나머지 연산자가 많이 사용되는데, 나누기 연산자를 주의해야함.

  파이썬에서 나누기 연산자(/)는 결과를 실수형으로 반환.

▶다양한 로직을 설계할 때, 나머지 연산자(%)를 이용할 때가 많음.  ex) 특정한 수가 홀수 인지 체크해야할 경우

▶몫을 얻기 위해 몫 연산자(//)를 사용함.

▶거듭 제곱 연산자(**) 또한 존재.

a = 7
b = 3

# 나누기
print(a / b)	# 2.333333333333335

# 나머지
print(a % b)	# 1

#몫
print(a // b)	# 2

# 거듭제곱
print(3 ** 3)	# 27

# 제곱근
print(5 ** 0.5)	2.23606797749979

ㅂ. 리스트 자료형 

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

▶배열의 기능 및 연결 리스트와 유사한 기능을 지원함. (추가, 삭제, 연결 등 가능)

▶배열이라고도, 테이블이라고도 불림.

 

① 리스트 초기화

▶대괄호[] 안에 원소를 넣어 초기화하며, 쉼표(,)로 원소를 구분.

▶비어있는 리스트를 선언하고자 할때는 list() 혹은 []를 이용할 수 있음.

▶0부터 시작하는 인덱스 값으로 리스트의 원소에 접근 가능.

a = [1,2,3,4,5]
print(a)	# [1,2,3,4,5]
print(a[3])	# 4

# 임의의 값으로 크기가 N인 1차원 리스트를 초기화
n = 10
a = [0] * n	# 0이 10번 들어가는 것.
print(a)	# [0,0,0,0,0,0,0,0,0,0]

② 리스트의 인덱싱과 슬라이싱

▶인덱싱(Indexing) : 인덱스 값으로 리스트의 특정한 원소에 접근하는 것

▶인덱스 값은 양의 정수와 음의 정수 모두 사용 가능.

▶음의 정수를 사용하면, 원소를 거꾸로 탐색함. (단, 0부터 시작되는 양의 정수와 달리, -1부터 시작된다!)

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

# 여덟 번째 원소만 출력
print(a[7])

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

# 네 번째 값 원소 변경
a[3] = 10

▶슬라이싱(Sliciing) : 연속적인 위치의 값들을 한번에 가져올 수 있는 기능.

▶대괄호 안에 콜론(:)을 넣어서 시작인덱스와 끝인덱스를 설정할 수 있음. (단, 끝 인덱스는 +1로 설정!)

a = [1,2,3,4,5]
print(a[0:2])	# [1,2] 출력

③리스트 컴프리헨션 : 리스트를 초기화 하는 방법 중 하나.

▶대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화!

# 0부터 9까지의 수를 포함하는 리스트 초기화 (반복문)
array = [i for i in range(50)]		# for문으로 돌아가는 값 'i'를 array[]에 넣겠다.

print(array)	# [0,1,2,3,,,,47,48,49]

# 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]

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

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

   코딩테스트 문제상황 자체를 2차원 리스트크기의 맵 상에서 벌어지는 상황으로 정의하는 경우가 많기 때문.

▶ex) array = [[0] * m for _ in range(n)]   # n번 반복할 때마다, 길이가 m인 리스트를 초기화 ⇒ N*M크기의 리스트.

array = [[0]*3 for _ in range(4)]	# 행이 4, 열이 3.

print(array)	# [[0,0,0], [0,0,0], [0,0,0], [0,0,0]]	4*3 크기의 2차원 리스트.

0	0	0
0	0	0
0	0	0
0	0	0

▶잘못된 예시: array = [[0] * m] * n  ⇒ 리스트를 초기화할 때 각 객체의 주소값이 할당되는데, 이런 식으로 작성하게 되면, 단지 리스트 [0]*m를 n번 복사한 것과 같기 때문에, 같은 객체로 인식됨.

 

Q. 언더바(_)는 언제 사용하는가?

반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 자주 사용함.

ex) for _ in range(5):

        print("Hello World")

 

④ 리스트 관련 기타 메서드

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

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,5)
print("인덱스 2에 5추가: ", a)	# 인덱스 2에 5추가:  [1, 2, 5, 3, 4]

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

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

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

a = [1, 2, 3, 4, 5, 5, 5]
remove_set = {3, 5}		# 집합 자료형: 특정한 원소의 존재 유무만을 체크하고자 할때 유용한 자료형.

result = [i for i in a if i not in remove_set]	# remove_set에 있지 않는 i만 result에 입력.
print(result)	# 3,5를 제외한 [1,2,4]

 

ㅅ. 문자열 자료형

▶문자열 자료형을 초기화할 때는 큰 따옴표(")나 작은 따옴표(') 이용함.

▶문자열 내에서 큰 따옴표나 작은 따옴표를 포함시키고자 한다면, 백슬래시(\)를 이용함. (이스케이프 문자형태로)

data = "Hello World"
print(data)		# Hello World

data = "Don't you know \"Python\"?"		# 큰따옴표로 구성된 문자열 내에서 작은따옴표를 포함할 수 있음.
print(data)		# Don't you know "Python"?

① 문자열 연산

▶문자열 변수에 덧셈(+)을 이용 ⇒ 문자열이 더해져서 연결(Concatenate)됨.

▶문자열 변수를 특정한 양의 정수와 곱셈 ⇒ 문자열이 그 값만큼 여러번 연결됨.

▶문자열 또한 인덱싱과 슬라이싱을 이용할 수 있음. (but, 특정 인덱스의 값을 변경할 수는 없음 - Immutable)

a = "Hello"
b = "World"
print(a + " " + b)	# Hello World

a = "String"
print(a * 3)	# StringStringString

a = "ABCDEF" 
print(a[2 : 4])	# CD

ㅇ. 튜플 자료형

▶리스트와 유사하지만 문법적 차이가 존재.

   - 튜플은 한번 선언된 값을 변경할 수 X

   - 리스트는 대괄호[] 이용, 튜플은 소괄호() 이용한다.

▶튜플은 리스트에 비해 상대적으로 공간 효율적.  (기능이 제한적 + 더 적은 양의 메모리를 사용.)

a = (1, 2, 3, 4, 5, 6, 7, 8, 9)
print(a[3])	# 4
print(a[1 : 4])	# (2, 3, 4)

# 튜플은 변경 불가능.
a[2] = 7
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

① 튜플을 사용하면 좋은 경우

▶서로 다른 성질의 데이터를 묶어서 관리해야 할 때

  ⇒ 최단 경로 알고리즘에서는 (비용, 노드번호) 형태로 튜플 자료형을 자주 사용함.

  ⇒ ex) 학생 정보: (학번, 성적)

▶데이터의 나열을 해싱(Hashing)의 키 값으로 사용해야 할 때

  ⇒ 튜플은 변경 불가하므로 리스트와 다르게 키 값으로 사용될 수 있음.

▶리스트보다 메모리를 효율적으로 사용해야 할 때

 

ㅈ. 사전 자료형 (dictionary)

▶사전 자료형 : 키(Key)와 값(Value)의 쌍을 데이터로 가지는 자료형.

  ⇒ 리스트, 튜플이 값을 순차적으로 저장하는 것과 대비.

▶사전 자료형은 원하는 '변경 불가능(Immutable)한 자료형'을 키(Key)로 사용할 수 있음.

  ⇒ 리스트, 튜플이 인덱싱으로 접근했다면, 사전 자료형은 키(Key)로 접근할 수 있음.

▶사전 자료형은 해시 테이블(Hash Table)을 내부적으로 이용함.

  ⇒ 데이터의 조회 및 수정을 O(1)의 시간(상수 시간)에 처리할 수 있다는 장점. (O(1)의 시간에)

* 키 값으로 접근했을때 그 값에 매칭되는 어떠한 값을 얻고자하는 자료구조에서 효과적으로 사용됨.

data = dict()
data	# {}
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'
print(data)	# {'사과': 'Apple', '바나나': 'Banana', '코코넛': 'Coconut'}
if '사과' in data:
...     print("'사과'를 키로 가지는 데이터가 존재합니다.")	# '사과'를 키로 가지는 데이터가 존재합니다.

key	value
'사과'	'Apple'
'바나나'	'Banana'
'코코넛'	'Coconut'

▶사전 자료형에서는 키와 값을 별도로 뽑아내기 위한 메서드 keys(), values()를 지원.

▶키/값 데이터만 뽑아서 리스트로 이용할 때 사용됨.

# key값 리스트 생성
key_list = data.keys()
print(key_list)	# dict_keys(['사과', '바나나', '코코넛'])
# list형태로 출력해주려면
key_list = list(data.keys())

# value값 리스트 생성
value_list = data.values()
print(value_list)	# dict_values(['Apple', 'Banana', 'Coconut'])
# list형태로 출력해주려면
value_list = list(data.values())

# key_list를 이용해서 이에 해당하는 value값을 data에서 출력 
for key in key_list:
...     print(data[key])
...
Apple
Banana
Coconut

ㅊ. 집합 자료형

▶집합은 중복 허용X, 순서 X 특징 존재.

▶초기화

  ⇒ 집합은 리스트 or 문자열을 이용해서 초기화 가능. set() 함수를 사용.

  ⇒ 중괄호{} 안에 각 원소를 콤마, 를 기준으로 구분하여 삽입하여 초기화 가능.

▶데이터 조회 및 수정에 있어서 O(1)의 시간(상수 시간)에 처리할 수 있음.

# 집합 자료형 초기화1
data = set([1, 1, 2, 3, 4, 4, 5])
print(data)	# {1, 2, 3, 4, 5} -> 중복 값은 자동으로 제거됨.

# 집합 자료형 초기화2
data = {1, 1, 2, 3, 4, 4, 5}
print(data)	# {1, 2, 3, 4, 5}

▶집합 자료형의 연산 (합집합, 교집합, 차집합)

① 합집합: 집합 A에 속하거나 B에 속하는 원소로 이루어진 집합 (A∪B)  ==  a | b

② 교집합: 집합 A에도 속하고 B에도 속하는 원소로 (A∩B) == a & b

③ 차집합: 집합 A의 원소 중에서 B에 속하지 않는 원소들로 이루어진 집합 (A－B) == a - b

 

▶집합 자료형 관련 함수 (모두 상수시간이 소요됨)

add() : 새로운 원소 추가   ex) data.add(4)

update() : 새로운 원소 여러 개 추가   ex) data.update([5,6]) ⇒ 집합 자료형 뒤에 추가됨.

remove() : 특정한 값을 갖는 원소 삭제 (인덱싱)   ex) data.remove(2)  ⇒ 인덱스 2의 값 삭제됨.

 

* 사전자료형과 집합자료형은 순서가 없기 때문에 인덱싱으로 값에 접근 불가능.

  ⇒ 사전의 키(Key) 혹은 집합의 원소(Element)를 이용하여 O(1)의 시간 복잡도로 조회함.