1️⃣ 조건문
| if ~ elif ~ else 문
🐾 논리 연산자
• X and Y : X 와 Y 가 모두 참일때 참
• X or Y : X 와 Y 중 하나만 참이어도 참
• not X : X 가 거짓일 때 참이다.
🐾 기타 연산자
• 리스트, 튜플, 문자열, 사전과 같은 자료형에 값이 존재하는지 확인하는 연산 : in, not in
• X in 리스트 : 리스트 안에 X가 들어있을 때 참
• X not in 문자열 : 문자열 안에 X 가 들어가 있지 않을 때 참
• pass : 조건문의 값이 참이라고 해도 아무것도 처리하고 싶지 않을 때 사용
• 조건부 표현식 : if ~ else 문을 한줄에 작성
score = 85
result = "성공" if score>=80 else "실패"
print(result)
2️⃣ 반복문
| while, for 문 둘 다 사용할 수 있는데 for 문의 소스코드가 더 짧은 경우가 많아 코테에서 자주 쓰인다.
🐾 While 문
• 조건문이 참일 때 한해서 반복적으로 코드가 수행된다.
# 1부터 9까지 홀수만 더하기
i = 1
result = 0
while i <= 9 :
if i%2 == 1 :
result += i
i+=1
print(result)
🐾 for 문
• in 뒤에 오는 데이터에 포함되어 있는 모든 원소를 첫 번째 인덱스부터 차례대로 하나씩 방문한다.
result = 0
for i in range(1,10) :
result += i
print(result)
• continue : 반복문 안에서 continue 를 만나면 프로그램의 흐름은 반복문의 처음으로 돌아간다.
🗨 pass, continue, break 정리하고 가기
• pass : 실행할 코드가 없는 것으로 다음 행동을 계속해서 진행한다. 즉 사용자가 프로그램이 아무 작업도 하지 않기 원할 때 자리 표시자로 사용된다.
• continue : 바로 다음 순번의 loop 을 수행한다.
• break : 반복문을 멈추고 loop 밖으로 나가도록 한다.
3️⃣ 함수
| 동일한 알고리즘을 반복적으로 수행해야 할 때 함수는 중요하게 사용된다.
🐾 기본
• 매개변수 : 함수 내부에서 사용되는 변수의 값을 전달받기 위한 값
• return : 함수에서 어떤 값을 반환하고자 할 때 사용하는 값
• 함수에서 매개변수나 return 문은 존재하지 않을 수 있다.
def add(a,b) :
return a+b
print(add(3,6))
🐾 전역변수, 지역변수
• global : 함수 안에서 함수 밖의 변수 데이터를 변경해야 하는 경우 사용하는 키워드로, 해당 함수를 사용하면 지역 변수를 만들지 않고 함수 바깥에 선언된 변수를 바로 참조할 수 있게 된다.
🐾 lambda 표현식
• 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다.
• 파이썬 정렬 라이브러리를 사용할 때, 정렬 기준 Key 를 설정할 때에도 자주 사용된다.
4️⃣ 입출력
| 알고리즘의 첫 단계는 "데이터를 입력받는 것"
🐾 input 함수와 숫자형
• input 의 경우 한 줄의 문자열로 인식하여 입력받는 함수이다. 따라서 숫자형 데이터로 처리하려면 int 함수를 써야 한다.
• list(map(int, input().split())) ⭐⭐
• 각 변수에 입력하고자 한다면
🐾 readline 함수
• input 함수는 동작 속도가 느려서 sys 라이브러리 함수를 사용하기도 한다.
import sys
data = sys.stdin.readline().rstrip()
print(data)
🐾 출력
• print 문 : 콤마로 구분하여 변수 여러개를 출력할 수 있다.
• 파이썬 print 문에서 단순히 + 연산자를 활용해 문자열과 수를 더하면 오류가 발생한다는 점을 꼭 기억하자. 따라서 str 함수를 통해 숫자를 출력하거나 각 자료형을 콤마로 구분해서 출력해야 한다.
• f-string 문법
answer = 7
print(f"정답은 {answer} 입니다")
5️⃣ 표준 라이브러리
① 내장함수
• 별도의 import 명령어 없이 바로 사용할 수 있는 함수
• print() , input()
• sorted() : iterable 객체 (리스트, 사전 자료형, 튜플 자료형 등) 이 입력으로 주어졌을 때 정렬된 결과를 반환
🗨 sorted 는 key 속성을 통해 정렬 기준을 설정할 수 있다.
🗨 리스트와 같은 iterable 객체는 기본적으로 sort() 함수를 내장하고 있어 굳이 sorted 를 사용하지 않아도 정렬 가능하다.
• sum() : iterable 객체 (리스트, 사전 자료형, 튜플 자료형 등) 이 입력으로 주어졌을 때 모든 원소의 합을 반환
result = sum([1,2,3,4,5])
• min() : 가장 작은 값 반환
• max() : 가장 큰 값 반환
result = min(7,3,5,2)
• eval() : 수학 수식이 문자열 형식으로 들어오면 해당 수식을 계산한 결과를 반환
result = eval( "(3+5)*7" )
# 56
② itertools
• 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리로 순열과 조합 라이브러리를 제공한다.
• permutations : r 개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산, 리스트 자료형 변환이 필수
• combinations : r 개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우를 계산 , 리스트 자료형 변환이 필수
• product : r 개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산, "중복" 허용 , r 을 repeat 속성값으로 지정해주어야 한다.
• combinations _with_replacement : r 개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우를 계산 , "중복" 허용
③ heapq
• Heap 기능을 제공하는 라이브러리 이다. 우선순위 큐 기능을 구현하기 위해 사용한다.
• Heap : 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조로 여러 개의 값들 중에 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 파이썬 힙은 최소 힙으로 구성되어 있어 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN) 에 오름차순 정렬이 완료된다.
🗨 최대 힙 : 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진 트리
🗨 최소 힙 : 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리
• heapq.heappush() : 힙에 원소를 삽입하고자 하는 경우
• heapq.heapop() : 힙에서 원소를 꺼내고자 하는 경우
• 파이썬에서는 최대 힙을 제공하지 않으므로 원소의 부호를 임의로 변경하는 방식을 사용해야 한다.
④ bisect
• 이진탐색 기능을 제공하는 라이브러리 이다.
• "정렬된 배열" 에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.
• bisect_left 함수와 bisect_right 함수가 가장 중요하게 사용되며 이 두 함수는 시간 복잡도 O(logN) 에서 동작한다.
• bisect_left(a,x) : 정렬된 순서를 유지하며 리스트 a 에, 데이터 x 를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a,x) : 정렬된 순서를 유지하며 리스트 a에, 데이터 x 를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
🐾 정렬된 리스트에서 '값이 특정 범위에 속하는 원소의 개수' 를 구하고자 할 때, bisect 가 효과적으로 사용될 수 있다.
⑤ collections
• deque, counter 등의 유용한 자료구조를 포함하고 있는 라이브러리 이다.
🐾 deque
• 파이썬에서는 deque 를 활용해 큐를 구현한다.
• 리스트 자료형 VS deque
리스트 자료형은 데이터 삽입, 삭제 등 다양한 기능을 제공하고 중간에 특정한 원소를 삽입하는 것도 가능하지만, append 로 데이터를 추가하거나 pop 으로 데이터를 삭제할 때 항상 가장 뒤쪽 원소를 기준으로 적용된다. 따라서 앞쪽에 있는 원소를 처리하려면 리스트에 속한 데이터의 개수에 따라 많은 시간이 소요될 수 있다.
| 리스트 | deque | |
| 가장 앞쪽에 원소 추가 | O(N) | O(1) |
| 가장 뒤쪽에 원소 추가 | O(1) | O(1) |
| 가장 앞쪽에 있는 원소 제거 | O(N) | O(1) |
| 가장 뒤쪽에 있는 원소 제거 | O(1) | O(1) |
deque 는 인덱싱, 슬라이싱의 기능은 없으나, 데이터의 시작 부분이나 끝부분에 데이터를 삽입 혹은 삭제할 때 효과적으로 사용된다. deque 는 스택이나 큐의 기능을 모두 포함한다고 볼 수 있다.
• popleft() : 첫 번째 원소 제거
• appendleft() : 첫 번째 인덱스에 원소 삽입
• pop() : 마지막 원소 제거
• append() : 마지막 인덱스에 원소 삽입
• deque 를 큐 자료구조로 이용하고자 한다면, 삽입할 땐 append 를 삭제할 땐 popleft 를 사용하면 된다. 그럼 먼저 들어온 원소가 항상 먼저 나가게 된다.
🐾 Counter
• 등장 횟수를 세는 기능을 제공하는 함수 : 원소별 등장 횟수 세기
⑥ math
• 필수적인 수학기능을 제공하는 라이브러리
• 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련 함수, pi 와 같은 상수 등을 포함하고 있다.
6️⃣ 자료구조
🚩 자료구조를 배우는 이유
• 데이터를 체계적으로 저장하고 효율적으로 활용하기 위해서 사용한다.
• 특정 상황에 놓인 문제를 해결하는데 특화되어 있다 → 문제 해결 능력을 필요로 하는 알고리즘과 밀접한 연관성
🚩 자료구조
• 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의
• 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법
🐾 선형구조
- 배열
- 연결 리스트
- 스택
- 큐
🐾 비선형구조
- 트리
- 그래프
🐾 시간 복잡도
| 빅오표기법 | 명칭 |
| O(1) | 상수시간 |
| O(logN) | 로그시간 |
| O(N) | 선형시간 |
| O(NlogN) | 로그선형시간 |
| O(N^2) | 이차시간 |
| O(N^3) | 삼차시간 |
| O(2^n) | 지수시간 |
• 위쪽에 있을수록 더 빠르다.
'2️⃣ Study > ⚙ 알고리즘' 카테고리의 다른 글
| [자료구조] 정렬 (1) | 2024.02.25 |
|---|---|
| [자료구조] DFS/BFS (0) | 2022.09.02 |
| [자료구조] 구현 (1) | 2022.09.02 |
| [자료구조] 그리디 (0) | 2022.09.02 |
| [자료구조] 필수 파이썬 문법 - 자료형 (0) | 2022.09.01 |
댓글