1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

Yeonghyeon·2022년 8월 1일

코테

이코테 2021

목록 보기

1/7

본 포스팅은 (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 공부하고 정리한 글임을 밝힙니다.

코딩 테스트 개요 및 출제 경향

온라인 개발 환경(Python)

리플릿: https://repl.it/langauges/python3
- 파이썬 코드 작성 후 실행 결과 확인 가능
파이썬 튜터: http://pythontutor.com/visualize.html
- (교육 목적)코드 실행하면서 어떤 변수에 어떤 값이 담기고, 어떤 방식으로 처리되는지 확인 가능

오프라인 개발 환경(Python

파이참(Pycharm)

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

예시: https://github.com/ndb796/Python-Competitive-Programming-Team-Notes

코테 준비 과정에서 자신만의 소스코드 관리하는 습관 기르기
자신이 자주 사용하는 알고리즘 코드를 라이브러리화 해놓기

IT 기업 코딩 테스트 최신 출제 경향

가장 출제 빈도가 높은 알고리즘 유형

그리디(쉬운 난이도)
구현
DFS/BFS를 활용한 탐색

알고리즘 성능 평가

복잡도(Complexity)

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
동일한 기능 ➡️ 복잡도 낮을수로 좋은 알고리즘

단순히 소스코드가 복잡해 보이는 것(이해하기에 복잡해보인다)과는 다름!, 성능적인 측면에서 복잡도를 말함

빅오 표기법(Big-O Notion)

가장 빠르게 증가하는 항만을 고려하는 표기법
```
	- 함수의 상한만을 나타내게 됨
```
ex) 연산 횟수: $3N^3+5N^2+1,000,000$ ➡️ 빅오 표기법에선 차수가 가장 큰 항만 남기므로 $O(N^3)$ 으로 표현됨 (계수도 무시)
빅오 표기법 순위 (밑으로 내려갈수록 나쁨)
1. $O(1)$ : 상수 시간(constant time)
2. $O(logN)$ : 로그 시간(Log time)
3. $O(N)$ : 선형 시간
4. $O(NlogN)$ : 로그 선형 시간
5. $O(N^2)$ : 이차 시간
6. $O(N^3)$ : 삼차 시간
7. $O(2^n)$ : 지수 시간

시간 복잡도 계산해보기

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

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

# 모든 데이터를 하나씩 확인하여 합계 계산 (복잡도 영향 받는 부분)
for x in array:
	summary += x
 
# 결과 출력
print(summary)

수행 시간은 데이터의 개수 N에 비례할 것임을 예측 가능(모든 데이터 하나씩 확인하며 합계) ➡️ 시간 복잡도: $O(N)$
```
	- N이 10만, 100만 늘어날수록 선형으로 비례하여 복잡도가 증가하겠지
```

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

array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)

for i in array:
	for j in array:
    	temp = i * j # 5x5 = 5^2
     	print(temp

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

알고리즘 설계 Tip

일반적으로 CPU 기반의 개인 컴퓨터 or 채점용 컴퓨터에서 연산 횟수 5억 넘어가는 경우:
- Python을 기준으로 통상 5~15초 시간 소요 (C언어보다 조금 더 걸림)
- 이때 PyPy의 경우 때때로 C언어보다 빠르게 동작하기도 함
$O(N^3)$ 의 알고리즘 설계한 경우에서 N > 5,000 이라면?
코딩 테스트 문제에서 시간제한을 통상 1~5초가량이라는 점
- 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제 푸는 것이 합리적

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

가장 먼저 확인해야 하는 것: 시간제한(수행시간 요구사항)
시간제한이 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) # 수행 시간 출력

파이썬 문법

리스트 컴프리핸션

2차원 리스트를 초기화할 때 효과적으로 사용 가능
특히 $N\times M$ 크기의 2차원 리스트를 한번에 초기화할 때
- ex) array=[[0]*m for _ in range(n)]
만약 2차원 리스트를 초기화할 때 다음과 같이 작성하면 예기치 않은 결과
- 잘못된 ex) array = [[0]*m] * n
- 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식됨

리스트 관련 기타 메서드

함수별 시간 복잡도

변수명.append(): $O(1)$
변수명.sort(): $O(NlogN)$
변수명.reverse():리스트의 원소 순서를 모두 뒤집음, $O(N)$
변수명.insert(): $O(N)$
변수명.count(): $O(N)$
변수명.remove(): $O(N)$

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

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

# remove_list에 포함되지 않은 값만을 저장
result = [i for i in if i not in remove_list]
print(result)

튜플 사용하면 좋은 경우

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

집합 자료형

중복 허용하지 않고, 순서가 없다 ➡️ 어떤 데이터가 존재하는지 안하는지 여부만을 체크할 때 매우 효과적으로 사용 가능
set() 함수 이용하여 리스트 혹은 문자열 이용해서 초기화 가능
혹은 중괄호({}) 안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입함으로써 초기화 가능

    # 초기화 방법 1
    data = set([1, 1, 2, 3, 4, 4, 5])
    
    # 초기화 방법 2
    data = {1, 1, 2, 3, 4, 4, 5}

