[ Python ] 코딩 테스트에 꼭 필요한 파이썬 문법

🙇‍♀️🙇‍♀️🙇‍♀️🙇‍♀️🙇‍♀️

(이코테 2021 강의 몰아보기) 1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

 

 

감사합니다...감사합니다..!!!

가뭄의 단비같은 강의를 보고 메모한 내용

온라인 코테

- 타인과 문제풀이를 공유하지 않는 선에서 인터넷 검색 허용

오프라인 코테

- 시험장에 방문하여 치르는 시험

- 인터넷 검색 안됨.

팁 1

알고리즘 코드나 노트를 만들면 좋다

팀 노트같은것을 만드는걸 추천(대회나갈때)

👓 출제경향

2~5시간 가량의 시간

- 그리디

- 구현

- DFS / BFS

✨ 알고리즘 성능평가

복잡도(complexity)

알고리즘의 성능을 나타내는 척도

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

복잡도의 표기

빅오 표기법(Big-O Notation)

가장 빠르게 증가하는 항만을 고려하는 표기법(함수의 상한을 나타냄)

차수가 가장 큰 항만 남긴다

극한의 개념으로 생각하면 된다.

순위	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2")	지수 시간

상수 시간으로 갈수록 성능이 좋다

알고리즘 설계 Tip

일반적으로 연산 횟수가 5억을 넘어가는 경우

python을 기준으로 통상 5~15초가량의 시간이 소요

pypy의 경우 때때로 C언어보다도 빠르게 동작하기도 한다.

따라서 문제에서 먼저 확인해야 하는 내용은 시간제한

• 시간제한이 1초인 문제를 만났을 때 일반적인 기준
  1. N의 범위가 500인 경우 : 시간 복잡도가 O(N^3) 이하
  2. 범위가 2000 : 시간 복잡도가 O(N^2)
  3. 범위가 100000 : 시간 복잡도가 O(NlogN)
  4. 범위가 10000000 : 시간 복잡도가 O(N)인 알고리즘

 

✨ 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩
   일반적으로 대부분은 핵심 아이디어를 캐치한다면 풀 수 있게 출제됨

Tip 2
수행 시간 측정하기

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

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

 

 

📚 자료형

모든 프로그래밍은 데이터를 다루는 행위 => 자료형을 알아야 한다
파이썬의 자료형

1. 정수형
2. 실수형
3. 복소수형
4. 문자열
5. 리스트
6. 튜플
7. 사전
   파이썬은 많은 자료형을 제공하기 때문에 좋은 기능들을 간단하에 이해할 수 있다

정수형

• 정수를 다루는 자료형
• 양의 정수, 음, 0

실수형

• 소수점 아래의 데이터를 포함하는 수 자료형
• 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리된다
• 소수부가 0이거나 정수부가 0이면 생략하고 샤용할 수 있다.
• 추가*
• 오늘날 가장 널리 쓰이는 IEEE754표준에서는 실수형 저장을 위해 4바이트 혹은 8바이트의 고정된 크기의 메모리를 할당하므로, 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가진다

지수 포현 방식

• e나 E를 이용한 지수 표현 방식을 이용
• e나 E 다음에 오는 수는 10의 지수부를 의미
• ex 1e9라고 입력하면 10의 9제곱이 된다
• 유효숫자e지수 = 유효숫자 * 10^지수
• 임의의 큰 수를 표현하기 위해 자주 사용된다.
• 실수형 데이터로 출력이 된다

 

✍ 수 자료형의 연산

• 나누기 연산자 : / 결과를 실수형으로 반환
• 나머지 연산자 : % 나머지를 반환
• 몫 연산자 : // 몫을 반환
• 거듭 제곱 연산자 : **

✍ 리스트 자료형

• 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형
• 연속적인 데이터가 메모리에 올라가 있을 때 귀에 붙일 수 있는 append()와 pop() 함수를 제공한다 : 다른 자료형보다 좋은 함수를 제공한다
• 테이블이나 배열이라고 부르기도 한다.

리스트 초기화

• 대괄호 안에 원소를 넣어 초기화하며, 쉼표로 원소를 구분
• 비어 있는 리스트 선언 시 list() 나 []을 이용할 수 있다
• index 값은 0부터 시작함
• a = [0] * n 같은 식으로 초기화가 가능하다

리스트의 인덱싱과 슬라이싱

• 인덱스 값을 입력하여 리스트의 특정 원소에 접근하는 것 = indexing
• 파이썬의 인덱스 값은 양의 정수와 음의 정수를 모두 사용할 수 있다
• 음의 정수를 넣으면 원소를 거꾸로 탐색한다.
• 연속적인 위치를 갖는 원소들을 가질 때는 Slicing을 이용할 수 있다 arr[a:b]

리스트 컴프리헨션

