[📚이코테 #0] 코딩 테스트 출제 경향 분석 및 파이썬 문법 🔥

출처 : https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

🤔 코딩테스트란?

• 기업/기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행되는 일종의 문제 풀이 시험
• 공개채용을 하는 기업에서는 코딩 테스트를 주로 이용합니다.
  • 문제 해결 역량을 평가할 수 있습니다.
  • 채점 시스템을 통해 응시자의 수를 효과적으로 줄일 수 있습니다.
    
    

🤔 온라인 저지란?

• 프로그래밍 대회나 코딩테스트에서 나올 법한 문제들을 시험해보는 온라인 시스템
• 해외 : 릿코드 추천
• 국내 : 백준, 코드업, 프로그래머스 추천
  

🤓 자신만의 소스코드 관리하기

• 자신만의 소스코드를 관리하는 습관
• 자신이 자주 사용하는 알고리즘 코드를 라이브러리화
• 팀 노트 예시) https://github.com/ndb796/Python-Competitive-Programming-Team-Notes

🌐 IT 기업 코딩 테스트 출제 경향 (2016 ~ 2019)

• 가장 출제 빈도가 높은 알고리즘 유형
  • 그리디 (쉬운 난이도)
  • 구현
  • DFS/BFS를 활용한 탐색

🌐 주요 기업 코딩테스트 유형 분석

카카오 코딩 테스트 문제 해설 모아보기
👉🏻 https://tech.kakao.com/careers/

• 2018
  

• 2019
  

📝 기업별 유형 정리

삼성 : 완전 탐색, DFS/BFS & 거의 다 맞아야 함
카카오 : 다양한 문제 유형, 구현(특히 문자열) & 절반 정도면 평타
라인 : 구현, 탐색, 다이나믹 프로그래밍 & 절반 정도면 평타

🤓 알고리즘 성능 평가

복잡도

• 알고리즘의 성능을 나타내는 척도, 낮을 수록 좋다.

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

빅오 표기법

• 함수의 상한만을 나타냄 👉🏻 극한과 비슷

파이썬 자료형 별 주요 연산자의 시간 복잡도 링크
👉🏻 https://wayhome25.github.io/python/2017/06/14/time-complexity/

예시 1) 연산 횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘이

👉🏻 시간 복잡도: O(N^3) 차수가 가장 큰 항만 남기므로 ✅

예시 2) N개의 데이터의 합을 계산하는 프로그램 예제

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

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
summary += x

# 결과를 출력
print (summary)

👉🏻 시간 복잡도: O(N)

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

array = [3, 5, 1, 2, 4]	 # 5개의 데이터(N = 5)
for i in array:
	for j in array:
		temp = i * j
print(temp)

👉🏻 시간 복잡도: O(N^2)

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

📝 시간 복잡도 정리

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

문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)
시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 아래와 같다.

• N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계
• N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계
• N의 범위가 100.000인 경우: 시간 복잡도가 O(NLogN)인 알고리즘을 설계
• N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계
  
  

소스코드를 통한 수행시간 측정

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

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

📚 파이썬 문법(일부)

실수형

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

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

지수 표현 방식

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

# 752.5
a = 75.25e1
print(a)

# 3.954
a = 3954e-3
print(a)

리스트 컴프리헨션 (좋은 예시)

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

리스트 컴프리헨션 (잘못된 예시)

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

array[1][1] = 5
print(array)

튜플을 사용하면 좋은 경우

• 서로 다른 성질의 데이터를 묶어서 관리해야 할 때
  • 최단 경로 알고리즘에서는 (비용, 노드 번호)의 형태로 튜플 자료형을 자주 사용한다.
• 데이터의 나열을 해(Hashing)의 키 값으로 사용해야 할 때
  • 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다.
• 리스트보다 메모리를 효율적으로 사용해야 할 때

집합 자료형

• 집합은 다음과 같은 특징이 있습니다.
  • 중복을 허용하지 않습니다.
  • 순서가 없습니다.
• 집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있습니다.
  • 이때 set() 함수를 이용합니다.
• 혹은 중괄호 ({})안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입함으로써 초기화 할 수 있습니다.
• 데이터의 조회 및 수정에 있어서 0(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 = set([1, 2, 3, 4, 5])
b = set([3, 4, 5, 6, 7])
# 합집합
print(a ! b)   # {1, 2, 3, 4, 5, 6, 7}
# 교집합
print(a & b)   # {3, 4, 5}
# 차집합
print(a - b)   # {1, 2}

# 새로운 원소 추가
a.add(4)

# 새로운 원소 여러 개 추가
a.update([5, 6])

# 특정한 값을 갖는 원소 삭제
a.remove(3)

빠르게 입력 받기

• 사용자로부터 입력을 최대한 빠르게 받아야 하는 경우가 있습니다.
• 파이썬의 경우 sys 라이브러리에 정의되어 있는 sys.stdin.readline() 메서드를 이용합니다.
• 단, 입력 후 엔터(Enter)가 줄 바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용합니다.

import sys
# 문자열 입력 받기
data = sys.stdin.readline().rstrip()
print(data)

global 키워드

• global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조하게 됩니다.

a = 0

def func():
	global a 
    a += 1
    
for i in range(10):
	func()

print(a)    # 10

람다 표현식

• 람다 표현식을 이용하면 함수를 간단하게 작성할 수 있습니다.
• 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다는 점이 특징입니다.

# 람다 표현식으로 구현한 더하기 메서드
print((lambda a, b: a + b)(3, 7))   # 10

람다 표현식 예시: 여러 개의 리스트에 적용

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = map(lambda a, b: a + b, list1, list2)
print(list(result))   # [7, 9, 11, 13, 15]

실전에서 유용한 표준 라이브러리

• 내장 함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공합니다.
  • 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있습니다.
• itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공합니다.
  • 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용됩니다.
• heapq: 힙(Heap) 자료구조를 제공합니다.
  • 일반적으로 우선순위 큐 기능을 구현하기 위해 사용됩니다.
• bisect: 이진 탐색(Binary Search) 기능을 제공합니다.
• collections: 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함합니다.
• math: 필수적인 수학적 기능을 제공합니다.
  • 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)와 같은 상수를 포함합니다.

순열과 조합

순열: 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것

• {'A', 'B', 'C'}에서 세 개를 선택하여 나열하는 경우: 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'

from itertools import permutations

data = ['A', 'B', 'C']	# 데이터 준비
result = list(permutations(data, 3))  # 모든 순열 구하기

print(result)

# 실행 결과
[('A','B','C'), ('A','C','B'), ('B','A','C'), 
('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

조합: 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것

• {'A', 'B', 'C'}에서 순서를 고려하지 않고 두 개를 뽑는 경우: 'AB', 'AC', 'BC'

from itertools import combinations

data= ['A', 'B', 'C']  # 데이터 준비
result = list(combinations(data, 2)) # 2개를 뽑는 모든 조합 구하기

print(result)

# 실행 결과: [('A','B'), ('A','C'), ('B','C')]

중복 순열과 중복 조합

from itertools import product

data=['A', 'B', 'C'] # 데이터 준비

# 2개를 뽑는 모든 순열 구하기 (중복 허용)
result = list(product(data, repeat=2)) 

print(result)




from itertools import combinations_with_replacement

data=['A', 'B', 'C'] # 데이터 준비

# 2개를 뽑는 모든 조합 구하기 (중복 허용)
result = list(combinations_with_replacement(data, 2)) 

print(result)