유튜브 동빈나 채널의 "이것이 코딩테스트다" 를 보고 정리한 내용입니다.
01~05강 까지의 강의 내용 정리
복잡도 알고리즘의 성능을 나타내는 척도
- 시간복잡도 알고리즘의 수행 시간 분석
- 공간복잡도 알고리즘의 메모리 사용량 분석
복잡도가 낮을 수록 좋은 알고리즘
빅오 표기법
차수가 가장 큰 항만 남기고 계수는 무시한다
상수시간
로그시간
선형시간 linear
로그 선형시간
이차 시간
삼차 시간
지수 시간
# N개의 데이터의 합을 계산하는 프로그램 예제
array = [3, 5, 1, 2, 4] # 5개의 변수(N=5)
summary = 0 # 합계를 저장할 변수
# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
summary += x
# 결과를 출력
print(summary)
수행시간은 for문 돌릴때 N개의 변수만큼 확인하니까 시간 복잡도는 0(N)
# 2중 반복문을 이용하는 예제
array = [3, 5, 1, 2, 4] # 5개의 변수(N = 5)
for i in array:
for j in array:
temp = i * j
print(temp)
i * j가 반복되는 횟수는 25번 (변수 5개)
시간복잡도 O(N2제곱)
파이썬으로 제출하면 C언어보다 많은 시간이 소모, pypy의 경우 c언어보다 빠르게 동작하기도 한다
파이썬이랑 pypy 번갈아 가면서 제출해보기
코딩 테스트 문제는 수행 시간 제한 1~5초 가량에 풀어야 한다
문제에서 가장 먼저 확인해야 하는 내용 시간제한(수행시간 요구사항)
시간제한이 1초인 경우
N의 범위가 500인 경우: 시간 복잡도가 O(N3)인 알고리즘 설계
N의 범위가 2,000인 경우: 시간 복잡도가 O(N2)인 알고리즘 설계
N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘 설계
N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘 설계
알고르즘 문제 해결 과정
1. 지문 읽기 및 컴퓨터적 사고 -> 최대한 간결하게 쪼개라
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩
난 누구보다 문제를 간결하게 창의적으로 풀 수 있다!!
# 수행 시간 측정 소스코드 예제
import time # 표준라이브러리 time 불러오기
start_time = time.time() # 측정 시작
#프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) #수행 시간 출력
자료형
정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등
수 자료형 수를 나타내기 위해 사용하는 자료형
integer 정수형 양의 정수 음의 정수 0
# 양의 정수
a = 1000
print(a)
# 음의 정수
a = -7
print(a)
# 0
a = 0
print(a)
실행결과
1000
-7
0
실수형
0.7 을 .7이라고 작성해서 대입할 수 있다 # 정수부가 0일 때 0을 생략
a = 157.93
print(a)
a = 5. # 소수부가 0일 때 0을 생략
print(a)
실행결과
157.93
5.0
지수표현 방식 -> 실수형, 임의의 큰수를 표현하기 위해 사용(그래프, 최단 경로 알고리즘)
e나 E 다음에 오는 수는 10의 지수부를 의미
유효숫자e지수 = 유효숫자 * 10지수
1e9 = 10의 9제곱(1,000,000,000) #10억, 임의의 INF값 대신으로 표현
# 1,000,000,000의 지수 표현 방식
a = 1e9
print(a)
# 752.5
a = 75.25e1
print(a)
# 3.954
a = 3954e-3
print(a)
실행결과
1000000000.0
752.5
3.954
지수표현 방식은 실수로 표현되기 때문에 int()로 묶어서 정수형으로 변환하여 처리하기
1을 3으로 나눈 값 0.3333333333....
10진수 에서 정확하게 표현하지 못하는 값 1/3
2진수 체계 컴퓨터는 표현상에 정확도 한계가 더 많다
a = 0.3 + 0.6
print(a)
if a == 0.9:
print(True)
else:
print(False)
실행결과
0.8999999999999999
False
이때 표현상의 한계를 극복하기 위해서 round() 함수 권장됌.
소수점 아래 몇 자리까지 값을 보장
123.456을 소수 셋째 자리에서 반올림하고 싶으면,
rount(123.456, 2)
결과값 123.45
a = 0.3 + 0.6
print(round(a,4))
if round(a,4) == 0.9:
print(True)
else:
print(False)
실행결과
0.9
True
수 자료형의 연산
별도의 수학 라이브러리 없이 기본 연산자로 다양한 연산이 가능
파이썬에서 나누기(/)는 실수형으로 반환
나머지 연산자(%) -> 홀수, 짝수
몫 연산자(//)
거듭 제곱 연산자(**)
a = 7
b = 3
# 나누기
print(a / b)
#나머지
print(a % b)
# 몫
print(a // b)
실행결과
2.333333333333333
1
2
리스트 자료형 [ , ] list() []
C나 자바에서의 array(배열)의 기능 및 연결 리스트와 유사한 기능 지원
유사한 속성을 가진 정보가 여러개 담겨야 할때
배열 혹은 테이블이라고 불림
리스트의 원소 접근할때는 인덱스(index) 값을 괄호에 넣는다
- 인덱스는 0부터 시작
# 리스트 초기화
# 직접 데이터를 넣어 초기화
a = [ 1, 2, 3, 4, 5, 6]
print(a)
# 네번째 원소만 출력
print(a[3])
# 크기가 N이고, 모든 값이 0인 1차원 리스트 초기화
n = 10
a = [0] * n # 크기가 1인 리스트를 10개 만들기
print(a)
실행결과
[1, 2, 3, 4, 5, 6]
4
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
리스트의 인덱싱
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a[-1]) # 뒤에서 첫 번째 원소 출력, 뒤쪽부터 출력 -1부터 작아지는 방식
print(a[-3]) # 뒤에서 세 번째 원소 출력
a[3] = 7 # 네 번째 원소 값 변경
print(a)
실행 결과
9
7
[1 , 2, 3, 7, 5, 6, 7, 8, 9]
리스트의 슬라이싱
(:)을 이용하여 시작 인덱스와 끝 인덱스 설정
- 끝 인덱스는 실제 인덱스보다 1을 더 크게 설정
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a[1:4]) # 두 번째 원소부터 네 번째 원소까지
실행 결과
[2, 3, 4]
리스트 컴프리헨션 -> 2차원 리스트 초기화에 효과적
대관호 안에 조건문과 반복문을 적용하여 리스트 초기화
# 0부터 9까지의 수를 포함하는 리스트
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부터 9까지의 수들의 제곱 값을 포함하는 리스트
array = [i * i for i in range(10)]
print(array)
실행 결과
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# N X M 크기의 2차원 리스트 초기화(잘한 예)
n = 3
m = 4
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], [0, 5, 0, 0], [0, 0, 0, 0]]
# N X M 크기의 2차원 리스트 초기화(잘못한 예)
n = 3
m = 4
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], [0, 5, 0, 0], [0, 5, 0, 0]]
a = [1, 4, 3]
print("기본 리스트: ", a)
a.append(2)
print("삽입: ", a)
a.sort()
print("오름차순 정렬: ", a)
a.sort(reverse=True)
print("내림차순 정렬: ", a)
실행 결과
기본 리스트: [1, 4, 3]
삽입: [1, 4, 3, 2]
오름차순 정렬: [1, 2, 3, 4]
내림차순 정렬: [4, 3, 2, 1]
a = [4, 3, 2, 1]
a.reverse()
print("원소 뒤집기: ", a)
a.insert(2, 3)
print("인덱스 2에 3 추가: ", a)
print("값이 3인 데이터 개수: ", a.count(3))
a.remove(1) # 특정 원소 하나만 제거
print("값이 1인 데이터 삭제: ", a)
실행 결과
원소 뒤집기: [1, 2, 3, 4]
인덱스 2에 3 추가: [1, 2, 3, 3, 4]
값이 3인 데이터 개수: 2
값이 1인 데이터 삭제: [2, 3, 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]
print(result)
실행 결과
[1, 2, 4]
문자열 자료형
큰따옴표(")나 작은 따옴표(') 이용
백슬래시(\) 이스케이프 문자 사용
data = 'Hello World'
print(data)
data = "Don't you know \"Python\"?"
print(data)
Hello World
Don't you know "Python"?
문자열 덧셈(+)과 곱셈(*) 연산 가능
인덱스 값 변경 할수 없음
a = "Hello"
b = "World"
print(a + " " + b) # 문자열 덧셈
a = "String"
print(a * 3) # 문자열 곱셈
a = "ABCDEF"
print(a[2:4]) # 문자열 슬라이싱
실행 결과
Hello World
StringStringString
CD
튜플 자료형 ()
한번 선언된 값은 변경 할 수 없음 -> 문자열과 유사
- 리스트에 비해 상대적으로 공간 효율적
- 서로 다른 성질의 데이터 묶어서 관리
최단 경로 알고리즘에서 (비용, 노드 번호)의 형태로 사용
- 데이터의 나열을 해싱(Hashing)의 키 값으로 사용할 때(변경이 불가하기 때문에)
a = (1, 2, 3, 4, 5, 6, 7, 8, 9)
# 네 번째 원소만 출력
print(a[3]) # 특정 원소에 접근할 때 리스트처럼
# 두 번째 원소부터 네 번째 원소까지
print(a[1:4])
실행 결과
4
(2, 3, 4)