코딩테스트 기초

어쩌다 보니 코테를 준비하게 되었다. 3일이라는 매우매우 짧은 시간이지만 최선을 다해 반타작 이상을 맞추는게 이번 첫 코테의 목표이다.

 

 

😈 알고리즘 성능평가 😈

 

딥러닝과 달리, 일반적으로 알고리즘을 짤때는 코드를 효율적으로 작성하는 것이 가장 중요하다. 이를 측정하기 위해 알고리즘 성능평가를 하는데, 이것이 무엇인지 다시 한번 복습하는 시간을 가지겠다.

 

1. 복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다. 크게 시간 복잡도와 공간 복잡도가 있는데, 이는 각각 알고리즘의 수행 시간과 메모리 사용량을 의미한다. 

2. 빅오 표기법

가장 빠르게 증가하는 항만을 고려하는 표기법이다. 즉 함수의 상한만을 나타낸다. (극한의 개념으로 생각하면 편하다.)

 

기본적으로 python의 경우 C언어보다 시간이 더 많이 소모되므로 이를 유의해서 코딩테스트를 준비하도록 하자! 

혹시라도 python으로 제출했을 때 시간초과, 메모리 초과가 발생한다면 동일한 코드를 pypy로 제출해보자!

 

😈 파이썬의 기본 입출력 😈

 

1. input() : 한줄의 문자열을 입력 받는 함수이다.

2. map() : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용한다.

 

예시 ) 공백을 기준으로 구분된 데이터를 입력받을 때는 다음과 같이 사용한다.

list(map(int, input().split()))     # 입력받은 문자를 먼저 공백 기준으로 구분하고, 정수형으로 만든 다음 리스트로 저장해줌

예시 ) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면 단순히 다음과 같이 사용한다.

a,b,c = map(int, input().split())   # 리스트로 치환하지 않고, a,b,c에 넣어준다.

 

3. 빠르게 입력 받기

사용자한테 입력을 최대한 빠르게 받아야 하는 경우 (시간 단축)

파이썬의 경우 sys 라이브러리에 있는 sys.stdin.realine() 메서드를 사용한다.

단, 이때 입력 후 Enter가 줄 바꿈 기호로 입력되므로 rstrip() 메소드를 함께 사용한다.

 

(이중탐색, 정렬, 그래프 등에서 자주 쓰이는 테크닉이기 때문에 꼭 기억하도록 하자!!)

 

import sys

data = sys.stdin.readline().rstrip()    # readline 다음 rstrip까지 한 묶음으로 사용한다.
print(data)

4. 출력

출력할 때 print를 쓰게 되면 줄바꿈이 일어나는데, 이를 원하지 않을 경우 print(A, end=" ")로 해결할 수 있다.

또한 f-string을 사용하여 보다 간단하게 표기할 수 있다.

ans = 9
print(f"answer is {ans}")

 

😈 람다 표현식 😈

 

람다 표현식을 이용하면 함수를 간단히 작성할 수 있는데, 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다는 점이 특징이다.

def add(a,b):
	return a+b

# 일반적인 add() 매소드 사용
print(add(3,7))

# 람다 표현식으로 구현한 add 매소드
print((lambda a,b: a+b)(3,7))

람다 표현식은 함수 자체를 입력으로 받는 상황에서 매우 유용하게 사용될 수 있다.

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

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

 

😈 자주 사용하는 내장함수 😈

 

1. sorted()

result = sorted([3,4,1,2])
reverse_result = sorted([3,4,1,2], reverse=True)

array = [('a',3),('b',1),('c',2)]
result = sorted(array, key=lambda x:x[1], reverse=True)

2. 순열과 조합

(1) 순열 : 서로 다른 n개에서 서로 다른 r개를 선택해 일렬로 나열

(2) 조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개 선택

# 1. 순열
 from itertools import permutations
 
 data = ['A','B','C']
 result = list(permutations(data,3)) # data에서 3개를 골라 순서를 고려하여 나열
 
 # 2. 조합
 from itertools import combinations
 result = list(combinations(data,2))

3. Counter

파이썬 collections 라이브러리 Counter는 횟수를 세는 기능을 제공한다.

리스트가 주어졌을 때 내부 원소가 몇번이나 등장했는지 알려준다.

from collections import Counter

counter = Counter(['a','b','a','c','a','b','d','a'])

print(counter['a'])
print(dict(counter))

여기서 counter의 결과값을 딕셔너리로 변환하면 결고값은 ['a':4, 'b':2, 'c':1, 'd':1] 이런식으로 출력될 것이다.

 

4. 최대공약수와 최소공배수

최대공약수를 구할 때는 math 라이브러리의 gcd() 함수를 이용한다.

import math

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

print(math.gcd(21,14))
print(lcm(21,14))