추천 사이트 : 오픈 소스로 셀프스터디를 할 수 있는 곳 :https://github.com/ossu/computer-science - OSSU(OSSU: Open Source Society University) 컴퓨터 과학(Computer Science) - GitHub 페이지는 누구나 컴퓨터 과학 학위를 무료로 온라인에서 공부할 수 있도록 돕는 학습 로드맵을 제공 - 무료 온라인 강의를 통해 컴퓨터 과학의 기초부터 고급 과정까지 배울 수 있도록 설계 -기초 학습 과정: 수학, 논리, 프로그래밍 기초 등의 기본적인 컴퓨터 과학 지식을 다룹니다. -핵심 과정: 데이터 구조, 알고리즘, 운영체제, 컴퓨터 네트워크 등 컴퓨터 과학의 필수 과목들을 포함 -전문 과정: 인공지능, 머신러닝, 보안, 데이터베이스 등 심화 학습을 위한 다양한 선택 과목들이 포함 -프로젝트 과정: 이 과정을 통해 학습자는 실습을 통해 배운 지식을 실제 프로젝트에 적용 - 모든 강의는 무료로 제공되며, Coursera, edX, Udacity 등 다양한 교육 플랫폼의 강의들을 활용 - 자신의 속도에 맞춰 공부할 수 있으며, 완전히 독립적으로 학습하는 것을 목표 - 여기의 강의를 다 들으면 적어도 4년 학부를 졸업
코딩 테스트 공부 법 :https://www.acmicpc.net/에서 문제 풀기 - 코딩테스트는 많이 풀어보는 게 최고 : 최대한 많이 200문항 이상 풀어보기 - 모르면 답을 보고서라도 풀어보기 - 코딩테스트는 꾸준히 많이 하는 게 중요함
Oriention
Introduction to Computer Science
Computer Science and Engineering(이하 CSE) - 계산, 자동화 및 정보를 연구하는 학문이다. 컴퓨터 과학은 알고리즘, 계산 이론, 정보 이론, 자동화 등의 이론적 분야부터 하드웨어 및 소프트웨어의 설계와 구현 등의 실용적 분야까지 포괄
- CSE에 포함되는 여러가지 분야 중에 다음 분야를 보통 중요하게 다룬다. (학부 레벨에서) 1. Basic Concepts of Programming Language + 특정 언어 하나(C, Java, **Python**) - 프로그래밍 언어 컨셉을 자체로 배우는 것, 언어자체를 배우는 게 아니라, 언어의 컨셉 2. Data Structure and Algorithms → 코딩 테스트! - 자료 구조 알고리즘 3. Computer Architecture → 컴퓨터의 하드웨어와 시스템 대한 과목. - 하드웨어에 대한 공부, 하드웨어를 제대로 공부를 하려면 전자과. 회로단위의 이론과 실제 구현 - 컴공에서는 컴퓨터의 구성요소와 관련 내용을 중점적으로. 컴퓨터가 어떤 구조로? 4. Operating System → Windows, macOS, Linux, … - 지옥의 과목 : 가장 어려운 과목 : 보통 학부 3학년때 배움 - 이론도 어렵고, 이론보다 더 어려운 건 이걸 구현하는 동작을 하는 게 좀 다른 느낌 5. Computer Network → Ethernet, Wi-Fi 6. Database System → 데이터를 관리하는 시스템에 대한 과목. - RDBS에 대해서 설명하라, 인덱스를 왜 쓰는지 설명하라 7. Software Engineering → 개발 방법론
- 선택 학습 부분 - System of Digital Circuit - Embedded System - Introduction to Compiler Design - Distributed System Concepts - Linear Algebra - Introduction to Statistics - Numerical and GPU Computing - Linux Kernel Development - Scientific Computing - Computer Graphics - Introduction to Cryptography - Machine Learning - Automata - Discrete Mathematics - BigData Mining
CSE - 굉장히 넓은 분야를 커버하고 있고, 분야의 이름을 보면 알 수 있듯 다양한 수학/공학의 영역과 맞닿아있음 - 전자, 기계공학 같은 다른 공학과 다르게 학부 때는 넓은 분야를 다양하게 커버하는 느낌으로 배윰 - 한 가지 깊게 배우는듯한 느낌을 받는게 있다면, Computer System에 대한 내용과 Programming에 대한 내용 (Note : Coding =/= Programming =/= Development) - 컴퓨터를 이용하여 주어진 문제를 계산 가능하게 하는 것 - 두개의 영역으로 나눔 - 컴퓨터가 이해할 수 있게 문제를 정의할 수 있는 “computation Thinking”의 개념 - 가장 중요한건 현실의 문제를 컴퓨터가 계산 가능한 형태로 정의하는 것 - 효율적으로 컴퓨터가 계산할 수 있게 하는 “problem solving”의 영역 - 잘 정의가 된 문제를 컴퓨터가 계산할 수 있게 명령을 내리는 과정 - programming을 자주 해봐야함
number = 2023
if number % 2 == 0:
print("The given number is even!")
else:
print("The given number is odd!")
짝수와 홀수를 확인하는 코드를 만들어내는 과정 - number가 계산 가능한 숫자여야 함. - 홀수 / 짝수를 구분하는 로직이 수학적으로 정의될 수 있어야 함. - 컴퓨터가 “현실적으로” 계산할 수 있는 범위내에 있어야 함.
Computational Thinking - Decomposition : 전체 문제를 작은 여러가지 문제로 나누는 과정. - Pattern Recognition : 주어진 문제의 반복적으로 나타나는 패턴을 찾는 과정. - Abstraction : 문제에서 해결해야할 주요한 정보를 수치화(또는 계산 가능하게)하는 과정. - Algorithmic Thinking : 추천을 수행하는 과정을 step-by-step으로 만드는 과정.
예시로 확인하기 - Example : “Organizing a small team-building event for your office.” (회사에서 소규모 팀 빌딩 이벤트 열기)
1. Decomposition 1. 이벤트에 적합한 날짜 및 시간 선택하기 2. 팀 빌딩 활동 선택하기 3. 장소 예약 또는 필요한 공간 및 장비 준비하기 4. 초대장 발송 및 RSVP 추적 (RSVP; Répondez s'il vous plaît, Reply Please 라는 뜻.) 5. 다과 및 간식 준비
2. Pattern Recognition 1. 직원들은 퇴근 후 금요일에 열리는 이벤트를 선호하는 경향이 있음. 2. 이전의 성공적인 팀 빌딩 활동에는 방탈출과 그룹 요리 수업이 포함되어 있음.
3. Abstraction 1. 가능한 각 활동의 구체적인 세부 사항(예: 특정 방탈출 테마)을 제외한 팀 빌딩 활동 유형 2. 모든 개인의 선호도를 고려하기 보다는 팀원 대다수의 선호도를 선택.
4. Algorithmic Thinking 1. 직원들에게 설문조사를 실시하여 날짜와 선호하는 활동을 선택 2. 선택한 액티비티에 적합한 장소 또는 서비스 제공업체를 조사하고 선택 3. 장소 또는 서비스 제공업체를 예약하고 날짜와 시간을 확인 4. 이벤트 세부정보와 RSVP를 추적할 수 있는 방법(예: 이메일 or 온라인 이벤트 관리 플랫폼)이 포함된 초대장을 발송 5. 확정된 참석자 수에 따라 필요한 다과 및 간식을 구매 또는 주문 6. 이벤트 전에 리마인더를 발송하고 모든 물류 측면이 준비되었는지 확인
Problem Solving - 자료구조나 알고리즘을 사용하여 주어진 문제에 대한 풀이법을 코드로 작성하는 과정 - 특정 요구 사항을 해결하거나 원하는 결과를 얻기 위해 소프트웨어 또는 시스템을 설계, 구현, 테스트 및 최적화하는 작업이 포함
- (일반적으로 불리는) Problem Solving(PS)는 CSE에서 정의하는 각 분야에 맞는 문제로 정의되며, 이를 해결하는 알고리즘을 설계하는 것 - (코딩 테스트 분야) Problem Solving(PS)는 LeetCode, CodeForce로 대표되는 코딩 문제를 해결하기 위한 분야 : 문제 해결을 위한 방법론들(여러가지 풀이 스킬들)이 있으며, 주어진 제한 조건을 만족하는(e.g. Memory capacity, Time limit) 코드를 작성해서 해당 문제에 대한 “정확한” 정답을 출력. : 알고리즘을 설계하고 코드로 풀어내는 것을 연습하기 위해서 만들어진 분야.
- 주어진 2개의 integer list가 있을 때, 두 개의 list가 공통으로 포함하고 있는 모든 원소를 출력하는 코드를 작성하세요.
def find_common_elements(L1, L2):
## TO-DO : 공통으로 포함된 원소를 포함하는 리스트 L을 return하라.
s1 = set(L1)
s2 = set(L2)
L = s1 & s2
L = list(L)
return L
- 이 함수는 두 개의 리스트 L1, L2를 입력으로 받아 공통된 원소가 포함된 리스트를 반환 - L1과 L2는 리스트 형식인데, 이 코드에서는 리스트를 **집합(set)**으로 변환, 집합은 중복된 원소를 허용하지 않고, 집합 연산을 통해 원소들의 교집합, 합집합 등을 계산
Data Structure and Algorithms
Data Structures
데이터를 구성, 저장, 조작하는 방법을 의미
데이터의 특성에 맞춰 효율적 액세스 및 수정이 가능하도록 함
대표적으로 Array(배열), List, Stack, Queue, Tree, Graph 가 포함됨. → 데이터를 효과적으로 표현하기 위해 만들어진 새로운 구조들. → 이런 구조들은 어떻게 만들어질까?
ADT ( Abstract Data Type )
추상화 (Abstraction) - 복잡한 데이터나 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것. - 실제 데이터의 형태를 그대로 다루는 것이 아니라 데이터가 가져야하는 명세(specification)를 기반으로 만듬. - 특성을 나타내는 변수, 필요한 연산 등이 포함됨.
ADT는 프로그래밍을 함에 있어 데이터를 추상화하여 논리적인 구조를 정의한 것
데이터의 특성과 필요한 연산에 맞게 구조를 추상화 → 이렇게 필요한 데이터의 구조를 따로 정의해서 만들게 되면, 코드에서 데이터를 다루기 편해진다. e.g. Python Class, C Struct
ADT를 사용하면 좋은 점 1) 데이터에 대한 정보를 이해하고 저장하는 방식을 결정함으로써 최적의 알고리즘을 개발할 수 있음 2) 프로그래밍을 효율적으로 구현할 수 있도록 도와줌
Time and space complexity
자료구조가 데이터를 효율적으로 처리할 수 있도록 도와준다는 것이 얼마나 효율적인지를 어떻게 평가방법 - 크게 두가지 평가 요소로 나뉨 - Time complexity : 프로그램이 실행되고, 완료되는데 걸리는 시간 - Space complexity : 프로그램이 실행되고 완료되는데 필요한 메모리(DRAM)
실행 시간과 메모리 사용량은 프로그래밍에 있어서 한정적 자원(computing resource)이므로 이를 효율적으로 활용해야 함. → 사용하는 데이터 개수(N)
Space Complexity : 메모리 관련된 게 굉장히 중요하다. - 고정 공간 요구량(Fixed space requirements): 자료구조가 사용하는 고정된 메모리 공간을 의미. - 고정된 크기를 갖는 변수(int, double)가 여기에 포함되며 크기가 정해진 배열의 경우에도 고정 공간 요구량에 속함 -정적 할당(Static allocation)**으로 이루어지는 메모리 공간을 말하며, 실행 중 메모리 사용량이 변하지 않음 - 고정된 크기의 변수(예: int, double 등), 크기가 미리 정해진 배열 (예: int arr[100]) - 메모리 공간은 프로그램이 시작될 때 정해지며, 할당된 메모리는 프로그램 종료 시까지 유지
- 가변 공간 요구량(Variable space requirements): 필요에 따라 동적으로 할당, 해제되는 메모리 공간을 의미. - 특정 instance에 따라서 size가 달라지는 변수들이 여기에 속함. - 계속 가지고 있는게 아니라, 잠깐잠깐 쓰는 것 -> 조절 할 수 있으면 - 동적 할당(Dynamic allocation)으로 이루어지는 메모리 공간 - 동적 배열 또는 리스트(예: ArrayList, LinkedList, vector) 등 크기가 유동적으로 변할 수 있는 자료구조 - 재귀 호출 시 스택 프레임이 메모리를 추가로 사용, 동적으로 할당된 객체들 (예: new 키워드로 할당되는 객체들) - 메모리를 효율적으로 사용하기 위해 필요한 만큼만 할당되고, 더 이상 필요하지 않을 때 해제
- Space Complexity는 고정공간 요구량과 가변공간 요구량을 더해 계산 - 메모리 제한이 있는 환경에서 효율적인 메모리 사용은 프로그램 성능과 실행 가능 여부에 직접적인 영향 - 임베디드 시스템이나 모바일 디바이스 같은 메모리가 제한된 환경에서는 공간 복잡도가 중요한 고려 요소 - 메모리 누수(Memory Leak)가 발생하지 않도록 동적 할당된 메모리를 적절히 해제하는 것이 중요
Space Compliexity 최적화방법 - 변수 재사용: 불필요한 새로운 변수 선언을 피하고, 기존 변수를 재사용할 수 있다면 메모리 사용을 줄일 수 있음 - 효율적인 자료구조 선택: 예를 들어, 트리나 리스트보다 메모리를 덜 차지하는 해시 테이블을 선택하는 경우 - 재귀 호출 최적화: 재귀를 반복문으로 변경하거나 tail recursion을 사용해 스택 메모리를 줄일 수 있음
Time Complexity - Compile Time과 Execution Time으로 나뉘는데, 우리는 Execution Time의 complexity만을 계산 - Compile Time : 작성한 프로그램이 실제 컴퓨터가 실행 가능한 Machine Instruction으로 변환되는데 걸리는 시간 → 우리가 조절이 불가능 : 컴파일러에 의해 자동화되어 있으며, 프로그래밍 언어의 특성상 고정된 변환 과정을 따름 : 프로그램 개발자가 조정을 하는 부분, 코더는 조정하기 매우 어렵고 비효율적 - Execution Time : Machine Instruction이 실제로 연산이 되는데 걸리는 시간: → **프로그래밍 언어 레벨에서 얼마나 실행 시간이 걸리는가!** : 코드만 딱 보고 계산할 수 있는 실행 시간에 관련된 연산을 의미!
# NN단 코드를 예시로 살펴봅시다.
step_count = 0
for dan in range(2, N+1): # N+1 -2 = N-1
for number in range(1, N+1): #N
# step_count
print(f"{dan} x {number} = {dan*number}")
step_count = step_count + 1
print(step_count) #(N-1)* N = N^2 - N
Best, average, and worst-case analysis - 어떤 프로그램의 경우에는 다른 input에 대해서 다른 복잡도를 가지는 경우도 있음 - 이러한 경우에 case를 Best, Avarage, Worst로 구분해서 복잡도를 평가
Big Oh, Big Ω, and Big Θ notation - count를 하나하나 체크하는 것 치고 정확도면에서 비효율적임 → Why? **dominant term의** 영향이 크기 때문에!
- 따라서 복잡도를 표현하는 방법으로는 Big Oh, Big Ω, and Big Θ notation을 사용 - Big Oh는 최악의 경우(최대로 걸릴 수 있는 상한 시간) - Big Ω는 최선의 경우(최소로 걸릴 수 있는 하한 시간) - Big Θ는 평균의 경우. - 보편적으로 Big Oh 표기법을 가장 많이 씀. - Quick sort를 사용한다고 쳤을 떄, 정렬에 대한 각 케이스별 time complexity : 면접 예시 질문 1. best case : O(N) 2. average case : O(N logN) 3. worst case : O(N^2)
- Big Oh: 주어진 복잡도 f(n)에 대해서 어떤 상수 c와 g(n)을 곱한 값이 f(n)보다 크다면 f(n)의 시간 복잡도는 O(g(n))으로 표현할 수 있음.
Stacks Stack(스택) : LIFO (Last In First-Out) 구조를 가진 자료구조 - 후입선출(LIFO: Last In, First Out) 방식 : 나중에 들어간 데이터가 먼저 나오는 방식 - 구조는 List와 비슷하나 기능적인 면에서 차이가 있음 - 삽입과 삭제가 항상 제일 뒤(최근) 요소에서 이루어짐 ( 가장 최근에 삽입한 요소를 top ) - stack 구조는 컴퓨터 가상메모리의 Stack 영역에서 사용 : 함수가 호출되면서 다시 복귀할 주소를 저장하거나, 지역변수, 매개변수 등을 임시로 저장하는데에 쓰임 - 주요 연산 - top : stack의 가장 뒤 요소를 지칭하며 삭제 없이 접근하기 위해서 사용. 파이썬에서는 리스트 인덱스를 통해 접근 - Push: 스택의 가장 위에 데이터를 추가하는 연산. - Pop: 스택의 가장 위에 있는 데이터를 제거하고 반환하는 연산. -Peek(또는 Top): 스택의 가장 위에 있는 데이터를 제거하지 않고 조회하는 연산. - isEmpty: 스택이 비어 있는지 확인하는 연산. -isFull: 스택이 가득 찼는지 확인하는 연산(고정 크기의 스택일 경우). - stack의 구현은 Array나 List 모두 가능하다. - 파이썬에서는 List를 통해 구현 - Basic operations (push, pop, is_full, is_empty) - Stack에 대한 기본적인 기능에는 push, pop, top, isFull(배열로 구현된 경우), isEmpty 가 있다. - push: stack의 가장 뒤에 요소를 삽입.
# list로 stack을 만들어보자. # LIFO, FILO
stack = []
stack.append(1) # push operation
stack.append(3)
stack.append(5)
stack.append(10)
print(stack) # [1, 3, 5, 10]
stack.pop(-1) # pop operation ## 10 ### pop: stack의 가장 뒤 요소를 제거 후 return.
top = stack[-1] # top: stack의 가장 뒤 요소를 지칭하며 삭제 없이 접근하기 위해서 사용. 파이썬에서는 리스트 인덱스를 통해 접근
class STACK: #Stack class에 대한 선언 및 초기화:
def __init__(self, max_size=5): # 데이터를 담을 list와 top, max_size를 통한 list 크기를 정함
self.stack = [] # top은 배열에서 제일 최근에 삽입된 요소의 index 정보를 담고 있으며
self.top = -1 # top이 -1인 경우 비어있는 stack을 의미
self.max = max_size-1
def isEmpty(self): #stack이 비어있는지 여부(비어있다면 True) 길이가 한정적인 stack의 경우 stack이 가득차있는지 여부(가득차있다면 True)를 확인.
if self.top == -1:
return True
else:
return False
# push를 하기 전에 isFull함수를 호출해서 새로운 요소를 삽입할 수 있는지 확인하고, pop을 하기 전 isEmpty 함수를 호출해 삭제할 요소가 남아있는지를 확인한다.
def isFull(self):
if self.top == self.max:
return True
else:
return False
def push(self, item): #push: 스택에 새로운 요소를 삽입
if self.isFullStack() == True:
print("Stack is full.")
else:
self.stack.append(item)
self.top += 1
def pop(self): #pop: 스택의 top을 제거 및 반환
if self.isEmptyStack() == True:
print("Stack is empty.")
else:
pop_item = self.stack[self.top]
del self.stack[self.top]
self.top -= 1
return pop_item
Queue - FIFO (Frist-In, First-Out) 구조를 가진 자료구조 - 먼저 들어온 요소를 먼저 내보냄 - front와 rear로 가장 먼저 들어온 요소와 제일 마지막에 들어온 요소에 접근
- Basic operations (enqueue, dequeue, is_full, is_empty) - Enqueue: queue에 원소를 삽입 - Dequeue: queue에서 원소를 삭제
# queue를 list로 만들어봅시다.
L = []
# 4개의 원소를 enqueue
L.append(1) # [1]
L.append(2) # [1, 2]
L.append(3) # [1, 2, 3]
L.append(4) # [1, 2, 3, 4]
# 2개의 원소를 dequeue
L.pop(0) # [2, 3, 4]
L.pop(0) # [3, 4]
class QUEUE:
def __init__(self, max_size=5):
# 큐를 빈 리스트로 초기화하고, front와 rear 인덱스를 0으로 설정
# 큐의 최대 크기(max_size)를 받아서 최대 인덱스(self.max)는 max_size - 1로 설정
self.queue = []
self.front = 0
self.rear = 0
self.max = max_size - 1 # 큐의 최대 크기를 설정 (0부터 시작하므로 -1을 해줌)
def isEmpty(self):
# 큐가 비어 있는지 확인: front와 rear가 같은 경우 큐가 비어 있다고 판단
if self.front == self.rear:
return True # 비어 있으면 True 반환
else:
return False # 비어 있지 않으면 False 반환
def isFull(self):
# 큐가 꽉 찼는지 확인: rear가 max 값과 같으면 큐가 꽉 찬 것으로 판단
if self.rear == self.max:
return True # 가득 찼으면 True 반환
else:
return False # 가득 차지 않았으면 False 반환
def enqueue(self, item):
# 큐에 새로운 항목을 추가 (enqueue)
if self.isFull() == True: # 큐가 가득 찼는지 확인
print("Queue is full.") # 가득 찼다면 항목을 추가하지 않고 메시지 출력
else:
self.queue.append(item) # 가득 차지 않았다면 항목을 큐에 추가
self.rear += 1 # rear 인덱스를 1 증가시켜서 다음 항목이 들어갈 자리를 설정
def dequeue(self):
# 큐에서 항목을 제거 (dequeue)
if self.isEmpty() == True: # 큐가 비었는지 확인
print("Queue is empty.") # 비어 있다면 항목을 제거하지 않고 메시지 출력
else:
pop_item = self.queue[self.front] # 큐의 front 인덱스에 있는 항목을 꺼냄
# pop_item을 삭제하고 자동으로 인덱스가 재조정됨
del self.queue[self.front] # front 인덱스에 있는 항목을 삭제
return pop_item # 제거한 항목을 반환
Linked List and Hash Table
Array vs Linked List
- Array(배열) 은 연속된 메모리 공간에 같은 타입의 데이터를 순차적으로 저장하는 자료구조 - 인덱스를 통해 빠르게 접근할 수 있음 - 크기가 고정되어 있기 때문에 배열을 생성할 때 크기를 지정해줘야 함 - 배열이 가득 차는 경우 새로운 데이터를 추가할 수 없거나 기존 데이터를 삭제해야 할 수 있음. - Python에서는 numpy array에서 소개됨
Linked List : array와 다르게 생성 후에 자유롭게 원소를 추가/삭제할 수 있는 자료구조 - 가변적인 길이를 가지고 있기 때문에, 새로운 데이터 추가에 대한 제한이 거의 없음 - 기본적으로는 하나의 요소에 그 다음 요소가 연결되어 있는 단순 연결리스트의 형태로 구현 - 경우에 따라 원형 연결 리스트, 이중 연결 리스트 등으로 나타냄
List 자료형에 대한 Basic operations(access, update, insert, delete) - 배열과 리스트에서 기본적으로 수행되는 작업으로는 데이터의 접근, 업데이트, 삽입, 삭제 등이 있음. - Access: 데이터에 접근을 하기 위해서는 인덱싱과 슬라이싱을 사용 - 인덱싱: 하나의 요소에 접근. - 슬라이싱: 범위의 요소에 접근. - Update: 데이터를 업데이터하기 위해서는 인덱스를 사용하여 해당 위치에 값을 할당 - Insert: 데이터를 삽입하고자하는 위치에 새로운 값을 삽입 - Delete: 배열에서는 해당 인덱스를 삭제하고 뒤의 요소를 앞으로 땡겨 빈공간을 채우고, 리스트에서는 해당 노드를 삭제하고 앞 뒤 노드를 연결한다.
Hash Table
데이터의 key를 hash fuction을 통해 hash value으로 변환, 이 값을 인덱스로 사용하여 데이터를 저장하거나 검색하는 효율적인 자료 구조
f : x % 3 (hash function) 0 -> index 0 1 -> index 1 2 -> index 2 3 -> index 0 4 -> index 1 5 -> index 2
- 평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있다. - Python의 dict가 hash table로 구현되어 있다. - Hash function을 통해 저장할 곳을 구분하므로, 어떤 함수를 쓰느냐에 따라 성능 차이가 난다. - 사용 목적은 정해진 메모리에 여러 원소를 효율적으로 저장하여 indexing 성능을 O(1)에 가깝게 만드는 것 - Hash function을 통해 hashing을 하게 되면 다른 원소가 같은 index를 가지는 Hash collision(해쉬 충돌) 이 발생한다. - Hash collision을 해결하기 위해서 많이 사용되는 방법은 아래 두 가지가 있다.
Separate Chaining - 방법: 해시 테이블의 각 인덱스에 연결 리스트나 다른 자료 구조를 사용하여 여러 개의 key-value pair를 저장 - 장점: 간단하고 동적으로 크기를 조절하기 쉬움
Open Addressing - 방법: 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장 - 장점 : 하나의 인덱스에 많은 원소가 chaining 되는 것을 방지
Trees and Graphs
Tree는 데이터 속 항목을 계층적으로 구조화하는 자료구조( 윈도우 폴더-파일 구조 (Directory))
Tree와 관련된 용어 설명 - Node : 트리 구조의 교점으로 Node는 **데이터(value)를 가지고 있고, 자식노드를 가지고 있습니다.** - Root Node: 트리구조에서 가장 위에 있는 노드. 즉 시작점이 되는 노드입니다. - edge(link): 트리를 구성하기 위해*노드와 노드를 연결하는 선 입니다. - level : 트리의 특정 깊이를 가지는 노드의 집합 입니다. - degree: 각 노드가 지닌 가지의 수를 말하며 '차수'라고도 합니다. (child node의 개수) - Leaf node(Terminal Node): 하위에 다른 노드가 연결되어 있지 않은 노드 - Internal Node : Leaf노드를 제외한 중간에 위치한 노드들을 말합니다. - Height(=depth) : 트리에 가장 큰 Level의 숫자
Tree의 종류들 - Binary tree : 자식 Node가 최대 둘 뿐인 Tree. - 비슷한 Tree로는 자식 node가 최대 세 개인 Ternary Tree가 있다.
- balanced Tree : 어느 한쪽으로 데이터가 치우치지 않도록 균형을 지킬 수 있는 규칙을 가지고 있다는 특징
Introduction to graphs - 그래프는 관계를 표현하기 위한 자료구조 - 트리도 일종의 그래프 중 하나에 속함
- Graph 용어 설명 G = {V, E} - Vertex(=Node) : Tree에서의 Node와 같은 개념 - Edge(=Link) : 정점과 정점을 있는 선 - weight: edge의 가중치값 - degree : Vertex에 연결되어 있는 Edge 수 - `out-degree`: 방향이 있는 그래프에서 정점에서부터 출발하는 간선의 수 - `in-degree`: 방향이 있는 그래프에서 정점으로 들어오는 간선의 수 - Path : V_i에서 V_j까지 간선으로 연결된 정점을 순서대로 나열한 리스트 ( e.g. A → E = {A, B, D, E} ) - Path Length : 경로를 구성하는 edge의 수 (not sum of weights) - cycle : 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 ( e.g. A → A = {A, B, D, A} )
Graph 유형 설명 - undirected graph: 두 정점을 연결하는 간선에 방향이 없는 그래프. 가장 기본적. - 간선을 (A, B) 와 같은 형태로 표현하고 (A, B)와 (B, A)는 같은 간선이다. - 방향 그래프(Directed Graph, Digraph): 간선에 방향이 있어 정해진 방향으로만 이동할 수 있는 그래프 - 이 경우 간선을 <A, B>로 표현하는데, A는 출발 정점, B는 도착 정점이다. - weighted graph : 정점을 연결하는 간선에가중치(weight)를 할당한 그래프
Dijkstra's Algorithm : 그래프에서 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 ***강의 내용 아님 : 알려주셔서 간단히 정리만 함*** - 알고리즘은 음의 가중치를 가지지 않는 그래프에서 최적의 해를 보장 - 최단 경로 문제를 해결하는 데 널리 사용
- 단일 출발점 최단 경로 알고리즘: 하나의 출발 노드에서 시작해 다른 모든 노드로 가는 최단 경로 - 비음수 가중치 조건: 다익스트라 알고리즘은 간선의 가중치가 음수일 경우에는 작동하지 않음. 모든 간선의 가중치가 0 이상일 때만 정확한 결과를 보장 - 탐욕적 알고리즘: 다익스트라 알고리즘은 매번 현재 최단 경로를 확정된 노드로부터 확장해나가는 탐욕적(Greedy) 방법을 사용
- 작동원리 1. 출발 노드 선택: 시작 노드를 선택하고, 이 노드의 최단 경로를 0으로 설정합니다. 다른 모든 노드의 최단 경로는 무한대(∞)로 초기화 2. 인접 노드 거리 업데이트: 현재 노드에서 이동할 수 있는 인접한 노드들의 거리를 계산하고, 그 거리가 기존에 기록된 값보다 짧으면 그 값을 업데이트 3. 방문하지 않은 노드 중 최단 경로 선택: 아직 방문하지 않은 노드들 중에서, 최단 경로가 가장 짧은 노드를 선택해 그 노드로 이동 4. 반복: 선택한 노드에서 다시 인접한 노드들의 최단 경로를 업데이트하고, 이 과정을 모든 노드를 방문할 때까지 반복 5. 경로 확정: 마지막으로 모든 노드에 대해 최단 경로가 확정되면 알고리즘이 종료
Basic Algorithm Design
Algorithms : 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것 ** 유튜브에 알고리즘이라는 말은 사실상은 맞지 않다*** - 알고리즘은 입력, 출력, 명확성, 유한성(정해진 시간내에 종료), 효율성의 조건을 만족해야함 - 자연어, pseudo code, 순서도, 프로그래밍언어 등으로 표현할 수 있음. *pseudo code (의사코드) : 프로그래밍 언어의 문법에 구애받지 않고 알고리즘이나 프로그램의 논리를 설명하기 위해 사용되는 간단한 코드 형태 - 프로그래밍 언어로 바로 실행할 수는 없지만, 사람들이 쉽게 읽고 이해할 수 있도록 작성된 일종의 알고리즘 설명서 - 좋은 알고리즘이란? 효율성을 고려한 알고리즘 - 공간복잡도와 시간복잡도를 고려해 알고리즘을 짜야 함. `“efficiency”` - Recursion and iterative approaches - 알고리즘의 구현을 위해서 자주 사용하는 접근 방식 두가지가 recursion & iteration 이다. -재귀 방식은 함수내에서 파라미터를 바꿔 새로운 자기 자신을 호출하는 방식이다. (예시)피보나치수열)
# recursion implementation
def fibo(n):
if n > 2:
fibo_number = fibo(n-1) + fibo(n-2)
return fibo_number
elif n == 2 or n == 1:
return 1
#iteration implementation
- 재귀 방식을 이용하는 경우 반복 방식보다 코드가 간결하고 가독성이 좋아 문제를 쉽게 이해할 수 있다는 장점이 있다. - 하지만 그 과정에서 계속적인 함수 호출은 스택에 함수 호출과 복귀 위치 등의 정보를 계속해서 추가하기 때문에 스택 오버플로우 문제가 발생할 수 있고, 시스템에 부담을 주기도 한다. - 이미 우리가 익숙한 방식은 반복을 적용한 알고리즘인데, for문, while문과 같은 loop 반복문을 통해서 문제를 해결한다. - 이 경우 스택 오버플로우 문제가 없고, 시스템적 부담이 적다는 장점이 있지만 코드가 복잡해진다는 단점이 있다. - 뒤에 search algorithm에서 서로 다른 방식을 이용해 구현된 탐색을 살펴보자.
Sorting algorithms 리스트에 대한 정렬 알고리즘
정렬 알고리즘은 주어진 데이터를 정해진 순서대로 재배열하는 알고리즘 (ascending, descending) → 비교가 가능해야 한다 (순서가 존재한다) : 보통 숫자 데이터로 진행을 함 [(37.8, 124.19), (38.99, 111.04), (128.44, 72.53)] ['apple', 'banana', 'grape']
(위도, 경도) partial-order 서울 ? 부산 → 2D(euclidean), 3D(Haversine)
