Upstage AI Lab 2기
2024년 2월 6일 (화) Day_040
Day_040 실시간 강의 : 자료구조 및 알고리즘 (1)
(노정호 강사님
https://www.youtube.com/@nossi-dev)
1일차 수업 요약 키워드
메모리 구조 - LIST : Array, LinkedList
시간복잡도
완전 탐색 - 조합 / 순열 / 부분집합 - 재귀함수
3일 강의의 목표
① 코딩테스트 합격
② 자료구조 & 알고리즘을 알아두면 구현에 도움이 됨
우선순위
1. 완전탐색, 그래프 + BFS + DFS (절반 이상의 비중을 차지)
+ α : 문자열, backtracking, dynamic programming, hashtable
코딩테스트 팁
https://www.nossi.dev/cote/tip
기본적인 문제는 풀 수 있는 것을 목표로!
but 각자의 원칙과 목표에 맞춰서 우선순위 조절
문제해결능력
구현능력
언어는 python 추천
면접과 코딩테스트는 다른 전략이 필요
이론 + 문제풀이 병행
주력언어를 정하고 체화
스터디를 꼭 하자!
'할 때 제대로 하자' <- 강사님의 강조
자료구조(Data Structure)
: 데이터를 저장하고 관리하는 방식
자료구조를 배워야 하는 이유 : 자료구조와 알고리즘은 긴밀한 관계가 있다.
알고리즘(Algorithm)
: 문제해결 방법
자주 쓰이는 문제는 해결방법이 패턴화(≒ 일반화)되어 있다.
일반화 -> 주어진 문제에 맞게 변형하고 응용해야 함
어느 정도 이해를 기반으로 암기가 필요
BFS, DFS, Binary Search, Dijkstra는 능수능란하게 쓸 수 있어야 함.
알고리즘 평가 기준
- 시간복잡도
- 공간복잡도
https://www.nossi.dev/cote/timecomplexity
https://www.youtube.com/watch?v=GHClo7yu_20&t=13s
메모리 구조
- 시간복잡도와 관련
어디에 저장하는가
HDD(하드디스크) / RAM
파일 자체는 하드디스크에 저장
실행할 때는 RAM 메모리에 잠시 올려놓는다.
∴ 동시에 많이 실행 -> RAM 많이 필요
즉, 우리에게는 RAM이 중요
LIST
순차적 자료구조 (ADT, Abstract Data Type, 추상자료형)
- Array : 메모리 상 인접 (continuous) (e.g. python list)
- LinkedList : 메모리 상 인접 X (discontinuous), link(pointer)가 꼭 필요
∴ 메모리구조상 어떻게 저장되는지 알아야 함
자료구조 -> 구현방식은 다양
list / heap / queue / stack -> array, linkedlist 등 구현방식 다양
이 자료구조가 무엇을 하고 싶은지 생각하기!
메모리구조 특성
- Array
: 맨 첫번째 자료의 주소가 저장되어 있고, 간격이 일정함(예: 4byte 또는 8byte)
산술연산 한번으로 접근 가능 - 즉시 실행
시간복잡도 O(1)
- LinkedList
: node를 다 타고 들어가야 함. (예. 100번째 자료 접근 -> 100번 실행)
n ↑ 시간 ↑
시간복잡도 O(n)
대신 node 삭제할 때 빠름
즉, 같은 list 도 array로 구현 하면 O(1), linkedlist로 구현하면 O(n)
각자 더 적합한 상황이 있음
bit 의 어원 binary digit
binary 0b
↓ 4bit = 1자리
hexadecimal 0x
RAM 설명
메모리 할당
C언어는 어떻게 구성되어 있는가
integer -> 4 byte(32bit)로 표현
1bit : 부호
31bit : 숫자 표현
-2^31 ~ 2^31
LinkedList (discontinuous)
value+ address(of next node)
(4byte or 8byte) + (4byte or 8byte) -> 8byte each
4byte or 8byte -> 시스템/컴퓨터마다 다를 수 있음
파이썬의 경우 dynamic array -> element의 자료형이 다 달라도 알아서 처리해줌
Running Time 실행 시간에 대한 이해가 중요함
-> 확장성을 고려
실행할 때마다 개별 running time은 다름 (캐시메모리 상황, cpu 성등 등등)
-> 매번 실행 시간을 계산할 수는 없음
-> 경향성으로 판별
--> Big O
Big O
10^8 -> 1초~10초 정도
넘지 말아야 할 선을 판별할 수있음
대세에 지장을 주는 부분 -> 반복문
input(n) -> n이 미지수이니까 n을 기준으로 생각할 수 있어야 함
예) 5n^2 + 3n +30
최고차항 외에는 의미 없어짐
Big-O notation
n! >> n^5 > n^4 > n^3 > n^2 > nlogn > n > logn
예)
5n^2 + 3n + 30 -> O(n^2)
5n + 30 -> O(n)
5030 -> O(1)
best case / average case / worst case
같은 알고리즘, 같은 환경, 같은 사이즈의 input 이어도 input 형태에 실행시간이 달라질 수 있음
예를 들어 insertion sort의 경우 worst case 는 O(n^2), best case 는 O(n)
average case 자체는 계산하기 어렵지만
average case ∽ worst case (-> upper bound)
보수적으로 마지노선인 worst case를 기준으로 정함
예)
문제에는 input들의 범위를 정해줌
nums.length <= 10^5 : O(n^2)인 알고리즘을 사용하면 안된다는 의도
-10^9 <= nums[i] <= 10^9 : int 자료형 써도 된다는 의도 (c, java 등 type이 strict한 언어들)
note. 우리는 우선순위를 정해서 공부할 것임
1.0 알고리즘 패러다임 (Algorithm paradigm)
① 완전 탐색 - BFS, DFS, 재귀, 반복문 etc
② Backtracking
③ Greedy
④ Divide and Conquer
⑤ Dynamic Programming
패러다임 인지하면 사용할 알고리즘을 선택하는데 도움이 됨.
완전 탐색
(모든 탐색의 근본)
모든 가능성을 탐색함 -> 시간 복잡도 매우 높아질 수 있음
(but '컴퓨터'를 사용하는 근본적인 목적은 완전 탐색을 하기 위함임)
완전탐색을 사용하는 경우
1. 범위가 작을 때
2. 일단은 해볼 때
(시간초과하더라도 일단 만들고 나면 최적화할 수 있는 부분이 보임)
완전탐색이 사용되는 예시
1. 모든 가능성 탐색
2. 부분집합생성
3. 순열과 조합
4. 격자탐색
코드 구현 : 반복문, 재귀, 비트마스크
코딩테스트에 꼭 나오는 편
예제 1)
1. Two Sum
https://leetcode.com/problems/two-sum/description/
내 풀이
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(1, len(nums)-i) :
if nums[i] + nums[i+j] == target:
return [i, i+j]
대희님 코드
def twosum(nums=[4, 9, 7, 5, 1, 10, 15, 56], k=3, target=17):
length = len(nums)
for i in range(length):
value = nums[i]
if k == 1:
if value == target:
return [i]
else:
next_target = target - value
result = twosum(nums[i + 1 :], k - 1, next_target)
if result is None:
continue
else:
next_result = list(map(lambda x: x + i + 1, result))
next_result.append(i)
return next_result
강사님 코드
- 재귀로 구현
(+) 중첩함수
twosum() 함수 안에 recur()함수를 정의
(함수 나중에 조금 다듬기)
def twosum(nums, k, target):
n = len(nums)
start = 0
answer = []
def recur(start):
# base case
if len(answer) == k: # k 만큼 호출됐나?
# if sum([nums[answer[i]] for i in range(k)]) == target:
# print(answer)
for i in range(k):
sum += nums[answer[i]]
if sum == target:
print(answer)
# sum += nums[i]
# if nums[answer[0]] + nums[answer[1]] + nums[answer[2]] == target:
# print(answer)
return False
#recursion
for i in range(start, n):
answer.append(i)
recur(i+1)
answer.pop()
# append, 재귀, pop 이런 구조!!!!!!!!!!
return recur(start)
받은 피드백 정리하기
# 중첩함수
# 대희님 : 인자로 받은 list의 요소들의 합을 반환하는 sum 함수 같은 걸 만들어서 사용해야 할 것 같아요
# 주형님 : sum(list)하면 되니까요 근데 이건 k==3일 때 한정인 코드라 k==n일 때를 가정하면, target == n_sum이면 nums[i]를 뺀 거에서 new_target = n-1_sum이런 식으로 재귀 불러도 될 것 같아요
# 현지님 :
# if len(answer) == k:
# sum = 0
# for idx in answer:
# sum += nums[idx]
# if sum == target: print(answer, np.take(nums, answer))
# 저는 그냥 여기는 반복문으로 구현했어요! 여기서 np.take써서 해당 인덱스에 맞는 원소를 뽑아내서 같이 볼 수 있도록 해봤어욥!
학습자료 2.4 재귀 (Recursion) 보면서 복습하기!
예제 2) 조합 / 순열 / 부분집합
(1) combination
(1-1) given : list, k
def combination(nums, k):
n = len(nums)
ans = []
def recur(start, tmp_ans):
# base case
if len(tmp_ans) == k:
ans.append(tmp_ans[:])
return
# recursion
for i in range(start, n):
tmp_ans.append(nums[i])
recur(i+1, tmp_ans)
tmp_ans.pop()
recur(0, [])
print(ans)
(1-2) given : n, k
def combination_n(n, k):
ans = []
tmp_ans=[]
def recur(start):
if len(tmp_ans) == k:
ans.append(tmp_ans[:])
return
for i in range(start, n+1):
tmp_ans.append(i)
recur(i+1)
tmp_ans.pop()
recur(1)
print(ans)
(2) permutation
(2-1) given : list, k
def permutation(nums, k):
n = len(nums)
ans = []
tmp_ans=[]
def recur(start):
# base case
if len(tmp_ans) == k:
ans.append(tmp_ans[:])
return
# recursion
for i in range(n):
if nums[i] not in tmp_ans:
tmp_ans.append(nums[i])
recur(i+1)
tmp_ans.pop()
recur(0)
print(ans)
return ans
(2-2) given : n, k
def permutation_n(n, k):
ans = []
def recur(start, tmp_ans):
# base case
if len(tmp_ans) == k:
ans.append(tmp_ans[:])
return
# recursion
for i in range(1, n+1):
if i not in tmp_ans:
tmp_ans.append(i)
recur(i+1, tmp_ans)
tmp_ans.pop()
recur(0, [])
print(ans)
return ans
(3) subset
(복습 후 코드 정리해서 넣기)
참고자료
itertools에서 combinations를 import 해서 한줄로 구현 가능
from itertools import combinations
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
return list(combinations(range(1, n+1), k))
재귀함수의 구조
1. 점화식
ans.append(i)
recur(i+1)
ans.pop()
2. base case
(무한반복되지 않도록 무조건 탈출 케이스가 있어야 함)
https://www.nossi.dev/edd45041-6c62-4d69-badc-b14af14def31
Backtracking
완전탐색을 최적화한 패러다임
solution이 될 가능성이 없을 때 반복문을 빠져나옴
if 문 한줄만 추가하면 됨
숙제:
https://leetcode.com/problems/word-search/description/
기타 참고 자료
강의자료 keynote로 만드신 듯 -> keynote 알아보기
'Upstage AI Lab 2기' 카테고리의 다른 글
| Upstage AI Lab 2기 [Day042] 자료구조 및 알고리즘 (3) (0) | 2024.02.09 |
|---|---|
| Upstage AI Lab 2기 [Day041] 자료구조 및 알고리즘 (2) (0) | 2024.02.07 |
| Upstage AI Lab 2기 [Day031] Machine Learning Workflow (1) (0) | 2024.01.24 |
| Upstage AI Lab 2기 [Day031] 머신러닝 기초 개념 이해 (1) (0) | 2024.01.23 |
| Upstage AI Lab 2기 [Day028] 실시간 강의 - 통계(4) (0) | 2024.01.19 |
