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

샤이니·2022년 3월 2일

python 알고리즘 이코테

이코테

목록 보기

1/8

reference

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

온라인 저지 (Online Judge)

해외
- 코드포스
- 탑코더
- 릿코드 : 기업 코딩 테스트 문제 多
- 코드셰프
국내
- 백준 온라인 저지
- 코드업: 초보자 추천
- 프로그래머스
- SW Expert Academy

온라인 개발 환경

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

가장 출제 빈도가 높은 알고리즘
- 그리디
- 구현
- DFS/BFS

알고리즘 성능 평가

복잡도

낮을 수록 좋은 알고리즘!

시간 복잡도

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

Big-O Notation

가장 빠르게 증가하는 항만을 고려하는 표기법(극한!)
일반적으로 연산 횟수가 5억을 넘어가는 경우 : Python 기준 통상 5~15초 가량의 시간이 소요됨
코테 문제에서 시간 제한은 통상 1~5초 가량임

시간제한(수행시간 요구사항)

시간 제한이 1초인 문제. N의 범위가 ..
- 500 : 시간복잡도 O(N^3)
- 2000 : 시간복잡도 O(N^2)
- 100000 : 시간복잡도 O(NlogN)
- 10000000 : 시간복잡도 O(N)

파이썬 문법

지수 표현 방식

e나 E로 지수 표현할 수 O

ex) 1e9 = 10의 9제곱(1,000,000,000)

리스트 컴프리헨션

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

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

# 2차원 리스트 초기화
array = [[0]*m for _ in range(n)]

~~2차원 리스트 초기화~~ 잘못된 예시
array = [[0]*m]*n
- 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식됨.
- 즉 m길이로 만든 array이 주소값을 n번 참조하는 것이 됨.(n개의 m크기의 array가 모두 같은 객체로 인식됨) 따라서 특정 위치의 하나의 값만 변경하더라도 모두 변경될 수 있음.

문자열 연산

+ 사용해서 문자열 연결 가능(Concatenate)
인덱싱 슬라이싱 가능
- but 특정 인덱스 값을 변경할 순 X (Immutable)

튜플

() 사용
한번 선언된 값을 변경할 수 없음
리스트에 비해 상대적으로 공간 효율적임

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

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

사전 자료형

Key와 Value 쌍을 데이터로 가지는 자료형
- 리스트나 튜플처럼 값을 순차적으로 저장하는 것이 X
변경 불가능한(Immutable) 자료형을 키로 사용할 수 있음

파이썬의 사전 자료형은 Hash Table을 사용 → 데이터의 조회 및 수정에 있어 O(1) 시간에 처리 가능

data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
print(data)
#결과 : {'사과':'Apple', '바나나':'Banana'}

data = {
			'사과' : 'Apple',
          '바나나' : 'Banana'
} #이렇게 초기화도 가능

if '사과' in data:
	print("사과를 키로 가지는 데이터 존재함")
  # 결과 : 사과를 키로 가지는 데이터 존재함

키(Key)	값(Value)
사과	Apple
바나나	Banana

keys() 함수 : key 데이터만 뽑아서 리스트로 사용
values() 함수 : value 데이터만 뽑아서 리스트로 사용

key_list = data.keys()
value_list = data.values()

print(key_list)
print(value_list)
#결과 : ['사과', '바나나']
# 		['Apple', 'Banana']

for key in key_list :
	print(data[key])
#결과 : Apple 
#		Banana

집합 자료형

중복 허용 X
순서 X
→ 따라서 데이터의 존재 유무 체크시 사용
초기화 방법
- 리스트 혹은 문자열을 이용
  - set() 함수 사용
- {} 안에 ,를 기준으로 구분하여 삽입하여 초기화
데이터의 조회 및 수정에 있어 O(1) 시간에 처리 가능

data = set([1, 1, 2, 2, 2]) #중복 제거됨
# 결과 : {1,2}
data = {1, 1, 2, 2, 2} #중복 제거됨
# 결과 : {1,2}

집합 연산인 합집합 |, 교집합 &, 차집합 - 사용 가능
add() 함수 : 새로운 원소 추가
update() 함수 : 새로운 원소 여러개 추가
remove() 함수 : 특정 값을 갖는 원소 삭제

기본 입출력

input() 함수 : 한 줄의 문자열을 입력 받는 함수
map() 함수 : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용

list(map(int, input().split()))
a, b, c = map(int, input().split())

빠르게 입력 받기

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

import sys

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

자주 사용되는 표준 출력 방법

파이썬에서 기본 출력은 print() 함수를 이용
- 각 변수를 콤마(,)를 이용하여 띄어쓰기로 구분하여 출력 가능
print()는 기본적으로 출력 이후에 줄바꿈을 수행
- 줄바꿈을 원치 않는 경우 end 속성 이용 가능

# 출력할 변수들
a = 1
b = 2
print(a, b)
print(7, end=" ")
print(8, end=" ")

# 출력할 변수
answer = 7
print(" 정답은 " + str(answer) + "입니다.")

>>> 1 2
>>> 7 8 정답은 7입니다.

f-string 예제

파이썬 3.6부터 사용 가능. 문자열 앞에 접두사 'f'를 붙여 사용
중괄호 안에 변수명을 기입하여 간단히 문자열과 정수를 함께 넣을 수 있음

answer = 7
print(f"정답은 {answer}")

>>> 정답은 7

파이썬의 pass 키워드

아무것도 처리하고 싶지 않을 때 pass 사용

ex) 디버깅 과정에서 일단 조건문의 형태만 만들어 놓고 조건문을 처리하는 부분은 비워놓고 싶은 경우