• 리스트를 초기화하는 방법 중 하나
• 대괄호 안에 조건문과 반복문을 적용하여 리스트 초기화 가능
• array = [i for i in range(10)] 0부터 9까지 값들이 배열로 들어감.
• array = [i for i in range(20) if i% 2 ==1] 이렇게 뒤에 if를 사용해 if가 참일 때만 리스트에 담겠다는 것을 나타낼 수도 있다.
• 2차원 리스트를 초기화할때 효과적임 [[0] *m for _ in range(n)]

Tip 3
언더바는 언제 사용하나요?

• 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 사용
• for _ in range(n)

 

리스트 관련 기타 메서드

함수	기능	시간복잡도
arr.append()	리스트에 원소를 하나 삽입할 때 사용	O(1)
arr.sort()	기본 정렬 기능으로 오름차순 정렬	O(NlogN)
arr.sort(reverse=True)	내림차순으로 정렬
arr.reverse()	리스트의 원소를 뒤집는다	O(N)
arr.insert(삽입위치, 삽입 값)	특정 인덱스 위치에 원소 삽입	O(N)
arr.count(특정 값)	리스트에서 특정 값을 가지는 데이터의 개수를 셀 때	O(N)
arr.remove(특정 값)	리스트에서 특정 값을 가지는 원소를 제거, 여러 개면 하나만 제거한다	O(N)

 

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

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

result = [i for i in a if i not in remove_set]
print(result)

집합 자료형을 이용해서 제거할 수 있다
집합 자료형은 특정한 자료의 유무를 파악할 때 좋다

 

 

✍ 문자열 자료형

• 문자열 변수를 초기화할 때는 ""나 '' 를 이용한다
• 문자열 안에 큰따옴표나 작은따옴표가 포함되어야 하는 경우가 있다
  • 전체 문자열이 큰 / 작은이면 내부를 다르게 할 수 있다
  • 백슬래시 \를 이용하면 원하는 만큼 포함시킬 수 있다

문자열 연산

• 문자열 변수에 덧셈을 이용하면 문자열이 연결된다
• 문자열 변수를 양의 정수와 곱하면 문자열이 그 만큼 더해짐
• 문자열에서도 인덱싱과 슬라이싱을 이용할 수 있지만 문자열을 변경할 수는 없다 a[2] = 'a' 이런식으로는 쓸 수 없음

 

 

✍ 튜플 자료형

• 리스트와 유사하지만 한 번 선언된 값을 변경할 수 없다
• 리스트는 대괄호, 튜플은 소괄호()
• 리스트에 비해 적은 양의 메모리를 사용한다
• a[3]이나 a[2:]처럼 사용할 수 있다

튜플을 사용하면 좋은 경우

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

 

✍ 사전 자료형

• 키와 값의 쌍의 데이터를 가진다
• 원하는 '변경 불가능한' 자료형을 키로 사용할 수 있다.
• 사전 자료형은 해시 테이블(Hash Table)을 이용하므로 데이터의 조회 및 수정에서 O(1)의 시간(상수시간)에 처리할 수 있다.
• data = dict() data['사과'] = Apple
• if '사과' in data: print('사과') 처럼 작성해서 key가 존재하는지 확인할 수 있다. 이 때 소요되는 시간이 상수시간.

사전 자료형 관련 메서드

• key 데이터만 뽑아서 리스트로 이용할 때는 keys() 함수
• value만 뽑아서 리스트로 이용할 때는 values() 함수
• key와 value가 출력될 때는 (['고양이', '강아지']) 이런 식으로 출력되기 때문에 list로 이용하려면 list 처리를 해주어야 한다.

 

✍ 집합 자료형

• 중복을 허용하지 않는다
• 순서가 없다 : 존재 여부를 찾을 때 좋다
• list나 문자열을 이용해서 초기화할 수 있다
  • 이 때 set() 함수를 이용
• 혹은 중괄호 안에 각 원소를 콤마를 기준으로 구분하여 삽입함으로 초기화 할 수 있다
• 조회 및 수정을 상수 시간만에 할 수 있다 O(N)

집합 자료형의 연산

• 합집합 : |
• 교집합 : &
• 차집합 : -

집합 자료형 관련 함수

• 추가할 때는 data.add(새로운 원소)
• 여러개 추가할 때 :ㅣ data.update([1,2])
• 특정한 값을 갖는 원소 삭제 : data.remove()

 

 

 

📚 기본 입출력

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

• input() 함수는 한 줄의 문자열을 입력 받는 함수
• map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용
• split()을 쓰면 공백을 기준으로 각각 함수를 적용한다.

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

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

• 기본 출력은 print() 함수를 사용
• 각 변수를 ,로 구분하여 출력할 수 있다
• 기본적으로 출력 후 줄바꿈이 시행되는데 이것이 싫으면 end=" "를 이용하면 된다

f-string

• 파이썬 3.6부터 사용 가능, 문자열 앞에 접두사 f를 붙여 사용한다
• 중괄호 안에 변수명을 기입하여 문자열과 정수를 함께 넣을 수 있음.
  print(f"정답은 {answer}입니다.")

 

 

