자료구조와 알고리즘

자료구조와 알고리즘 이란?

초보자들은 데이터 구조와 알고리즘이 필요하진 않다... 아직 실행되게 하는게 더 중요한 단계

버그는 없으나 어플리케이션이 느릴때 → 최적화를 위해 데이터 구조와 알고리즘을 배울때

구현 가능/불가능 → 클린코드(관리 좋고 협업 좋음) → 더 효율적이고 빠른 코드 (자료구조와 알고리즘을 통해)

알고리즘

목적을 달성하기 위한 여러개의 행동들. 이를 통해 동일한 결과를 야기한다.

어떠한 액션을 수행하기 위해 컴퓨터가 수행해야하는 것들

훌륭하고 효율적인 알고리즘을 찾으면, 반복적으로 사용 가능하다

우리 생활에도 알고리즘이 있다. ex) 아침에 나갈 준비하기 (일어나서 씻고 옷입고 나가기)

ex) Path Finder 알고리즘(집에서 목적지를 가기위한 최단 거리 찾기), 압축 알고리즘(이미지의 퀄리티 손실 없이 어떻게 ?), 암호화

제한된 공간과 시간에서 데이터를 어떻게 처리할지 정해놓은 로직

즉, 주어진 Input → function → output 과정

문제 해결을 위한 나의 방법/생각

Key point

input에 size가 커질수록 bigO가 어떻게 변화하는지

공간/시간 복잡도는 어떤지

어떤 자료구조를 통해 알고리즘을 쓰는게 좋은지

⇒ 작은 공간과 빠른시간 내에 효율적으로 처리할 수있는 알고리즘이 좋다.

데이터 구조 (자료구조)

데이터를 정리하는 것

어떻게 정리하느냐에 따라 스피트에 영향을 끼치기 때문

어떤 데이터 구조는 정렬에 최적화 되어있다. 어떤 구조는 검색에 최적화, 또 다른 구조는 추가/편집에 최적화 되어있다.

어떠한 작업에 어떠한 데이터 구조를 언제 어떻게 쓰는지가 어플리케이션의 스피드를 결정한다.

서비스나 어플리케이션에서 필요한 데이터를 메모리에 어떻게 구조적으로 잘 담아두고 관리하고 효율적인 방식으로 필요한 데이터에 빠르게 접근/수정/삽입을 도와줌

Key Point

자료구조 안의 순서가 보장이 되는지

중복된 데이터가 들어갈 수 있는지

검색시 얼마나 효율적인지

우리가 원하는 기능에 따라 수정할때 얼마나 효율적인지

Programming

언어를 쓰는 모든 개발자들이 기본적으로 알아야한다.

다양한 결과를 얻기위해 여러가지 명령어를 모아 놓은 언어/컴퓨터 프로그램에서 알고리즘을 구현하기 위해 사용 (HTMLl, CSS는 각각 Mark up 언어, style sheet 언어이기에 프로그래밍 언어는 아니다)

자료구조와 알고리즘을 알면 효율적으로 원하는 기능을 만들 수 있다.

문제 먼저 푼다면 개념없이 수학문제를 푸는 것과 같다.

실무에선 프레임워크를 써서... 면접에서 시간/공간 복잡도와 알고리즘 이해 답변을 목적으롷나다.

⇒ 자료구조와 알고리즘의 전반적인 이해 필요

공부순서

기본문법

알고리즘 100제 ex)z코드업 기초 100제

백준/코드포스/탑코더 등에서 그리디 알고리즘 부터

DFS/BFS 탐색, 기본 동적 프로그래밍

그래프이론, 중급/고급 동적 프로그래밍 문자열 등... (연구적이나 대학원 진학을 위해 필요)

💡

대기업 공채를 위해선 → 코드포 블루, 삼성 SW 역량 test B형 정도 수준

Array 자료구조

시간 복잡도

데이터 구조의 오퍼레이션/알고리즘이 얼마나 빠르고 느린지 측정하는 방법

