알고리즘-1(Python)

백엔드류·2024년 2월 7일

python 코딩테스트 코테

알고리즘

목록 보기

1/4

리스트

append() - 리스트에 원소를 하나 삽입할 때 사용 & O(1)
sort() - 기본정렬기능, 오름차순으로 정렬 & O(NlogN)
sort(reverse=True) - 내림차순으로 정렬 & O(NlogN)
reverse() - 리스트의 원소 순서를 모두 뒤집음 & O(N)
insert() - insert(삽입할 위치 인덱스,삽입값) & O(N)
count() - 변수명.count(특정값) - 리스트에서 특정값을 가지는 데이터의 개수 반환 & O(N)
remove() - remove(특정값) - 특정한 값을 갖는 원소제거,여러개면 하나만 제거 & O(N)
2차원 리스트를 초기화할때 nm크기면 array=[[0]m for _ in range(n)]
리스트에서 두 값을 교환할떄는 C[1],C[2]=C[2],C[1] 이렇게함

딕셔너리

+딕셔너리(dictionary)는 items()함수를 사용하면 딕셔너리에 있는 키와 값들의 쌍을 얻을 수 있습니다.

딕셔너리는 순서보장 x

시간복잡도 순서

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)

cf)길이가 i,j가 각각 정렬된 배열일 때 이 둘을 합쳐서 재정렬 할때의 수는 i+j이다.

기본 입출력

input() 함수는 한 줄의 문자열을 입력 받는 함수
map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용
map(적용할 함수, 순회 가능한 객체반복가능한 자료형) -
split()은 문자열을 나눠서 리스트로 만들어준다
파이썬에서 반복문이 끝날 조건이 없는 상태에서 입력이 빈 데이터를 받은 경우 eof에러를 발생시킴. 프로그램 종료 조건이 주어지지 않으면 eof를 이용 (try-except) 근데 input()보다 sys.stdin.readline()을 주로 사용하니까 이건 valueerror를 발생

순회 가능한 객체의 각 원소에 지정한 함수를 각각 적용하여 결과를 반환하는 함수인데요.
- ex) 공백을 기준으로 구분된 데이터를 입력 받을 때
list(map(int,input().split()))
- ex) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면, 단순히 다음과 같이 사용
a, b, c = map(int,input().split())

Python에서 input() 함수로 입력 받은 값은 기본적으로 문자열로 처리됩니다. 따라서 a는 문자열이 됩니다. 문자열은 시퀀스 자료형으로, 각 문자에 인덱스를 사용하여 접근할 수 있습니다. a[0]은 첫 번째 문자를 나타냅니다. 그래서 작동합니다.
2차원배열 입력받기 : 세로의 길이를 안다고 가정(B)

arr = []
for i in range(B):
arr.append(list(map(int, input().split())))
##다른 방법##
arr = [list(map(int, input().split())) for _ in range(B)]
2차원 배열 출력하기 :

	for a in arr:
		for b in a:
    		print(b,end=" ")
		print()

사용자로부터 입력을 최대한 빠르게 받아야 하는 경우가 있다. 파이썬으로 코테 문제를 풀때 입력데이터의 개수가 상당히 많다면 시간초과가 날 수 있으므로 이때는 sys 라이브러리에 정의되어 있는 sys.stdin.readline() 메서드를 이용. 단, 입력 후 엔터가 줄 바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용
ex) 이진탐색, 정렬, graph 관련 문제에서 자주 사용되는 테크닉
ex) 반복문으로 여러줄 입력받는 상황에서는 반드시 sys.stdin.readline()을 사용해야 시간초과가 발생하지 않습니다.

입력 보충 설명 : https://shinho0902.tistory.com/55

기본 출력 : print() - 기본적으로 출력 이후에 줄 바꿈을 수행 cf) 줄 바꿈을 원치 않는 경우 'end' 속성 이용 가능

a= 7
b= 8

print(a, b)
print(7, end=" ")  # 공백을 넣는다(줄바꿈 x) default = "\n"
print(8, end=" ")  

#실행결과 7 8
#        7 8

f-string : 문자열 앞에 접두사 'f'를 붙여 사용. 중괄호 안에 변수명을 기입하여 간단히 문자열과 정수를 함께 넣을 수 있음
ex) answer =1
print(f"정답은 {answer} 입니다.")

먼저 파이썬은 기본 10진수이기 때문에 다른 진수는 아래와 같이 접두어가 붙습니다.