데이터 조회 및 수정: $O(1)$
합집합: a|b, 교집합: a&b, 차집합: a-b
집합 자료형 관련 함수
- .add(4): 새로운 원소 추가
- .update([5,6]): 새로운 원소 여러개 추가
- .remove(3): 특정 값을 갖는 원소 삭제

빠르게 입력 받기

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

import sys

data = sys.stdin.readline().rstrip()

f-string 예제

answer = 7
print(f"정답은 {answer} 입니다.")

조건문의 간소화

소스코드 한 줄인 경우, 줄 바꿈 할 필요없이 가능

score = 85

if score >= 80: result = "Success"
else: result = "Fail"

조건부 표현식: if~else 문을 한 줄에 작성할 수 있도록 해줌

score = 85
result = "Success" if score >= 80 else "Fail"

print(result)

람다 표현식 예시: 내장 함수에서 자주 사용되는 람다 함수

array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]

def my_key(x): # key 변수에 정렬 기준 함수 명시
	return x[1]

# key를 기준으로 정렬
# 1. 
print(sorted(array, key=my_key))
# 2.
print(sorted(array, key=lambda x: x[1]))

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

ex) 각 리스트의 원소끼리 더하기

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

result = map(lambda a, b: a + b, list1, list2)
print(list(result))

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

- 내장 함수

파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능 포함

- itertools: 반복되는 형태의 데이터 처리하기 위한 유용한 기능 제공

특히 순열과 조합 라이브러리는 코테에서 자주 사용됨 (완전 탐색 문제 유형에서 소스코드 매우 간결하게 작성하도록 도와줌)

- heapq: 힙(heap) 자료구조 제공

일반적으로 우선순위 큐 기능 구현 위해 사용됨 (대표적: Dijkstra 알고리즘 ➡️ 최단 경로 알고리즘)

- bisect: 이진 탐색(Binary Search) 기능 제공

- collections: 덱(deque), 카운터(Counter)등의 유용한 자료구조 포함

- math: 필수적인 수학적 기능 제공

팩토리얼, 제곱근, 최대공약수, 삼각함수 관련 함수부터 파이(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)

조합: 서로 다른 n개에서 순서 상관 없이 서로 다른 r개 선택하는 것
- {'A', 'B', 'C'}에서 순서 고려하지 않고 두 개 뽑는 경우: 'AB', 'AC', 'BC'

	from itertools import combinations
    
    data = ['A', 'B', 'C']
    
    result = list(combinations(data, 2)) # 모든 조합 구하기
    print(result)

중복 순열과 중복 조합

# 중복 순열
from itertools import product
    
data = ['A', 'B', 'C']
    
result = list(product(data, repeat=2)) # 2개를 뽑는 모든 순열 구하기 (중복 허용)
print(result)

# 중복 조합
from itertools import combinations_with_replacement
    
data = ['A', 'B', 'C']
    
result = list(combinations_with_replacement(data, repeat=2)) # 2개를 뽑는 모든 조합 구하기 (중복 허용)
print(result)

Counter

등장 횟수 세는 기능 제공
리스트와 같은 반복 가능한 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지 알려줌

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue')]

print(counter['blue']) # 'blue'가 등장한 횟수 출력
print(counter['green']) # 'green'가 등장한 횟수 출력
print(dict(counter)) # 사전 자료형으로 반환

최대 공약수와 최소 공배수

math 라이브러리의 gcd() 함수 이용

import math

# 최소 공배수(LCM) 구하는 함수
def lcm(a, b):
	return a * b // math.gcd(a, b)
    
a = 21
b = 14

print(math.gcd(21, 14)) # 최대 공약수 (GCD) 계산
print(lcm(21, 14)) # 최소 공배수 (LCM) 계산

Yeonghyeon

다음 포스트

1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

이코테 2021

코딩 테스트 개요 및 출제 경향

온라인 개발 환경(Python)

오프라인 개발 환경(Python

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

예시: https://github.com/ndb796/Python-Competitive-Programming-Team-Notes

IT 기업 코딩 테스트 최신 출제 경향

가장 출제 빈도가 높은 알고리즘 유형

알고리즘 성능 평가

복잡도(Complexity)

빅오 표기법(Big-O Notion)

시간 복잡도 계산해보기

알고리즘 설계 Tip

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

알고리즘 문제 해결 과정

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

파이썬 문법

리스트 컴프리핸션

리스트 관련 기타 메서드

함수별 시간 복잡도

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

튜플 사용하면 좋은 경우

집합 자료형

빠르게 입력 받기

f-string 예제

조건문의 간소화

람다 표현식 예시: 내장 함수에서 자주 사용되는 람다 함수

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

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

- 내장 함수

- itertools: 반복되는 형태의 데이터 처리하기 위한 유용한 기능 제공

- heapq: 힙(heap) 자료구조 제공

- bisect: 이진 탐색(Binary Search) 기능 제공

- collections: 덱(deque), 카운터(Counter)등의 유용한 자료구조 포함

- math: 필수적인 수학적 기능 제공

순열과 조합

Counter

최대 공약수와 최소 공배수

2. 그리디 & 구현

0개의 댓글

관련 채용 정보