실제 시간을 초/분단위로 측정하는 것이 아니라 얼마나 더 많은 단계로 있는가로 측정

단계가 적을수록 더 좋은것

Read, Search, Add, Delete에 대한 시간복잡도를 알아보자

휘발성/비휘발성 메모리

휘발성 메모리 : 껐다다가 키면 데이터가 나라감... (RAM), 속도가 빠름(랜덤하게 접속이 가능하니깐...)

프로그램의 변수들은 전부 RAM에 저장된다.

Array는 메모리에서 처음에 얼마나 긴지를 설명하여 할당받는다. (JS/Python은 자동으로 해준다..)

1. Reading - 배열을 어떻게 읽는가

컴퓨터는 배열이 어디서 시작되는지 아니깐, 인덱스를 통해 배열에서 읽어내는것은 빠르다. (Random access가가능하기에 배열이 아무리 길어도 괜찮다.)

배열에 요소가 5개있든 100개있든 속도는 같다

2. Searching

이건 좀 시간이 걸린다...

해당 값이 어디있는지, 존재하는지도 모른다. → 전부 탐색해야한다.

원하는 아이템이 처음에 있는지, 중간에 있는지, 마지막에 있는지, 없는지에 따라 속도가 차이난다.

처음부터 차근차근 찾기 방법 (Linear Search)

3. Insert

배열을 만들 때에는 메모리 공간을 미리 확인한다.

공간에 여유가 있고 맨 마지막에 추가한다면, 그냥 배열 마지막으로 가서 토마토를 넣으면 된다 → 빠름

공간에 여유가 있고 배열 중간에 추가하는 경우, 뒤에 있는 애들을 하나씩 미루고 토마토 넣기 → 보통..

공간에 여유가 있고 토마토를 맨 앞에 넣는 경우, 배열이 클수록 좋지 않다...

이미 공간이 꽉찼는데 추가해야하는 경우 → 더 큰 배열을 만들어서 이전 배열을 복사하고 추가한다. → 매우 오래 걸림

4. Delete

insert랑 비슷하다.

맨 뒤일경우 지우고 끝

중간의 요소를 삭제할 경우 → 지우고 배열 뒤에있는 나머지를 하나씩 앞으로 당긴다

첫번쨰 요소를 삭제할 경우 → 최악의 경우... 모든 값을 한칸씩 옯겨야한다.

⇒ 배열은 데이터를 읽을때 매우 빠르다 Random access 때문, 반면 2~4는 느리다.. 이러한 경우 맨 끝에서 작업하는게 좋다.

Search Algorithom

검색 관련에 대한 작업을 빠르게

Linear Search (선형검색 알고리즘)

처음부터 하나씩 비교하면서, 원하는 값이 맞는지 확인

검색을 위한 가장 자연스터운 방법

최악의 경우 우리가 찾는 아이템이 배열 맨 마지막에 있거나, 배열에 없는 경우 → 배열이 커지면 커질수록 선형검색 하는 시간이 길어진다 = Linear time complexity

선형 검색은 어느 배열에서도 사용 가능

검색시 상대적으로 느리다.

Binary Linear (이진검색 알고리즘)

검색시 중간에서 시작한다. 정 중간의 값이 타겟보다 큰지 작은지 확인한 후 해당 방향으로 이동한다. x 반복

Linear Search의 Linear time complexity한계를 극복하기 위한 방법

모든 배열에 쓸 수는 없다... Sorted Array (정렬된 배열)에서만 사용 가능하다. (어떤 알고리즘은 특정 자료구조에서만 사용 가능하다)

(단)정렬된 배열에서 insert는 정렬안된 경우보다 느리다. (장)그러나 검색은 매우 빠르다

Sorted Array에서 insert를 위해서는 1. 위치찾기, 2. 뒤로 미루기, 3 insert 하기

여기서 binary의 의미는 두개로 쪼갠다는 의미다.

input 리스트의 길이가 2배가 되더라도, 필요한 스텝은 1step이 추가될 뿐이다. → 큰사이즈 데이터 처리에 용이하다.

