대부분 밑의 출처를 보며 작성한 글입니다 :)
계속해서 업데이트 될 예정입니다 :)
출처 - 코딩테스트 [All In One] 강의 (개발남노씨)
기초문법
변수 및 자료형
변수 할당 : variable_name = value
자료형 : int, float, str, list, tuple, dict, set(집합)
조건문
if 조건:
코드블록
elif 조건:
코드블록
else:
코드블록반복문
for 요소 in iterable:
코드블록while 조건:
코드블록함수 정의
def 함수이름(매개변수):
코드블록
[return 반환값]
# []는 생략가능리스트 조작
리스트 생성: list_name = [요소1, 요소2, ...]
요소 추가 : list_name.append(요소)
요소 삭제: del list_name[index] or list_name.remove(값)
문자열 다루기
문자열 합치기: + 연산자 또는 join() 메서드 사용
문자열 분리: split() 메서드 사용
딕셔너리 활용
딕셔너리 생성 : dict_name = {key1: value1, key2: value2, ...}
값 접근 : dict_name[key]
정규 표현식
re 모듈 사용
ex) re.match(), re.search(), re.findall() 등..
예외 처리
try:
코드 블록
except 예외:
예외 처리 코드 블록모듈과 패키지 사용
모듈 임포트 : import module_name
패키지 임포트 : from package_name import module_name
리스트 컴프리헨션
new_list = [표현식 for 요소 in interable if 조건]람다
lamba 매개변수: 표현식
클래스와 객체 지향 프로그래밍
클래스 정의 : class ClassName:
객체 생성: object_name = ClassName()
메서드 정의: def method_name(self, parameters):
내장 함수
len(), max(), min(), sum(), sort() 등
유용하게 쓰이는 함수
enumerate()
이 함수는 파이썬에서 주어진 iterable(반복 가능한 객체)의 각 요소에 대해 인덱스와 값을 순회하는데 사용됩니다.
이 함수는 enumerate 객체를 반환하며, 각 요소는 (인덱스, 값) 튜플로 구성됩니다.
유용한 자료구조 모음
List
set()은 순서가 중요하지 않지만, List[]는 순서가 중요하다.
Array List
파이썬에서는 이미 List로 구현이되어, List[]를 사용하면 된다.
Linked List
선형 자료구조 + 중간에 데이터 추가/삭제 용이
Tree or Graph에 활용
Queue (Deque)
Queue는 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다.
Queue의 rear에 데이터를 추가하는 것은 enqueue, front에서 데이터를 꺼내는 것을 dequeue라고 합니다.
deque
파이썬에서는 이미 Queue를 잘 구현한 자료구조가 있습니다.
deque이라는 자료구조고,
doubly ended queue라는 뜻입니다.
추가 제거를 할 수 있습니다.
밑의 코드 형태로 사용할 수 있습니다.
from collections import deque
queue = deque()
# enqueue() 0(1)
queue.append(1)
queue.append(2)
# dequeue() 0(1)
queue.popleft()
queue.popleft()
Stack
시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장하는 자료구조입니다.
stack의 top에 데이터를 추가하는 것을 push라고 하고, 추출하는 것은 pop이라고 합니다.
밑의 코드 형태로 사용할 수 있습니다.
# stack 선언
# push 0(1)
stack.append(1)
stack.append(2)
# pop 0(1)
stack.pop()
stack.pop()
Stack의 다양한 활용
1. LIFO 특성을 활용한 문제
2. DFS(깊이 우선 탐색)에 사용
Stack의 주요 문제(유형적 접근)
Valid Parentheses(괄호 유효성 문제)
Hash Table
HashTable은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다.
hash function h에 key 값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다.
저장, 삭제, 검색의 시간복잡도는 모두 O(1)입니다.
Hash Table에는 index의 Collision(충돌)이 발생할 수 있는데,
이를 해결하는 방법으로 addressing, separate chaining 방법이 있습니다.
이러한 HashTable은 Dictionary라는 자료구조로 구현이 되어있습니다.
Dictionary
// Dictionary 기본 사용
score = {
'math' : 97,
'eng' : 49,
'kor' : 89
}
score['math']
score['math'] = 40
score['sci'] = 100
'music' in score # 키가 있는지 확인하는 방법
value가 필요없을때는 HashSet을 사용하는게 좋다!
Direct-address Table
키 값이 index가 되는 테이블 (해시 테이블과 반대)
이렇게 할때, 키 값이 클경우 메모리의 낭비를 초래할 수 있다.
Recursion
재귀함수(Recursive function)란 자신을 정의할 때 자기 자신을 재참조하는 함수를 뜻합니다.
def factorial(n):
if n == 1 :
return 1 # Base Case
return n * factorial(n - 1)
def fibo(n):
if n == 1 or 2:
return 1 # Base Case
return fibo(n-1) + fibo(n-2)
재귀함수에는 구성요소가 2가지 있는데,
Recurrence Relation(점화식)과 Base Case를 가진다.
Base Case가 존재하지 않으면, 계속 함수를 호출하면서 무한루프에 빠질 수 있기에, 항상 생각하며 프로그래밍 해야한다.
재귀함수의 시간복잡도
재귀함수 전체 시간 복잡도 = 재귀 함수 호출 수 x (재귀 함수 하나당) 시간복잡도
Execution Tree(Recursion Tree) : 재귀 함수의 실행 흐름을 나타내는 데 사용되는 트리
Tree
Tree는 서로 연결된 Node의 계층적 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어 있습니다.
Tree 관련 개념
노드(Node) - 트리는 보통 노드로 구현됩니다.
간선(Edge) - 노드간에 연결된 선
루트 노드(Root) - 트리는 항상 루트에서 시작합니다.
리프 노드(Leaf) - 더이상 뻗어나갈 수 없는 마지막 노드
자식 노드(Child), 부모노드 (Parent), 형제노드(Sibling)
차수(degree) - 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 합니다.
조상(ancestor) - 위쪽으로 간선을 따라가면 만나는 모든 노드
자손(descendant) - 아래쪽으로 간선을 따라가면 만나는 모든 노드
높이(height) - 루트노드에서 가장 멀리있는 리프 노드 까지의 거리. 즉, 리프 노드 중에 최대 레벨 값.
서브트리(subtree) - 트리의 어떤 노드를 루프로 하고, 그 자손으로 구성된 트리를 subtree라고 합니다.
이진트리 구현 코드
class Node:
def __init__(self, value = 0, left = None, right = None):
self.value = value
self.left_child = left
self.right_child = right
class BinaryTree:
def __init__(self):
self.root = None
bt = BinaryTree()
bt.root = Node(value = 1)
bt.root.left = Node(value = 2)
bt.root.right = Node(value = 3)
bt.root.left.left = Node(value = 4)
bt.root.left.right = Node(value = 5)
bt.root.right.right = Node(value = 6)트리 순회(Tree Traversal)
트리 순회(Traversal)란 트리 탐색(search)이라고도 불리우며 트리의 각 노드를 방문하는 과정을 말합니다.
모든 노드를 한번씩 방문해야 하므로, 완전탐색이라고도 불립니다.
순회 방법으로는 너비 우선 탐색의 BFS와 깊이 우선 탐색의 DFS가 있습니다.
너비 우선 탐색(Breadth-first search BFS)
Level order (큐 필요)
def bfs(root):
visited = []
if root is None:
return 0;
q = deque()
q.append(root)
while q:
cur_node = q.popleft()
visited.append(cur_node.value)
if cur_node.left:
q.append(cur_node.left)
if cur_node.right:
q.append(cur_node.right)
return visited
bfs(root)
DFS(깊이 우선 탐색) by recursion
def dfs(root):
if root is None:
return
dfs(root.left)
dfs(Root.right)
dfs(root)전위순회(preorder)
def preorder(cur_node):
if cur_node is None:
return
print(cur_node.value)
preorder(cur_node.left)
preorder(cur_node.right)
preorder(root)중위순회(inorder)
def inorder(cur_node):
if cur_node is None:
return
inorder(cur_node.left)
print(cur_node.value)
inorder(cur_node.right)
inorder(root)후위순회(postorder)
def postorder(cur_node):
if cur_node is None:
return
postorder(cur_node.left)
postorder(cur_node.right)
print(cur_node.value)
postorder(root)
코테 적용 방법
Tree 활용 -> 자주 나오는 유형
1. Tree 구현
2. Tree 순회
a. level order
b. post order
Graph
그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조입니다.
그래프 종류
1. 방향 그래프(단방향 그래프) vs 무향 그래프(양방향 그래프)(코테 빈출도 높음)
2. 다중 그래프(연결되는 선이 여러개) vs 단순 그래프(단 하나의 선으로만 연결)
3. 가중치 그래프(각각의 선에 가중치를 정할 수 있다) => 다익스트라
그래프 활용
현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현합니다.
그래프는 현실의 문제를 해결하기 위한 도구로써 유용하게 이용됩니다. -> 문제 다수 출제
- 도시들을 연결하는 도로망 : 도시(vertex), 도로망(edge)
- 지하철 연결 노선도: 정거장(vertex), 정거장을 연결한 선(edge)
- 컴퓨터 네트워크: 각 컴퓨터와 라우터(vertex), 라우터간의 연결 관계(edge)
- 소셜 네트워크 분석: 페이스북의 계정(vertex), follow 관계(edge)
Graph 표현방법
인접 리스트(adjacency list)
graph = {
1: [3, 5],
2: [4, 5],
3: [1, 5],
4: [2, 5],
5: [1, 2, 3, 4]
}인접 행렬(adjacency matrix)
graph = [
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 1],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 1],
[1, 1, 1, 1, 0],
]왼쪽상단에서 오른쪽하단의 대각선으로 대칭되는 구조이다.
메모리 낭비가 심한 단점이 있다.
암시적 그래프(implicit graph)
graph = [
[1, 1, 1, 1, 1],
[0, 0, 0, 1, 1],
[1, 1, 0, 1, 1],
[1, 0, 0, 0, 0],
[1, 1, 1, 1, 1]
]
미로찾기와 같은 문제를 풀때 많이 쓴다.(대부분 이 그래프를 사용)
그래프 순회(Graph Traversal)
그래프 순회란 그래프 탐색(search)라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말합니다.
그래프 순회에는 크게 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)의 2가지 알고리즘이 있습니다.
너비 우선 탐색(Breadth-first search, BFS)
from collections import deque
def bfs(graph, start_v):
visited = [start_v]
queue = deque(start_v)
while queue:
cur_v = queue.popleft()
for v in graph[cur_v]:
if v not in visited:
visited.append(v)
queue.append(v)
return visited
bfs(graph, 'A')깊이 우선 탐색(Depth-first search DFS)
graph = { ... }
def dfs(graph, cur_v, visited = []):
visited.append(cur_v)
for v in graph(cur_v):
if v not in visited:
visited = dfs(graph, v, visited)
return visited
dfs(graph, 'A')
간단한 버전
graph = { ... }
visited = []
def dfs(cur_v):
visited.append(cur_v)
for v in graph[cur_v]:
if v not in visited:
dfs(v)
dfs('A')
Dynamic Programming(DP)
문제에 대한 정답이 될 가능성이 있는 모든 해결책을 체계적이고 효율적으로 탐색하는 풀이법
1. 크고 복잡한 문제를 작은 문제들로 나눈다. (subproblem - 하위문제)
2. 하위 문제의 답을 계산한다.
- 중복 계산해야 하는 하위 문제가 있다. (overlapping subproblem - 중복 하위 문제)
- 한번 계산한 결과는 메모리에 저장하여 재계산 하지 않도록 한다. -> 속도 향상(memoization, dp table)
3. 하위 문제에 대한 답을 통해 원래 문제에 대한 답을 계산한다. (optimal substructure - 최적 부분 구조)
- 최적 부분 구조 - 하위 부분 문제에서 구한 최적의 답이 합쳐진 큰 문제의 최적의 답을 구할 수 있는 구조.
Top-down VS Bottom-up
코딩테스트 접근방법
<1.문제이해>
* input, output 확인
** input 값의 특징 (정수인가? 값 크기의 범위는? 마이너스도 되는건가? 소수인가? 자료형은 문자열인가? 등등)
** output 값의 특징 (내가 어떤 값을 반환해줘야 하는지, 정해진 형식대로 반환하려면 어떻게 구현할지)
* input size N 확인
** 시간복잡도를 계산하기 위한 input size N 또는 M이 무엇인지 확인
* 제약조건 확인
** 시간복잡도 제한이 있는지 확인
** 내가 선택할 수 있는 알고리즘이 무엇이 있는지
* 예상할 수 있는 오류 파악
** 상황을 가정하면서 예상할 수 있는 오류를 파악한다.
** 입력값의 범위, stack overflow 등
<2. 접근방법>
직관적으로 생각하기
* 보통 완전탐색으로 시작
* 문제 상황 단순화 및 극한화
자료구조와 알고리즘 활용
* 문제이해 에서 파악한 내용을 토대로 어떤 자료구조를 사용하는게 가장 적합한지 결정
* 대놓고 특정 자료구조와 알고리즘을 묻는 문제도 다수
* 자료구조에 따라 선택할 수 있는 알고리즘 문제에 적용
메모리 사용
* 시간복잡도를 줄이기 위해 메모리를 사용하는 방법
* 대표적으로 해시테이블
출처 - 코딩테스트 [All In One] 강의 (개발남노씨)
'Coding Test' 카테고리의 다른 글
| 탐색 알고리즘 | 순차 탐색(Sequential Search) (0) | 2024.10.16 |
|---|---|
| CT | 백준 - 11286번 절대값 힙 (0) | 2024.08.27 |
| CT | Java에서 효율적으로 ArrayList에서 최대값을 찾고 제거하기(백준 - 11279) (0) | 2024.08.27 |
| CT | 완전 탐색(Brute Force) (0) | 2024.03.04 |
| CT | 문자열을 Integer로 형변환 시 NumberFormatException 방지하여 문제풀기 - (프로그래머스)크기가 작은 부분문자열 (1) | 2024.02.28 |