2진수: 0b
8진수: 0o
16진수: 0x
10진수에서 2진수, 8진수, 16진수 변환
bin(), oct(), hex() 내장함수 사용 - 문자열로 반환
파이썬에서 제공하는 내장함수를 사용하면 쉽게 변환 할 수 있습니다.

value = 60

b = bin(value)
o = oct(value)
h = hex(value)

print(b)
print(o)
print(h)

//실행결과
0b111100
0o74
0x3c

다른 진수 형태에서 10진수로 변환
2진수, 8진수, 16진수에서 10진수로 변환하는 방법입니다. 여기서 변환하고자 하는 진수의 타입은 문자열이며 반환되는 10진수 결과는 정수 타입입니다.

b = int('0b111100', 2)
o = int('0o74', 8)
h = int('0x3c', 16)

print(b)
print(o)
print(h)

//실행결과
60
60
60

여러 진법의 숫자들을 연산할 경우 먼저 10진법으로 int(" ",?) 이렇게 변환하고 연산하고 최종적으로 출력하고자하는 진법으로 변환한다.
어떤 문자의 유니코드 값을 알고 싶거나, 반대로 유니코드 값을 문자로 변환할때
ord('a') //97
chr(97) //a
format(수, ".2f") 를 사용하면 원하는 자리까지의 정확도로 반올림 된 실수 값을 만들어 준다.
반올림함수 - round() ex) round(3.141592,2) -> 3.14 , round(3.141592,3) ->3.142 , round(3.141592) -> 3
비트시프트연산 - a<<1 : a에 2를 곱한값 a<<2 : a*4 a>>1 : a를 2로 나눈값
파이썬에서는 return 문을 함수내에서만 쓴다.
bool(a) : a변수값에 대한 참 거짓으로 변환 0이 아닌값은 모두 참

비트 연산자 (Bitwise Operators):
a = 60, b = 13 이라 가정한다.

a = 0011 1100

b = 0000 1101

Operator Description Example
'&' AND 연산. 둘다 참일때만 만족 (a & b) = 12 → 0000 1100
'|' OR 연산. 둘 중 하나만 참이여도 만족 (a | b) = 61 → 0011 1101
'^' XOR 연산. 둘 중 하나만 참일 때 만족 (a ^ b) = 49 → 0011 0001
'~' 보수 연산. (~a) = -61 → 1100 0011
'<<' 왼쪽 시프트 연산자. 변수의 값을 왼쪽으로 지정된 비트 수 만큼 이동 a << 2 = 240 → 1111 0000
'>>' 오른쪽 시프트 연산자. 변수의 값을 오른쪽으로 지정된 비트 수 만큼 이동 a >> 2 = 15 → 0000 1111

조건문

조건문의 기본적인 형태는 if ~ elif ~ else 이다. 조건문을 사용할 때 elif 혹은 else 부분은 경우에 따라서 사용하지 않아도 됨
논리 연산자 : and, or ,not
기타 연산자 : x in 리스트 , x not in 문자열
pass : 아무것도 처리하고 싶지 않을 때 pass 키워드를 사용
ex) 디버깅 과정에서 일단 조건문의 형태만 만들어 놓고 조건문을 처리하는 부분은 비워놓고 싶은 경우
조건문에서 실행될 소스코드가 한 줄인 경우, 굳이 줄 바꿈을 하지 않고도 간략하게 표현 가능
조건부 표현식은 if ~ else 문을 한 줄에 작성할 수 있도록 해줌(3항연산)
ex ) score = 85
result = "success" if score>=80 else "fail"
print(result) ## if 문을 가운데 끼고 왼쪽은 참일때 내용, 오른쪽인 거짓일때 내용 적기

반복문

for 문은 특정한 변수를 이용하여 'in' 뒤에 오는 데이터(리스트, 튜플 등) 에 포함되어 있는 원소를 첫번째 인덱스부터 차례대로 하나씩 방문 cf) 변수가 쓸모업다면 _로 표시
일반적으로 for 문 바로 옆에 조건문 다는건 별로. for 문 아래 들여쓰기 후 if문 쓰는게 일반적 다만 리스트 컴프리헨션등과 같은 기능을 쓰면 가능 sum(), list() 등등.
반복문에서 남은 코드의 실행을 건너뛰고, 다음 반복을 진행하고자 할 때 continue를 사용(pass랑 혼동주의!)
반복문을 즉시 탈출하고자 할 때 break를 사용