Big O

알고리즘의 속도 표현법

알고리즘의 속도는 초로 표현하지 않는다.

컴퓨터 하드웨어 차이 때문에

완료까지 걸리는 절차의 수로 표현한다.

시간 복잡도를 빠르게 설명할 수 있다. 읽기 쉽고 바로 설명이 가능하다

어떻게 작동할지 알 수 있으니, 언제 무엇을 쓸지 빠르게 파악 가능

코드 평가에 사용 가능

알고리즘의 시간복잡도를 인풋과 연관하여 빠르게 알아낼 수 있다

선형검색 - O(N)

하나씩 검색한다

데이터가 n개이면 아이템을 찾기까지 n대 필요

O(N)으로 표현한다.


def print_first(arr):
	for n in arr:
		print(n)
	for n in arr:
		print(n)

O(N) = O(2N)

전달하고자 하는 것은 동일하다. 인풋이 증가하면, 스텝도 증가한다는 사실

상수시간 - O(1)

N이 얼마나 크든 상관 없이 끝내는데 동일한 시간이 소요됨

두번 해도 O(1)으로 표현 = 인풋 숫자와 상관없이미리 정해진 숫자만큼 진행


def print_first(arr):
	print(arr[0])
	print(arr[0])

2차시간(Quadratic Time) - O(n^2)

Nested loop(중첩 반복)이 있을때 발생

시간복잡도는 인풋의 n^2

르푸 안에서 르푸 실행


def print_first(arr):
	for n in arr:
		for x in arr:
			print(x, n)

로그시간 (Logarithmic Time) - O(log n)

이진검색 알고리즘 설명할때 사용

https://www.notion.so/e51ad68b47cb4e9fb9b36e47842b1295#333286e26459452cb6dd97961534e95e

인풋 사이즈가 더블 됬을때 스텝은 딱 한개 증가

밑을 쓰진 않는다. (=크게 의미 없다)

정렬된 배열에만 사용 가능하다... (장단점이 있다)

Hash Table

해시테이블이 무엇이고, 어떻게 작동하는지

해시테이블은 key : Value System으로 자료를 정리한다

사전과 유사 (단어는 Key, 내용은 value)

언어마다 같은 함수가 다양하게 존재한다 ex) JS Object, 파이썬의 딕셔너리, Go 에서 Map

Hash Table VS Array

어떤 메뉴의 가격을 찾아도 한 스텝이면 찾을 수 있다.

Hash Table VS Array

Array에서 피자 가격을 찾으려면 처음부터 하나씩 비교해보고 찾는다 → 느리다.

아이템이 많을수록 가격 찾는 시간이 증가한다.

작동하는 원리 및 컴퓨터 레벨에서 어떻게 움직이는지

Hash Table은 내부엔 Array 형태로 저장되어있다. 근데 왜 빠를까? ⇒ 해쉬 함수 덕분에

해쉬 함수의 결과를 가진 index에 저장하였기에, 빠르게 value를 확인할 수 있다.

Collision (해시 충돌)

각기 다른 Key에 대해 해시함수가 동일한 값을 두는 경우

가장 쉬운 해결법 = 해당 인덱스에 배열을 넣어 추가 저장

→ 해시테이블이 항상 0(1)은아니다. 충돌이 있는경우 0(n)이 된다.

그래도 평규적으론 0(1)이니... 시간복잡도를 보통 0(1)이라 사용한다.

알고리즘 - 그리디 & 구현

그리디 알고리즘(탐욕법)

지금 상황에서 당장 좋은 것만 고르는 방법

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해버법은 그 정당성 분석이 중요하다.

단순히 가장 좋아 보이는 것을 반복적으로 해도 문제에서 요구하는 최적의 값을 구할 수 있는지 확인해야한다.

구현 : 시뮬레이션과 완전 탐색

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

Problem → Thinking → Solution

흔히 알고리즘 대회에서 구현 유형의 문제란?

풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제

예시