📚 조건문과 반복문

 

📌조건문

• 프로그램의 흐름을 제어하는 문법
• 조건에 따라 프로그램의 로직을 시행할 수 있다

조건문의 기본 형태

• if ~ elif ~ else
• elif나 else 부분은 경우에 따라 사용하지 않아도 된다.

Tip 5
파이썬의 기타 연산자

• 다수의 데이터를 담는 자료형을 위해 in 연산자와 not in 연산자가 제공된다
• 리스트 튜플, 문자열, 딕셔너리 모두에서 사용이 가능하다
• x in a
• x not in a

Tip 6
파이썬의 pass 키워드

• 아무것도 처리하고 싶지 않을 때 pass 키워드를 사용

조건문의 간소화

• 조건문에서 실행코드가 한 줄일 경우, 굳이 줄바꿈을 하지 않아도 표현할 수 있다
• 조건부 표현식 : if~else문을 한 줄에 작성할 수 있다
  • print('Success') if score >= 80 else print('Fail')

파이썬 조건문 내에서는 부등식

• 다른 프로그래밍 언어와 다르게 조건문 안에서 수학의 부등식을 그대로 사용할 수 있다 0 < x < 20

 

📌 반복문

• 특정한 소스코드를 반복적으로 실행하고자 할 때 사용
• 파이썬에서는 while과 for문이 있는데 코테에서는 for을 더 많이 사용한다

while

while 조건 :
    실행할 소스코드

for

for 변수 in 리스트, 튜플..:
    실행할 소스코드

for문

• for문에서 연속적 값을 차례로 순회할 때는 range()를 주로 사용
• range(시간 값, 끝 값 + 1)
• 인자를 하나만 넣으면 자동으로 시작 값은 0
  for i in range(1,10)

continue

• 남은 코드 실행을 건너뛰고 다음 반복을 진행하고자 할 때 사용

break

• 반복문을 즉시 탈출하고자 할 때 break 사용
• 현재 진행되고 있는 반복문만 탈출

 

✍ 함수와 람다 표현식

 

📌 함수

• 특정한 작업을 하나의 단위로 묶어 놓은 것
• 불필요한 소스코드의 반복을 줄일 수 있다.

종류

• 내장함수 : 파이썬이 기본적으로 제공하는 함수
• 사용자 정의 함수: 개발자가 직접 정의하여 사용할 수 있는 함수

함수 정의하기

• 매개변수 : 함수 내부에서 사용할 변수
• 반환 값 : 함수에서 처리 된 결과를 반환 (return)
• def 함수명(매개변수): 실행할 소스코드 return 반환 값

용어

• argument(인자) : 함수를 호출할 때 넣는 값
• paramater(매개변수) : 함수 내부에서 전달받고자 하는 변수

파라미터 지정하기

• 파라미터의 변수를 직접 지정할 수도 있다. 이 때 매개변수의 숫자가 달라도 상관 없음
  add(b =3,a=7)

global 키워드

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

여러 개의 반환 값

def operator(a,b):
    return x,y,z

차례대로 특정 변수에 담는 것을 unpacking
반환된 순서에 맞데 특정 변수에 순서대로 담을 수 있다

 

📌 람다 표현식

• 함수를 간단하게 작성할 수 있다
• 함수를 한 줄에 작성할 수 있음
• 함수의 이름이 없다
  print((lambda a,b : a+b)(3,7))
• 함수 자체를 입력으로 받는 함수가 존재할 때 유용하게 쓸 수 있다
• 한번만 입력하고 끝날 때 유용하다

여러 개의 리스트에 적용

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

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

print(list(result))

동일한 규칙을 가지는 하나의 함수에 적용하고자 할 때 사용

 

 

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

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

 

✍ 내장 함수

• sum()
• min(), max()
• eval() : 수식으로 표현된 형태를 실제로 계산한다 eval("(7-2)*6")
• sorted()
• sorted() with key : 기본적으로 두번째 원소를 기준으로 해서 정렬해준다. 이 때 원소를 정하면서 lambda 함수를 자주 쓴다

 

✍ 순열과 조합

• 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나타내기 nPr
• 조합 : 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택 nCr

📌 순열

from itertools import permutations

permutations(arr,3)

중복 순열

from itertools import product
product(arr, repeat=2) # 2개를 뽑는 모든 순열 구하기 (중복 허용)

📌 조합

from itertools import combinations

combinations(arr,2)

중복 조합

from itertools import combinations_with_replacement
combinations_with_replacmment(data,2)

 

 

Counter

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

print(dict(counter)) # 사전 자료형으로 반환

#### 최대 공약수와 최소 공배수
- 최대 공약수는 math의 gcd()


import math  
math.gcd(a,b) # 최대 공약수 계산 (GCD)  
a\*b // math.gcd(a,b) # 최소 공배수 계산