함수

global 키워드로 함수내에서 변수를 지정하면 해당 함수에서는 지역변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조함.
하지만 연산이 아닌 단순히 출력과같은 단순 기능을 쓰게되면 global 키워드를 안써도된다.
ex) a = 10
def func():
print(a)
func() #실행결과 : 10

전역변수와 함수내의 지역변수 이름이 같다면 함수는 지역변수를 우선적으로 참조함.
파이썬에서 함수는 여러개의 반환 값을 가질 수 있음.
람다함수 - ex) print((lambda a,b: a+b)(3,7))

+map(function, iterable)
function: 각 요소에 적용할 함수입니다.
iterable: 함수가 적용될 반복 가능한 객체입니다. 예를 들어, 리스트, 튜플, 세트 등이 될 수 있습니다.
map() 함수는 주어진 함수를 각 요소에 적용한 결과를 새로운 이터레이터(iterator)로 반환합니다. 결과를 보려면 리스트, 튜플 등의 다른 자료구조로 변환해야 합니다.

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

내장 함수
random : ex) 1부터 10까지 3개의 정수를 랜덤으로 뽑기(
import random
numbers = random.sample(range(1, 11), 3)
print(numbers)),
range(start, stop, step) 함수로 만들어지는 정수 중에 하나를 랜덤하게 리턴합니다. 랜덤하게 하나의 원소를 선택합니다(random.choice('abcdefghij') # Choose a random element)
itertolls : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능제공 - 특히 순열과 조합 라이브러리는 코테에서 자주 사용
heapq : 힙 자료구조를 제공 - 일반적으로 우선순위 큐 기능을 구현하기 위해 사용
bisect : 이진 탐색 기능을 제공
collections : 덱,카운터 등의 유용한 자료구조를 포함
math : 필수적인 수학적 기능을 제공 - 팩토리얼,제곱근,최대공약수,삼각함수 관련 함수부터 파이와 같은 상수를 포함
etc) sum() , min(), max() , eval()-수식으로 표현된 식을 자동으로 계산해주는 함수,sorted() , sorted() with key - key의 값을 기준으로 정렬 예를 들어 array = [('홍길동',44),('이순신',43)] 이렇게되있을때 주로 사용
순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열 - 순서 고려
- from itertools import permutations
data = ['a','b','c']
result = list(permutations(data,3)) # 모든 순열 구하기 3은 3개를 뽑는다는 뜻
print(result)
조합일 때는 import combinations을 쓰면됨\
중복순열 - import product, 중복조합 - import combinations_with_replacement
Counter - 파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능 제공
리스트와 같은 반복 가능한 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려줌
```
	from collecitons import Counter
```
counter = Counter(['red','blue','red','blue','yellow'])

print(counter['blue']) # 'blue'가 등장한 횟수 출력
최대공약수 & 최소공배수 - 최대공약수 : import math , math.gcd(?,?)
최소공배수 일때는 따로 함수 만들자.
ex) def lcm(a,b):
return a*b // math.gcd(a,b)
문자열, 리스트, 튜플, 딕셔너리 등의 값이 비어 있으면("", [], (), {}) 거짓이 되고 비어 있지 않으면 참이 된다. 숫자에서는 그 값이 0일 때 거짓이 된다.

기타 모듈 & 메서드

try:
~ 에러가 발생할 가능성이 있는 코드
except 에러 종류:
~ 에러가 발생 했을 경우 처리할 코드
예외의 이름을 모를때 - except 뒤에 아무것도 안쓰는 방법이 있고 except Exception as ex: 라고 쓰고 except 아래의 실행구문에 ex 변수를 쓰면 에러 정보를 얻어올수 있음
try:
```
# 에러가 발생할 가능성이 있는 코드
```
except Exception as ex: # 에러 종류
print('에러가 발생 했습니다', ex) # ex는 발생한 에러의 이름을 받아오는 변수
사용자가 직접 에러를 발생시키는 기능 : raise Exception # 에러 종류 , 많이 사용하면 코드를 읽기 어려워진다. 실행 흐름을 깬다는 의미로 종종쓰이곤한다(raise StopIteration)

참고 : 이코테 2021 강의 몰아보기

백엔드류

공부한 내용을 정리한 블로그입니다 & 백엔드 개발자

다음 포스트