알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 (언어마다 다르다...)
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 (문법적으로 언어별 구현 법을 알고 있어야한다.)
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 (파이썬이 다른 언어에 비해 처리하기 쉽다.)
적절한 라이브러리를 찾아서 사용해야하는 문제

대부분 코딩 테스트에서는 2차원 행렬 공간을 다룰 줄 알아야한다.

행렬 (= 2차원 배열, 2차원 list)

시뮬레이션 및 완전탐색 문제에서는 2차원 공간에서의 방향 백터 활용이 자주 사용된다.


# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x , y = 2, 2

for i in range(4):
	# 다음 위치
	nx = x + dx[i]
	ny = x + dy[i]
	pring(nx, ny)

DFS & BFS (그래프 탐색 알고리즘)

탐색이란 많은 양의 데이터에서 원하는 데이터를 찾는 과정

대표적인 그래프 탐색 알고리즘은 DFS, BFS (코딩테스트에서 자주 등장)

필수적으로 알아야할 자료구조

Stack 자료구조

선입후출

DFS 뿐만 아니라 다양한 알고리즘에서 사용된다.

파이썬에서 append / pop을 통해 구현

주로 stack은 list, Queue는 deque 활용

Queue를 deque 사용하는게 시간적으로 좋다. (deque 사용시 O(1) 시간 활용)
pop 시, 원소의 위치를 조정하는 과정이 필요하여 O(k) 시간 필요

Queue 자료구조

선입 선출

대기열, 차래대로 처리하는 방식을 표현

파이썬에서 보통 deque 라이브러리를 활용한다.


from collections import deque

# 뷰 구현을 위해 deque 라이브러리 사용
queue = deque()

queue.append(5) #append는 list와 동일한 역할
queue.popleft() #가장 왼쪽 데이터 빼기

queue.reverse() #역순으로 바꾸기

재귀함수

자기 자신을 다시 호출하는 함수

DFS를 실질적으로 구현할 때 자주 사용된다.

파이썬 코딩 도장

함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 합니다. 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다(구현은 만들다와 같은 뜻입니다). 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다. 이번에는 재귀호출을 사용하는 방법과 주의점을 알아보겠습니다. 참고로 재귀호출은 코드가 간단한 편이지만 머릿속으로 생각을 많이 해야 됩니다.

https://dojang.io/mod/page/view.php?id=2352

재귀함수의 종료조건

재귀함수를 문제풀이에서 사용할 때는 재귀함수의 종료조건을 반드시 명시해야한다.

함수의 무한 호출이나 오류 방지

재귀 함수 사용 시, 유의사항

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.

단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.

모든 재귀 함수는 반복뭉을 이요하여 동일한 기능을 구현할 수 있다.(재귀 함수가 반복문보다 유리한 경우도 있고, 불리한 경우도 있다.)

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임이 쌓인다. 그래서 스택을 사용해야 할 때 특성상 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다.

DFS (깊이 우선 탐색)

그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다

스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 없으면 스택에서 최상단 노드를 꺼낸다

더 이상 2번의 과정을 수행할 수 없을때까지 반복한다.


def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
	visited[v] = True
	print(v, end = ' ')
	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
	for i in graph[v]
		if not visited[i]
			dfs(graph, i, visited)

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

#각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False]* 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

BFS (너비 우선 탐색 )

그래프에부터 가까운 노드부터 우선적으로 탐색하는 알고리즘

큐 자료구조를 이용

특히 특정 조건에서의 최단 경로 탐색에 효과적으로 사용 할 수 있다.

탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드르 모두 큐에 삽입하고 방문 처리

더 이상 2번의 과정을 수행할 수 없을 때까지 반복


from collections import deque

def bfs(graph,start, visited):
	# 큐 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	# 현재 노드를 방문처리
	visited[start] = True
	# 큐가 빌때까지 반복
	while queue:
		# 큐에서 하나의 원소를 뽑아 출력
		v = queue.popleft()
		print(v, end='')
		# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

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

#각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False]* 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)