score = 85

if score >= 80:
    pass # 나중에 작성할 소스코드
else:
    print("성적이 80점 미만입니다.")

print("프로그램을 종료합니다.")

#결과 : 프로그램을 종료합니다.

continue

반복문에서 남은 코드의 실행을 건너뛰고, 다음 반복을 진행하고자 할 때 continue를 사용

#1부터 9까지의 홀수의 합을 구하기
result = 0

for i in range(1, 10):
    if i % 2 == 0:
        continue # 건너뛰기
    result += i

print(result)

# 학생들의 합격 여부 판단
# 특정 번호의 학생은 제외하기

scores = [90, 85, 77, 65, 97]
cheating_student_list = {2, 4}

for i in range(5):
    if i + 1 in cheating_student_list:
        continue
    if scores[i] >= 80:
        print(i + 1, "번 학생은 합격입니다.")

#결과: 1 번 학생은 합격입니다.
# 5 번 학생은 합격입니다.

break

반복문을 즉시 탈출하고자 할 때 break를 사용

#1부터 5까지의 정수를 차례대로 출력
i = 1

while True:
    print("현재 i의 값:", i)
    if i == 5:
        break
    i += 1

함수

특정한 작업을 하나의 단위로 묶어 놓은 것
함수를 사용하면 소스코드의 반복을 줄일 수 있음
내장 함수 : 파이썬이 기본적으로 제공하는 함수
사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수
- 매개 변수(parameter) : 함수 내부에서 사용할 변수
- 변환 값(argument) : 함수에서 처리 된 결과를 반환

Parameter 지정

파라미터의 변수를 직접 지정할 수 있음
- 매개변수의 순서가 달라도 상관 없음

def sub(a, b):
    print('함수의 결과:', a - b)

sub(b = 3, a = 7)

# 함수의 결과: 4

global 키워드

global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조하게 됨
- 전역 변수와 지역변수가 동일한 이름일 때 global을 쓰지 않을 경우, 함수는 지역변수를 우선적으로 처리함

a = 10

def func():
    global a #전역 변수
    a += 1
	print(a)
    
func()
# 11

여러 개의 반환 값

파이썬에서 함수는 여러 개의 반환 값을 가질 수 있음 (패킹이라 함)

def operator(a, b):
    add_var = a + b
    subtract_var = a - b
    multiply_var = a * b
    divide_var = a / b
    return add_var, subtract_var, multiply_var, divide_var 

a, b, c, d = operator(7, 3)
print(a, b, c, d)

람다 표현식 🔥

특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있음

def add(a, b):
    return a + b
    
# 일반적인 add() 메소드 사용
print(add(3, 7))

# 람다 표현식
print((lambda a, b: a + b)(3, 7))

# 내장 함수에서 자주 사용되는 람다 함수

#튜플형태 리스트를 정수 기준으로 정렬하기
array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]

def my_key(x):
    return x[1]
#key 속성 = 정렬 기준
print(sorted(array, key=my_key)

#위와 같은 결과~
print(sorted(array, key=lambda x: x[1]))


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

# 여러 개의 리스트에 동일한 규칙 적용

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

#a,b 변수가 있을 때 a+b 구하기 -> a,b는 각각 list1, list2에서 가져옴
result = map(lambda a, b: a + b, list1, list2)

print(list(result))

# [7, 9, 11, 13, 15]

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

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

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

# min(), max()
min_result = min(7, 3, 5, 2)
max_result = max(7, 3, 5, 2)
print(min_result, max_result)

# eval()
result = eval("(3+5)*7")
print(result)

# 15
# 2 7
# 56

# sorted()
result = sorted([9, 1, 8, 5, 4])
reverse_result = sorted([9, 1, 8, 5, 4], reverse=True)
print(result)
print(reverse_result)

# sorted() with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted(array, key=lambda x: x[1], reverse=True)
print(result)

# [1, 4, 5, 8, 9]
# [9, 8, 5, 4, 1]
# [('이순신', 75), ('아무개', 50), ('홍길동', 35)]

순열과 조합

모든 경우의 수를 고려해야할 때 사용하는 라이브러리
순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것
- {'A', 'B', 'C'}에서 세 개를 선택하여 나열하는 경우 : 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'
조합 : 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것
- {'A', 'B', 'C'}에서 순서를 고려하지 않고 두 개를 뽑는 경우 : 'AB', 'AC', 'BC'

# 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것
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개를 선택하는 것

from itertools import combinations

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

result = list(combinations(data, 2)) # 2개를 뽑는 모든 조합 구하기
print(result)

# [('A','B'), ('A','C'), ('B','C')]

Counter

파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공
리스트와 같은 반복 가능한(Iterable) 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려줌

from collections import Counter

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

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

# 3
# 1
# {'red': 2, 'blue': 3, 'green': 1}

최대 공약수와 최소 공배수

최대 공약수를 구해야 할 때는 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) 계산

# 7
# 42

샤이니

다음 포스트

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

이코테

reference

온라인 저지 (Online Judge)

온라인 개발 환경

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

알고리즘 성능 평가

복잡도

Big-O Notation

시간제한(수행시간 요구사항)

파이썬 문법

지수 표현 방식

리스트 컴프리헨션

문자열 연산

튜플

사전 자료형

집합 자료형

기본 입출력

빠르게 입력 받기

자주 사용되는 표준 출력 방법

f-string 예제

파이썬의 pass 키워드

continue

break

함수

Parameter 지정

global 키워드

여러 개의 반환 값

람다 표현식 🔥

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

순열과 조합

Counter

최대 공약수와 최소 공배수

[이코테] Greedy

0개의 댓글