자료구조와 알고리즘 개론
자료출처
Upstage AI Lab 2기 코딩테스트 대비 자료구조와 알고리즘 실강 ppt
/ 개발남 노씨 강사님 https://www.youtube.com/@nossi-dev
교육목표
1. 코딩 테스트 합격
2. 코드를 작성했을 때 예측 및 효율적인 변수, 자료구조에 어떻게 담을까, 논리구조를 어떻게 할까
우선순위 따라 진행, 필요하면 추가 공부
코딩 테스트 Tip
네이버 카카오 코딩 테스트 빡셈
잘 준비하면 경쟁자를 줄일 수 있음
기업마다 해나가는 방향성을 다르게 해야
(IT 기업 vs 제조업 기반 대기업)
기본 유형의 알고리즘만 차근차근해도 중견 기업은 충분히 가능
같은 기업이라도 팀마다 원하는 인재상에 따라 코딩테스트 난이도 차이
"그래도 기본은 해놓아야한다"
코딩테스트 목적
1. 문제해결 능력
문제 이해, 접근 방법(자료 구조 & 알고리즘 이론), 코드 설계(시간 복잡도)
2. 구현능력
프로그래밍 언어, 자료구조/알고리즘 구현
전반적인 내용 관련 아래 링크 참조
https://www.nossi.dev/cote/tip
Nossi.DEV
개발자 취업의 모든 것
www.nossi.dev
효율적인 공부 방법
- 시간 복잡도 부터 시작
- 자주 나오는 필수 자료구조/알고리즘 위주로
- 면접 필요 내용 ≠ 코딩 테스트 필요 내용
- 이론 제대로 이해 후 문제 풀이
- 구현 능력 중요 → 주력 언어 선정 후 체화
- 스터디 권장
cf.
2달간 준비해서 코딩 테스트를 준비해서 통과해도,
한게 없으면 면접에서 보여줄게 없음(= 탈락)
스타트업 부터 다니면서 커리어를 쌓는 식으로 전략을 바꿈
이후 다음 해에 원하던 기업(카카오) 공채에 성공
잘 따라오면 좋은 결과가 있을 것임 자부
자료구조 Data structure
데이터를 저장하고 관리하는 방식
자료구조와 알고리즘은 긴밀한 관계가 있음
ex)
특정 알고리즘 구현 위해 필수 자료구조 존재할수도
and 선택 자료구조 따른 사용 가능 알고리즘이 달라질수도
ex2)
DFS, BFS, Dijkstra
알고리즘
문제해결방법 ; 어떠한 문제를 해결하기 위해 정해진 일련의 절차 or 방법
자주 쓰이는 문제 해결방법 > 패턴화 > 외워야한다
- BFS, DFS, Binary Search, Dijkstra 등
한 문제 해결가능 알고지름 다양함
- 각 문제 적합 알고리즘 선택 필요
- 알고리즘 평가할 수 있어야
- 시간 복잡도 Time Complexity
- 공간 복잡도 Space "
- 구현 복잡도
ex)
array는 index를 통해 바로 접근 가능하지만, linked list는 순차적으로 접근할 필요 있음
반대로 요소를 하나 뺄 때는 모두 데이터를 옮겨야하는 array보다 linked list가 유리
ADT ; Abstract Data Type
추상 자료형
각 자료구조마다 무엇을 위한 것인지 파악하는 것이 필요
Binary Digit = Bit
트랜지스터로 0, 1 표현 = 1bit
8bit = 1bye 2^8 가지 표현가능
2진법 binary
16진법 hexadecimal
1MB - 2^10
integer 정수
Character 문자열
Running Time 실행시간
ram, cpu 성능마다 실행시간 달라짐
= 명확하게 계산하는 것은 불가
코테 실험장에선 1초~10초 사이에서 돌아갈 수 있도록 구성함
= 정렬이 가능하겠다 등 계산을 미리 해두는것
따라서, 시간 복잡도에 대한 개념(어느정도 시간걸리겠다)이 있으면 코드 설계할 때 유리
사실 실행시간을 알 수 있는 방법이 명확히 없다보니까 미리 계산하기 위해서 시간 복잡도를 고려함
시간복잡도
https://www.nossi.dev/cote/timecomplexity
점근표현식을 사용하여 간단히 approximation 개념으로 나타낸 것들
제약조건을 통해 출제 의도와 설계방향을 구체화해두면 좋음
알고리즘 패러다임 Algorithm paradigm
알고리즘보다 더 높은 차원의 추상화
- 완전탐색
- 백트래킹
- 탐욕법
- 분할정복
- 동적 계획법
접근시 패러다임 생각 → 적용할 알고리즘/자료구조 선택 후 풀어나가기
if. 잘 생각 안날 때.. 패러다임을 선정하는 것부터 돌아가 생각하면 도움됨
완전탐색 Exhaustive search
정답이 될 가능성이 있는 모든 후보를 체계적(반복문, 재귀, 비트마스크 등)으로 확인하는 것
모든 가능성 확인 → 가장 정확하고 최적의 해 산출 가능
but 시간 복잡도 매우 높아질 수 있어
적용 케이스
- 주어진 입력 범위 작아 시간이 적게 들때
- 우선 적 답 구하고 과정 최적화하여 시간 줄이고 싶을 때
- 정렬
- 메모이제이션
- 투포인터
- DP
- 백트래킹
- 이진탐색
cf. 완전탐색 vs 브루트 포스
항상 완전 탐색이 기본이고,
코딩 테스트 문제에서도 완전탐색 문제는 꼭 1개 정도는 나옴
(알고리즘의 기반이라)
Q. 더할 횟수를 지정 안한 케이스?
A. 재귀를 활용하면 쉽다
재귀 Recursion
자신을 정의할 때 자기 자신을 재 참조하는 함수를 뜻함
base case
- 더이상 재귀 호출을 하지 않아도 계산 값을 반환할 수 있는 상황(조건)
- 모든 입력이 최종적으로 base case 이용
- 무한 루프 방지용으로 base case가 있어야함
재귀의 경우 코드가 여러번 반복되는 case가 많음 → 2ⁿx O(n)
중첩 함수 짜기가 힘듬 약 10시간 정도씩 투자함 2달간 (단기간에 달성하기 어려움)
Q. 코테 준비할 때 알고리즘 공부는 얼마나 하고 코테문제에 집중하나요?
A. 하나의 파트를 공부하고 관련된 코딩 테스트를 실전 느낌으로 진행,
이후 순차적으로 다음파트로 진행하는 것이 좋았음.
Combination 조합 예제
1. 주어진 nums 리스트의 숫자들 중 k개를 선택하여 target을 만족하는 조합을 출력하기
# 강사님의 코드
nums = [4, 9, 7, 5, 1 ,10, 15, 56]
k = 3
target = 17
def twosum(nums, k, target):
n = len(nums)
start = 0
ans = []
def recur(start):
if len(ans) == k :
if nums[ans[0]] + nums[ans[1]] + nums[ans[2]] == target:
print(ans)
return False
for i in range(start, n):
ans.append(i)
recur(i+1)
ans.pop()
return recur(start)
twosum(nums = [4, 9, 7, 5, 1], k = 3, target = 17)# 어떤 에이스 수강생 분의 구현코드 1
# 강사님께선 개인마다 코딩 스타일이 다르다고 한다.
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
2. Given two integersnandk, returnall possible combinations ofknumbers chosen from the range[1, n]. https://leetcode.com/problems/combinations/description/
# 강사님의 코드
# 직접 구현을 할 수 있어야
def combination(n, k):
ans = []
def recur(start, tmp_ans):
# basecase
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)
return
combination(n = 4, k = 2)
# 어떤 것을 매개변수로 줄지
# 복사를 왜 해야하는지# 어떤 에이스 수강생 분의 구현코드 2
# return 값을 저장하는 방식인 것 같다
class Solution:
def combine(self, n: int, k: int):
def get_items(i = 0, arr = []):
result = []
if len(arr) == k:
return [arr]
for index in range(i, n):
result += get_items(index+1, [*arr,index+1])
return result
return get_items(0, [])
s = Solution()
print(s.combine(n=4, k=2))
cf. 내장 라이브러리 사용 코드
# 라이브러리 활용
from itertools import combinations
c = combinations([1,2,3,4], 2)
comb_list = list(c)
print(comb_list)
내장 라이브러리를 사용하면 실수할 가능성을 줄여주고, 시간을 아낄 때 도움이 많이 됨
cf2. python 코드 동작방식 볼 수 있는 사이트
https://pythontutor.com/python-compiler.html#mode=edit
Python compiler - visualize, debug, get AI help from ChatGPT
Write code in Python 3.11 [newest version, latest features not tested yet] Python 3.6 [reliable stable version, select 3.11 for newest] Python 2.7 [unsupported] ------ Java C (C17 + GNU extensions) C++ (C++20 + GNU extensions) JavaScript (ES6) Visualize Ex
pythontutor.com
3. 부분집합 및 순열
# 부분집합
def subset(nums):
ans = []
n = len(nums)
def recur(start, tmp_ans):
ans.append(tmp_ans[:])
# basecase
if len(tmp_ans) == n:
return
for i in range(start, n):
tmp_ans.append(nums[i])
recur(i+1, tmp_ans)
tmp_ans.pop()
recur(0, [])
print(ans)
return
subset([4,6,2,7, 8])
# 순열
def permutation(n, r):
ans = []
tmp_ans = []
def recur():
if len(tmp_ans) == r:
ans.append(tmp_ans[:])
return
for i in range(1, n+1):
if i not in tmp_ans:
tmp_ans.append(i)
recur()
tmp_ans.pop()
recur()
print(ans)
permutation(4, 2)
수강생 공유 Tip
- 릿코드나 프로그래머스 같은 곳에서 다른 사람들의 풀이를 볼 수 있어서 참고하면서 공부하는 것도 좋음
- 읽는 게 불편하지 않으시다면 다른 언어를 사용하는 사람들은 어떻게 풀었나 보는 것도 좋음
재귀 코드를 완전히 이해를 하고 소화를 한다면 최대의 소득이라고 생각함
코딩테스트 학습자료 모음집 관련하여 일자별로 정리해줄 예정
> 초대메일 확인
코딩테스트는 모두에게 어려우며, 복습하는 게 필요하다
'일별 학습일지' 카테고리의 다른 글
| 2/13~2/23 :: ML PJT (0) | 2024.02.23 |
|---|---|
| 2/7 :: 실강 (0) | 2024.02.07 |
| 1/24~2/2 :: ML 이론 (0) | 2024.02.02 |
| 1/22 :: 실강 (0) | 2024.01.24 |
| 1/19 :: 실강 (0) | 2024.01.22 |
