[이것이 취업을 위한 코딩테스트다] 1일차 TIL

 

오늘 처음 '이것이 코딩테스트다' 강의를 들었고, 큰 틀로서는 코딩테스트가 어떤 식으로 진행되는 지 그리고 복잡도 개념과 파이썬에서 자주 사용되는 대표적인 문법을 학습하였다. 복잡도 개념은 이전부터 추상적으로만 이해를 했었는데, 오늘 강의를 통해 시간 복잡도와 공간 복잡도에 대한 개념을 이해하게 되었고 문제 풀이를 할 때 나타나는 시간 초과에 대한 개념을 이제야 이해하게 되었다. 파이썬의 문법을 학습하는 파트에서는 이미 학교 교양시간에 배웠던 내용이 있어서, 모르는 개념과 까먹었던 개념 위주로 정리를 하였다. 

 

 

< 복잡도 >

 

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

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

=> 복잡도가 낮을수록 좋은 알고리즘 

 

 

O 표기법

- 가장 빠르게 증가하는 항만을 고려하는 표기법 (함수의 상한만을 나타내게 된다) 

 

상단부터 복잡도가 좋은 순서

 

시간 복잡도 계산

 

(1)

array = [3, 5, 1, 2, 4] 
summary = 0

for x in array: 
	summary += x 

print(summary) 

# 수행시간은 데이터의 개수에 비례하여 증가함 
# O(N)

 

(2) 

array = [3, 5, 1, 2, 4] 
summary = 0

for x in array: 
	for y in array:
		temp = x * y
		print(temp)

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

 

** 코딩 테스트 문제에서 시간 제한은 통상 1~5초 (대략 5초 정도로 생각하고 문제를 푸는 것이 합리적) 

 

 알고리즘 문제 해결 과정 

1. 지문 읽기 
2. 요구사항(복잡도) 분석 
3. 문제 해결을 위한 아이디어 찾기 
4. 소스코드 설계 및 코딩 

 

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

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

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

 

 

< Phython 문법  >

 

(1) 소수부가 0일 때 0을 생략

a = 5.
print(a) # output: 5.0

 

 

(2) 정수부가 0일 때 0을 생략 

a = -.7
print(a) # output: -0.7

 

 

(3) 지수의 표현 방식 

 

  ex ) 10의 9제곱 = 1e9

=> 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단거리를 무한(INF)로 설정하곤 한다. 이때 가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9를 이용할 수 있다. 

 

 

(4) 실수형 

 

=> 개발과정에서 실수값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수 있다. 이럴 때는 round() 함수를 이용할 수 있다. 

 

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

 

 

(5) 특정 원소가 n번 반복되는 배열 생성 

n = 10
a = [0] * n
print(a) // output: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

(6) 원소의 index에 따른 원소 출력 

a = [1, 2, 3, 4]

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

#네번째 원소 값 변경 
a[3] = 7
print(a) # output: [1, 2, 3, 7]

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

 

(7) 리스트 컴프리헨션 

# 0부터 9까지의 수를 포함하는 리스트 
array = [ i for i in range(10)]
print(array)

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

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

=> 리스트 컴프리헨션은 특히 N X M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 매우 유용하다. 

 

# 잘못된 리스트 컴프리헨션 

n = 4
m = 3

array = [[0] * m] * n 

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

=> [[0] * [m]] 이 같은 객체로서 인식되어 일어나는 현상

 

 

(8) 배열 관련 자주 쓰이는 함수 

 

# 특정 인덱스에 데이터 추가 
a.insert(2,3) 
print(“인덱스 2에 3 추가: “, a) 

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

# remove_list 에 포함되지 않은 값만을 저장
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)

 

(9) 문자열 : 변경 불가능한 객체 

# 문자열 슬라이싱도 가능
a = "ABCDEF"
print(a[1:3]) # output: "BC"

 

(10) 튜블 자료형 

튜플을 사용하면 좋은 경우 

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

-  데이터의 나열을 해싱의 키 값으로 사용해야 할 때 

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

 

(11) map 함수 

# 공백 기준으로 나누고 리스트로 만들기
n = int(input())
data = list(map(int,input().split()))

print(n)
print(data)

 

(12) 출력을 위한 전형적인 소스코드 

a = 1 
b = 2 
print(a,b)
print(7, end=" ")
print(8, end=" ")

answer = 7
print("정답은" + str(answer) + "입니다") # output: 7 8 정답은 7입니다