minjoo0613 님의 블로그

그래프를 탐색하는 방법에는

깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 있음.

1. 깊이 우선 탐색(DFS)

: 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동
즉, 루트노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 모든 노드를 방문하고자 하는 경우 이 방법을 선택

- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

2. 너비 우선 탐색(BFS)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
즉, 루트노드(혹은 다른 임의의 노드)에서 시작한 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택함

✴️ DFS/BFS 간단한 비교
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
- 너비 우선 탐색의 경우 - 나와 가까운 관계부터 탐색

깊이우선탐색(DFS)	너비우선탐색(BFS)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택(stack) 또는 재귀함수로 구현	큐(Queue)를 이용해서 구현

🔸DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 탐색한다는 점에서 시간 복잡도는 동일함.


💡dfs, bfs에 가중치가 붙으면 사용할 수 없음

3. 최단거리 알고리즘

: 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘

✏️다익스트라 알고리즘
- 가중치 그래프상에 존재하는 특정한 두 정점의 최단거리를 계산하는 알고리즘 (실제 자동차 네비에서 사용되는 알고리즘 중 하나)

- 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘
- 가중치가 음수가 아닌 경우에만 사용가능

✏️밸만-포드 알고리즘
- 가중치 그래프에서 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
- 음수 가중치에도 사용가능

✏️플로이드-와샬 알고리즘
- 가중치 그래프의 모든 쌍에 대해 최단 경로를 찾는 알고리즘
- 음수 가중치에도 사용가능

DFS와 BFS를 코드로 구현하여 그래프를 탐색해보자

1. DFS(깊이우선탐색)
두가지가 필요함
- visit list (방문한 노드를 체크하는 용도)
- 스택 (스택에 쌓아놓고 나중에 POP해서 출력함) : LIFO(LAST IN FIRST OUT)

2. 코드 구현 (중요도🌟🌟🌟🌟)

DFS를 iterative로 구현하거나 재귀로 구현하는 방식 두 가지를 해보자

보통 그래프를 코드로 구현할 때 딕셔너리 또는 이차행렬로 구현함.

iterative_dfs (while 반목문으로) 코드 구현하는  순서

visit list 만들기 (빈 리스트 생성)
stack 만들기 (처음 들어가는 노드를 스택에 넣는다.)

while 반복문 (모든 노드를 탐색하기 위해) (이때 스택이 비어질 때까지 반복함)
스택에 있는 노드를 꺼낸다(내 손에 노드가 쥐어져있다고 생각하자)
꺼낸 노드가 방문리스트에 있는지 확인
방문리스트에 없다면 노드를 방문리스트에 추가한다. (방문 순서를 알 수 있게 됨)

현재 노드와 인접하는 노드를 꺼내어 스택에 쌓는다
(while문에 의해) pop한 노드가 방문 여부 확인
만약 방문한 노드라면 다른 노드를 pop함

이전과 동일하게 꺼낸 노드와 인접한 노드 중 방문하지 않은 노드를 찾는다
만약 모든 노드를 방문했을 경우 스택에 쌓여있는 노드들이 하나씩 pop 한다
스택이 empty가 되면 코드는 종료된다

🫧visit list를 만드는 두 가지 방법
1. visit 배열을 0으로 만들어놓고 방문하면 1로 체크하는 방법
2. visit 배열을 빈 리스트로 만들어놓고, 방문한 노드를 append 하는 방법 (방문순서를 알 수 있게 됨)

recursive_dfs (재귀함수로) 코드 구현하는 순서

visit list 만들기 (빈 리스트 생성) : 이때 주의할 점, 재귀함수 안에 visit 리스트를 생성하면 함수가 재귀될 때마다 리스트가 초기화 되기 때문에, 함수 밖에 빈 리스트를 선언한다. (좋은 코드는 함수 인자 값으로 빈 리스트를 받도록 함)

현재 꺼낸 노드를 받는 값을 설정해준다. (내 손에 쥐고 있는 노드)
꺼낸 노드가 방문리스트에 있는지 확인
방문리스트에 없다면 노드를 방문리스트에 추가한다. (방문 순서를 알 수 있게 됨)

현재 노드와 인접하는 노드를 꺼내고
인접하는 노드를 재귀함수에 넣는다.
재귀함수에 들어간 노드와 인접하는 노드를 반환하는 것을 계속 반복한다

만약 모든 노드를 방문했을 경우 재귀(스택)에 쌓여있는 노드들이 하나씩 반환된다.
재귀에 쌓여있는 값들이 모두 반환됐을 경우, 자동 종료된다.

3. DFS를 사용하는 용도
- 경로 탐색(최단경로 찾는 게 아니라 경로가 있는지)
- 사이클 검출
- 그래프 연결성 확인

+) DFS를 하면 신장트리를 만들 수 있음

4. BFS(넓이우선탐색)
두가지가 필요함
- visit list (방문한 노드를 체크하는 용도)
- 큐 : FIFO(FIRST IN FIRST OUT)

5. 코드 구현 (중요도🌟🌟🌟🌟)

6. BFS를 사용하는 용도
- 최단 경로 탐색할 때는 BFS가 더 유리함
- 연결 요소 탐색
- 그래프 전체 탐색

📍deque?
큐(Queue) : The order of arrival (줄서기)
데크(deque) : 양방향 큐
==> 앞, 뒤 방향에서 element를 추가하거나 삭제할 수 있음

[아래 용어가 나오면 큐임]
REAR : 데이터가  삽입되는 곳(인덱스라고 생각하면 됨) (스택에선 TOP)
처음에는 rear랑 front의 지점이 같음. 값이 추가될 수록 rear가 한칸씩 앞으로 감
이때 큐의 끝까지 다 갔다면, full of queue 인 거 (queue의 전체 size-1한 값이 rear라면 full인 거 : rear == size - 1)

FRONT : 데이터가 삭제되는 곳(인덱스라고 생각하면 됨)
deque를 하게 되면, front의 위치가 한칸씩 앞으로 가게 됨.

AddQ : 데이터 넣을 때 (스택에선 PUSH)

DeleteQ : 데이터를 삭제 반환할 때 (스택에선 pop)
(add - remove, enqueue - dequeue)

📁 추가 내용

rear == size - 1 이면 queue 는 full 한 상태라고 나타냄. (deque를 해서 모두 값이 없는데도 full 이라고 말함)

그래서, 두가지의 스페셜 큐를 만들어냄.
- Circular queue:  (rear와 front의 출발지점이나 도착지점이 모두 같음 즉 운동장 트랙같은 느낌)
- doubley-Ended Queue: rear와 front 모두 삽입과 삭제를 할 수 있게 하는 큐

Queue 시간복잡도
- deque는 양쪽 끝에서의 삽입과 삭제 연산(popleft)이 평균적으로 O(1)
- 파이썬의 리스트의 pop(0) 시간복잡도가 O(n)

(bc) 파이썬에 리스트는 연결리스트가 아닌 동적배열임.

큐의 First가 Out하면[FIFO] , 리스트 안의 element가 앞으로 한칸씩 이동함. 즉, 시간복잡도 O(n)

==> 즉, DEQ를 사용하면, 조금 더 빠르게 코드를 구현할 수 있음. (시간복잡도 O(1))

📍 deque 사용법

from collections import deque

deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.extend(array): 주어진 리스트를 데크의 오른쪽에 추가한다.
deque.extendleft(array): 주어진 리스트를 데크의 왼쪽에 추가한다.
deque.remove(item): item을 데크에서 찾아 삭제한다. (제일 처음 나온 해당 string만 제거됨)
deque.clear(): 해당 deque 전체 삭제
deque.reverse(): 말그대로 역순으로 정렬한다.
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

그래프

1. 그래프의 약자

Graph(그래프)
Graph : G = (V, E) 이 두개가 세트임
V: vertex (트리에선 노드)
E: a set of pairs of nodes (엣지)
▼▼▼▼▼▼▼▼▼▼
V = {0,1,2,3}
E = {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}
u: tail of the edge
v: head of the edge
<u, v> =/= <v, u>

2. 방향/무방향 그래프

양방향(무방향) 그래프: <u, v> == <v, u>
단방향(방향) 그래프: <u, v> =/= <v, u>

그래프에서 (1,1)이 있다면, 자신이 자신에게로 향한 것임(그런 그래프도 있을 수 있음)

3. 그래프의 용어 (중요도 🌟 🌟)

🔸사이클(cycle): 시작 정점과 종료 정점이 같은 단순 경로 (그런 그래프를 사이클이 있는 그래프라고 부름)

🔸인접성(adjacency): 그래프에서 두개의 정점이 간선으로 직접 연결되어 있다면 인접하다고 말함. (그냥 서로 선이 연결돼있으면 인접한거)

🔸경로(path): 시작 정점에서 종료 정점까지 가는 다양한 경로
이때 다양한 경로가 존재할 수 있다 == length of path 가 다를 수 있음 (짧은 경로가 있을 수 있고, 긴 경로가 있을 수 있음)

🔸연결(Connected): 어떤 노드로 다른 노드로 갈 수 있느냐를 봤을 때, 갈 수 있다면 연결되어있다고 말함
(즉 연결되어있지 않는 그래프가 있을 수 있음. 중간에 경로가 끊긴 겨)

🔸가중치(weight): 지도로 따지자면 하나의 경로에 걸리는 시간이 가중치라고 생각하면 됨. 경로에 부하된 가중치가 있음.

그 가중치로 최단의 경로를 제시해줌. 거리가 짧다고 가중치가 낮다고 볼 수 없음.

4. 트리는 그래프 중 하나

: 트리도 그래프 중 하나이고, 특정한 조건을 만족하여 트리라고 부르는 것

그 조건은,
두 개의 노드 사이에 반드시 1개의 경로만 가지면서, 사이클이 존재하지 않는 방향 그래프
(방향이 위에서 아래로 떨어지는 상하 그래프)

5. 신장트리(Spanning Tree)

: 모든 정점을 포함하지만 모든 엣지를 포함하고 있지는 않으며, 사이클이 없는 연결 그래프

(즉 그래프가 모두 간선으로 이어져있지는 않음)

6. 최소신장트리(Minimum Spanning Tree, MST)

: 신장 트리 중에서도 간선의 가중치 합이 최소가 되는 신장트리를 말함.
MST는 실제로 네트워크 설계, 도로망 구축 등에서 비용을 최소화하기 위해 굉장히 많이 사용

최소신장트리의 알고리즘(일단 지금은 중요하지 않으니 용어만 알아두기)
크루스칼 알고리즘: 모든 간선을 가중치 순으로 정렬한 후 스패닝 트리를 구하는 방법
프림 알고리즘: 시작 정점에서 출발해서 최소 가중치의 간선을 선택하며 트리를 확장해 나가는 방법

7. 그래프를 구현하는 2가지 방법 (중요도 🌟 🌟 🌟 )

- 인접 행렬: 

방향그래프인지, 무방향 그래프에 따라 인접행렬이 달라짐. 무방향 그래프일 경우 인접 행렬은 대칭을 이루게 됨

장점: 행렬이기 때문에 사용하기 편할 수 있음. 근데 행이나 열이 너무 많아지면 표를 나타내는 공간을 많이 차지하기 때문에 쓰기가 어려움 (공간복잡도)

- 인접 리스트: 

연결리스트처럼 표현함

장점: 공간을 덜 차지함 (vertex가 많을 때 인접리슽를 사용하면 좋음)

📁 추가 내용

우리의 관심사는 '순회'임
즉, 주어진 그래프의 특정 정점에서 도달 가능한 모든 정점을 찾는 것
DFS, BFS

DFS(깊이우선탐색) 코드 구현하는 방법 (요약)

탐색할 때 마킹을 해야 함. (해당 vertex는 방문했다는 표시, 즉 표시할 리스트가 필요함)
나랑 인접한 vertex 중에 하나 선택해서 방문함. 그리고 방문하지 않은 vertex로 감
스택에 쌓는다
만약 이미 방문했을 경우 pop한다.(back 한다)
모두 방문했을 경우, 스택에 쌓인 걸 순서대로 pop한다

🔸객체(object)란?

객체는 객체 지향 프로그래밍의 가장 기본적인 단위(혹은 시작점)

모든 현상과 발생하는 모든 사건은 이러한 객체들 간의 상호작용을 통해 발생함

모든 실재하는 대상

🔸객체 지향 프로그래밍

객체들의 모임으로 파악하고자 하는 것

객체를 추상화시켜 속성과 기능으로 분류한 후, 이것을 다시 변수, 함수로 정의함
이전에는 명령어의 목록으로 봤었는데 그걸 바꾸고자 나옴 [절차지향 -> 객체 지향 프로그래밍, 함수형 프로그래밍]

🔸절차 지향 프로그래밍

모든 절차가 다 기술돼있음(ex.Global data) 
- 장점: 컴퓨터가 고민 안하고 순서가 정해져있어서 실행이 빠름, 프로그램 전체가 유기적으로 연결됨
- BUT, 절차지향의 구조가 점차 복잡해짐. 소프트웨어 위기(소프트웨어가 하드웨어 발전 속도를 못 따라감)
그래서 데이터를 중심으로 절차를 도입해서, 현실의 사물을 나타내고 .... 그리하여 oop를 만듦.

🔸객체지향 프로그래밍이 필요한 이유🙆
프로그래밍 왜 배워요? 현실 세계의 문제를 풀도록 프로그램을 설계해서 반영하려고.

🔸객체지향의 장점 👍

1.객체는 잘 만들어놓으면 재사용 가능(class) (반복적인 코드를 최소화하고 코드를 최대한 간결하게 표현할 수 있음)
2. 객체 그 자체로 데이터와 행동이 정의됨(개발자가 내부 구조를 몰라도 바로 사용 가능 -> 생산성이 올라감), 대규모 소프트웨어 가능함
개발 용이성, 유지 보수 편의성, 코드의 신뢰성 -> 생산성이 증가함(keypoint) -> 즉 돈 많이 벌게 됨

🔸객체지향의 단점
1. 클래스 설계하는 게 매우 중요함, 클래스가 잘못 설계되면 다른 부분에도 영향을 끼침 (많은 노력과 시간이 필요)
2. 실행 속도가 상대적으로 느림(컴퓨터가 생각을 해야 돼서)

🔸 클래스

클래스는 객체지향 프로그래밍의 핵심
객체는 클래스에서 정의한 것을 토대로 메모리(실제공간)에 할당된 것이고 클래스는 설계도라고 보면 됨. 원하는 구조의 객체 틀을 짜놓고 비슷한 모양의 객체를 공장처럼 찍어낼 수 있음.

🌟객체: 속성(data) 또는 행동(method)으로 구성된 모든 것🌟
ex. 이찬혁
클래스(설계도):가수, 객체(실제 사례):이찬혁
클래스로 만든 객체를 인스턴스라고"도" 함

🌟 중요 🌟
🌳사용자 정의 타입이 클래스임
(자료형을 메모리에 효율적으로 저장하는데, 내가 원하는 타입을 만들기 위해 하는 것을 클래스라고 한다....?)

🌳파이썬은 모든 것이 객체이다. == 파이썬의 모든 것이 행동과 속성이 존재
클래스를 만드는 건 나만의 데이터 타입을 만드는 것

💡[3,2,1].sort() -> 객체.행동()

✏️기본 문법

- 🐍snake_case (소문자/언더바) (파이썬에서 주로 snake case 사용)

- 🐫camelCase (소문자로 시작하고 이어지는 단어들의 시작은 대문자로 작성. 즉, 의미/단위가 달라질 때  대문자)

- 🐪PascalCase (단어의 첫 시작은 항상 대문자)

💡 Tip) 캐멀케이스>낙타는 "소두"라서 앞에는 소문자이고 뒤에는 다 대문자) (조금 현타..가.. 오지만 암기는 잘될 듯...)

🥕 인스턴스
클래스를 통해 생성된 객체

🥕 메서드
함수. 클래스는 수많은 종류의 메서드를 가질 수 있음.


🥕클래스 정의
class MyClass:   [규칙: 이때는 파스칼 케이스로!]


🥕인스턴스 생성
my_instancd = MyClass()


🥕메서드 호출
my_instance.my_method() (이제부터 인스턴스한테 행동을 호출할 수 있음)


🥕속성 접근
my_instance.my_attribute


💡isinstance(A,B): A가 B타입(클래스 name)을 물어볼 때 사용

🐱참고🐱

a == b 랑 a is b 랑 다름. "=="은 값이 같으면 트루, "is"는 주소가 같으면 트루
is 는 주로 is None 쓸 때 사용함 (None은 값이바뀌지 않기 때문에 주소가 고정임)

클래스 변수와 인스턴스 변수..... 

namespace 
LEGB (뭔데 이거..... 나 왜 모름...)

📌 선형 자료구조(Linear Data Structure)

일반적으로는 배열(array), 연결리스트
파이썬에서는 리스트, 튜플, 큐, 스택

하나의 자료 뒤에 하나의 자료만 있음

🔸특징

- 일직선으로 연결되어 있음
- 이전 - 현재 - 다음 (연속성)
- 각각 요소들이 매핑되어있음

🔸한계점

선형으로된 자료만 표현할 수 있음 == 계층에 대한 표현이 불가함

📌 비선형 자료구조(NonLinear Data Structure)

하나의 자료 뒤에 여러 개의 자료가 있을 수 있음

데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조

계층형 자료구조

🔸 특징

- 한 가지의 소스에서 연결되어 있음
- 하나의 노드가 여러 노드로 전파됨
- 순환구조가 없음 (중요도 🌟🌟🌟)    (단순 순환을 갖지 않고, 연결된 무방향 그래프 구조임)

👉이걸 '트리'라고 함

🔸 조건

🥕조건 01
Node (or Vertes) : 값을 가지고 있는 기본 단위 객체
Edge : 상위 노드와 하위 노드 간의 연결하는 선(link)

🥕조건 02
Root : 트리의 맨 위에 있는 노드, 유일한 부모가 없는 노드
Leaf : 더 이상 자식 노드가 없는 최하위 노드
Internal : root와 left 사이의 내부 노드 

🥕조건 03
Parent : 해당 노드 바로 위에 있는 부모 노드
Child : 해당 노드 바로 아래에 있는 자식 노드
Sibling :동일한 부모를 가지고 있는 노드들

🥕조건 04
ancestor(each node -> root node) : 조상 노드
diancestor(root node -> each node) : 자손 노드

🥕조건 05
Sub Tree : 주어진 노드의 모든 하위 목록 (그 계층을 삼각형 틀로 보면 됨. ex. 나, 금쪽이, 우리 아빠)

🥕조건 06 (중요도🌟🌟🌟)
🌟degree of a node : 특정 노드가 가지고 있는 자식 노드의 수 (주의, 자식과 자손은 다름. 자손은 포함하지 않음)
🌟degree of a tree : 가장 높은 차수를 가진 노드의 차수(즉, 특정 노드가 가지고 있는 자식 노드의 수가 가장 많은 차수를 말함)

🥕조건 07 (중요도 🌟 🌟🌟)
Depth : 노드에서 루트까지의 edge 수
Height : 루트 노드와 가장 먼 leaf 사이의 edge 수
Level : depth + 1

depth of a node : root -> each node의 edge의 수(나뭇가지의 수)
🌟depth of a tree(height) : root -> 가장 깊은 node까지의 edge 수
width of a tree : 각 계층에서 node의 최대 node 수

🌲 Tree의 종류

🍃 Binary Tree(이진 트리)

🍃 Non-Binary Tree

🌲 이진 트리

🍃최대 자식의 수가 2임
🍃차수가 2임

🔸이진 트리 특징 (중요도🌟🌟🌟)

i번째 레벨의 최대 노드 수 : 2^(i-1)  (각 계층의 2의 제곱임)
깊이가 k인 이진 트리의 최대 노드 수 : 2^k - 1

🔸이진 트리의 종류

🌲포화 이진 트리
- 모든 노드가 0개 또는 2개의 자식 노드
- 모든 내부 모드는 두개의 자식 노드를 가져야함
- 모든 리프 노드는 동일한 깊이에 있어야함
- 모든 레벨의 노드가 모두 차있는 트리
- 노드의 수 = 2^depth - 1

🌲완전 이진 트리
- 마지막 레벨을 제외한 모든 레벨이 완전히 채워져있고
- 마지막 레벨의 노드들은 왼쪽에서 오른쪽으로 채워진 트리
(레프트차일드랑 라이트차일드가 다 있어야 됨. 라이트차일드만 있으면 완전 이진트리가 아님)

🌲트리의 순회
Search == Traversal (탐색 == 순회)
- 어떠한 값이 주어졌을 때 해당 값이 일치하는 노드가 있는지 보는 것
- 즉 모든 노드를 봐야함

🔸순회방법

🍎Depth-first search (DFS) (깊이 우선 탐색)

- 계층 순서대로 탐색 (할아버지 - 아버지 - 나)

- 트리의 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방법

- 스택, 재귀 이용하여 구현함

▼이진트리는 특히 세가지 방법으로 구현할 수 있음▼

🥕 Preorder Traversal (전위순회) (A - B - C) (루트 -> 왼쪽 -> 오른쪽)

👉A B D H I E C F G

---

🥕 Inorder Traversal (중위순회) (B - A - C) 왼쪽 -> 루트 -> 오른쪽

👉H D I B E A F C G

---

🥕 Postorder Traversal (후위순회) (B - C - A) 왼쪽 -> 오른쪽-> 루트

👉H I D E B F G C C A



💡전위, 중위, 후위가 헷갈리다면?  >>> "루트"에 집중할 것!
- 전위는 루트 > 왼쪽 > 오른쪽
- 중위는 왼쪽 > 루트 > 오른쪽
- 후위는 왼쪽 > 오른쪽 > 루트

 🍎Breadh-fist search (bfs) (너비)

- 계층별로 탐색 (나랑 금쪽이 계층, 아버지 형제들 계층, 할아버지 형제들 계층)

- 트리의 레벨순으로 노드 탐색

- 큐를 이용하여 구현함

📌프로그래밍 기본

🔸컴파일러

고급 프로그래밍 언어로 작성된 소스코드를 기계어로 번역 및 실행하기 위한 프로그램

🥕 특징: 소스 코드 전체를 분석하고 그 다음 기계어로 번역 후 실행함

🔸인터프리터

컴파일러와 마찬가지로 고급 프로그래밍 언어로 작성된 소스코드를 기계어로 번역 및 실행하기 위한 프로그램

🥕 컴파일러와 차이점: 한 문장씩 소스코드를 번역하고 실행한다는 점

🔸메모리 영역

작업을 효율적으로 하기 위해 다양한 영역으로 나뉨 (이러한 영역들은 운영체제에 의해 관리)

코드 영역 : 프로그램을 실행하기 위해 명령어들이 저장되는 공간 데이터 영역 : static(정적) 변수, 전역 변수와 같은 데이터들이 이곳에 저장, 프로그램 시작과 함께 할당되고 프로그램이 종료될 때 소멸 Heap 힙 영역 : 동적 메모리 할당을 위한 곳으로 프로그래머가 직접 사용 및 관리해야하는 메모리 영역 (큐와 같은 자료구조가 여기서 생성됨) Stack 스택 영역 : 정적 메모리 할당을 위한 곳으로 함수, 지역변수, 매개변수 등을 사용하기 위한 공간 (재귀함수를 사용할 떄 이곳을 사용함)

📌OOP (Object-Oriented Programming, 객체지향 프로그래밍) (중요도🌟)

🔸객체 지향
추상화하고자 하는 객체의 모습을 가상의 공간에 구체화하며 설계해나가는 것

🔸객체
현실세계에 있는 어떤 대상을 추상화한 것을 의미

🔸클래스
객체를 생성하기 위해 어떤 속성과 방법의 집합을 추상화하여 표현한 것을 의미
클래스 안에는 함수, 변수, 클래스 안에 또 클래스 만들 수 있음
클래스 안에 있는 멤버함수와 변수에 접근하기 위해서는 반드시 객체를 이용해야 함


🌟반드시 알아야 되는 개념🌟

🥕상속 다른 클래스의 기능을 사용하고 싶다면 상속을 받아서 부모클래스와 자식클래스의 관계를 만들어주면 됨

🥕오버라이딩(덮어쓴다, 재정의한다) 상속받은 클래스에서 어떤 기능을 재정의하는 것을 의미 부모클래스에서 'get()'이라는 함수가 있는데 이름을 똑같이 자식 클래스에서 'get()'이라는 함수를 만들고 그 기능을 다시 정의

🥕오버로딩(덮어서 불러온다) 연산자 오버로딩, 메소드 오버로딩, 함수 오버로딩 등 다양하게 있지만 일단 파이썬에서는 함수오버로딩은 없다고 생각하면 됨 일반적으로 오버로딩이라고 하면 함수의 이름은 같으나 매개변수를 다르게 설정하여 사용 목적에 따라 다르게 불러오는 것을 의미

📌소프트웨어 개발 방법론

🔸폭포수 방법론
하향식 방법으로 가장 오래된 개발 방법   ’계획 → 설계 → 개발 → 시험 → 유지보수’
순차적으로 진행하며 SDLC(소프트웨어 개발 생명 주기)가 굉장히 김
단점: 매우 큰 규모의 프로젝트에 적합하며 이미 진행된 작업에 대해서는 변경 및 수정이 어려움

---

🔸애자일 방법론
반복적이고 점진적으로 개발하는 방법    '계획 - 설계 - 개발 - 시험 -유지보수'
이해관계자의 피드백을 빠르게 반영할 수 있지만 개발 계획을 세우기 어려움
🥕 변화가 빠른 산업군에서는 효과적
🥕 절차와 도구보다 고객과의 소통에 초점을 맞춤


💡 개발에서는 ’계획 → 설계 → 개발 → 시험 → 유지보수’ 중 계획이 중요함

📌디자인 패턴

🔸 디자인 패턴
소프트웨어를 설계 및 구현할 때 어떠한 공통된 구조를 띄는 형태

🔸 MTV
python기반의 웹 구현을 위한 프레임워크인 Django(장고)가 MTV 디자인 패턴을 지향
(백엔드를 이 패턴으로 구현하게 됨)

M : model(모델)을 의미하며 DB에 데이터를 적재하고 테이블 정의를 담당

T : Template(템플릿)을 의미하며 사용자에게 보여지는 화면을 의미

V : View(뷰)를 의미하며 요청에 따라 필요한 로직을 수행하는 역할을 담당

💡 아키텍처, 소프트웨어 패턴도 있음

📌형상관리

🔸 형상관리
소프트웨어의 변경사항을 추적하고 통제하기위한 작업을 의미

🔸 형상관리를 위한 툴
- git : github, gitlab

📌V&V (Verification & Validation) 검증과 확인

🔸 V&V
소프트웨어의 완성도 및 신뢰도를 검증 및 확인하는 작업
소프트웨어를 개발하면 우리의 의도대로 동작하는지 또는 충분한 성능을 나타내는지, 보안 이슈는 없는지 등 다양한 방면에서 소프트웨어의 완성도를 검증하는 작업

🥕 Verification (검증) 개발자 중심에서 제품이 ‘요구사항’에 만족하게 구현되었는지에 대해 검증하는 작업

🥕 Validation (확인) 사용자 중심에서 제품이 ‘사용감’에 만족하게 구현되었는지에 대해 확인하는 작업

🥕 Test (시험) ☘️[Test 단위]☘️ 단위 - 통합 - 시스템 - 인수 테스트를 순차적으로 실행 - Unit Test(단위 시험): 가장 작은 단위의 test로 함수, 모듈 등 제일 작은 단위의 기능을 test - Integration Test(통합 시험): 함수간, 클래스간, 모듈 간 등 어떤 기능이 합쳐져서 잘 동작하는지 test - System Test(시스템 시험): 실제 적용하려는 하드웨어나 어떤 시스템에 개발한 소프트웨어를 탑재한 뒤 test - Acceptance Test(인수 시험): 출시 및 배포전 최종 test ☘️[Test 종류]☘️ 정적 Test : 소프트웨어를 구동하지 않고 test 하는 방법 - 동료 검토 - 코드 리뷰 - 기술 검토 동적 Test : 소프트웨어를 구동하며 test 하는 방법 - Black Box Test (블랙박스테스트) : 소프트웨어의 작동 원리를 모르는 상태에서 진행하는 test 결과물이 요구사항과 일치하는지 알아보기 위한 test - White Box Test(화이트박스테스트) : 소프트웨어의 작동 원리를 보며 진행하는 test 소프트웨어가 의도한대로 동작하는지 알아보기 위한 test

💡추가내용💡

📌 자료구조

🔸 스택
선입후출 방식의 자료구조, 선입후출이란 먼저 들어온 데이터가 나중에 처리되는 것을 의미
히스토리 기능을 구현할 때 유용하고 DFS(깊이우선탐색), 후위연산, 백트래킹, 유효성 검사 등 다양한 곳에 사용됨

🔸 큐
선입선출 방식의 자료구조
작업스케줄링 기능을 구현하거나 캐시, BFS(넓이우선탐색), 티켓 시스템 등 다양한 곳에서 사용


🔸 비선형 구조
자료들 간에 관계가 1:N로 나열되어 있는 것을 의미

그래프 노드와 간선으로 이루어진 자료 구조를 의미

트리 그래프의 한 종류이며 나무의 가지나 뿌리가 뻗어나는 모양과 비슷 트리인데 자식이 2개만 있다? 이진 트리 🥕완전이진트리: 이진트리에서 거의 모든 노드가 채워져 있으며, 가능한 한 제일 왼쪽부터 채워져 있는 이진트리 구조 🥕트리의 특징으로는 일반 그래프와는 다르게 사이클이 존재하지 않으며 부모노드와 자식노드를 통해 구조를 표현

📌 하드웨어 기본 

메인보드: 컴퓨터의 부품 및 장치들을 설치하여 연동할 수 있게끔하는 부분. 즉, 컴퓨터의 수많은 부품들을 하나로 연결해줌

🌟CPU(중앙처리장치): 컴퓨터의 두뇌, 명령어 해석하여 연산을 수행하는 역할을 하며 컴퓨터의 성능에 가장 크게 관여 (동시에 실행 못함)
- 클럭: CPU의 처리 속도를 나타내는 단위
- 오버클럭: 컴퓨터의 속도를 강제로 빠르게 하는 기술 (클럭의 잠재성을 끌어내기 위해 사용자가 임의로 끌어올리는 것)

🌟GPU(그래픽처리장치): 그래픽 연산을 하기 위해 병렬처리를 할 수 있도록 설계. 하나의 코어는 하나의 연산을 수행할 수 있는데, 이 수천 개의 코어가 동시에 연산작업을 하는 것이 병렬처리임. 연산이 어렵진 않지만 많은 양의 연산을 수행해야하기 때문에 적합함
(디지털 신호를 영상 신호로 바꾸어 모니터로 전송하는 장치 (근데 CPU도 가능하나 매우 느림) )

RAM(주기억장치): 컴퓨터의 수치, 자료, 명령 등을 기억하며 프로그램 및 운영체제가 실행되기 위해 위치되는 곳. (보조기억장치에서 업무를 적재하는 용도로 사용, 컴퓨터의 성능과 관련된 건 CPU)

HDD, SSD(보조기억장치):
- HDD: 비휘발성, 순차접근이 가능한 컴퓨터의 보조기억장치.
- SSD: 플래시 메모리로 구성됨. SSD는 HDD에 비해 데이터 입/출력 속도가 매우 빠름.

가상메모리: 주기억장치의 용량이 부족할 경우 보조기억장치를 주기억장치의 일부인 것처럼 사용 가능

입력장치: 사용자가 컴퓨터를 조작할 수 있게 해주는 모든 장치(키보드, 마이크)
출력장치: (모니터, 스피커, 프린터, 조명)

OS(운영체제): 사용자가 컴퓨터를 조작 및 제어하고 작업의 편의성을 제공하기 위한 '시스템 소프트웨어'

📌 반드시 알아야 되는 개념 (중요도 🌟🌟🌟)

프로세스: 실행중인 프로그램 의미 (실행하지 않은 건 그냥 프로그램이라고 부름)

프로세싱: 프로그램이 실행중인 것을 프로세싱중이라고 말함

🌟멀티테스킹: 하나의 시스템 또는 CPU가 여러 작업을 수행하는 것. 단, 동시에 처리가 되는 것은 아니고 시분할 방식을 통해 동시에 처리되는 것처럼 보이게 함 (하나의 CPU가 여러 작업을 빨리빨리 번갈아 가면서 수행함)

다수의 작업을 운영체제의 스케줄링에 의해 번갈아 가며 수행되도록 해주는 것을 의미 즉, 운영체제가 다수의 작업을 스케줄링하여 우리가 느끼지 못하는 시간마다 작업을 번갈아가며 수행하여 우리 눈에는 동시에 수행되는 것처럼 보이게 함.

멀티 태스킹의 스캐줄링 방식 - 멀티 프로그래밍 방식 - 시분할 방식 - 실시간 시스템 방식

🌟멀티프로세싱: 두 개 이상의 프로세서가 동시에 실행되는 것(여러개의 CPU가 여러 작업을 동시에 수행함)

프로세서와 프로세스의 개념 프로세서는 CPU나 Microprocessor라는 하드웨어를 의미 프로세스는 실제 메모리에 적재되어 프로세서에 의해 실행되고 있는 프로그램을 의미

보통 하나의 프로세서(CPU)가 하나의 작업을 맡지만 멀티 프로세싱은 다수의 프로세서가 다수의 작업을 함께 처리


🌟멀티스레드: 하나의 프로세스가 여러 작업 단위를 가지며 작업을 수행하는 것
(크롬 브라우저 하나 켜놓고 여러 개의 사이트를 틀어놓는 것)

프로세스와 스레드 비교 프로세스를 생성하는 비용보다 스레드를 생성하는 비용이 더 저렴하기 때문에 프로세스에 다수의 스레드를 생성하여 병렬처리하는 것 +) 프로세스는 데이터, 힙, 스택 영역을 서로 공유하지 않지만 스레드는 스택 영역을 제외한 데이터, 힙 영역을 서로 공유하기 때문에 메모리 부분에서도 훨씬 효율적임.

🌟스케줄링: 작업에 필요한 자원을 언제 누가 어떻게 사용할지 결정해주는 것

커널: 하드웨어와 응용 프로그램 사이에서 인터페이스 역할 수행하기 위한 핵심 부분

터미널: 사용자와 컴퓨터 간에 상호작용을 제공하는 인터페이스

CUI: 사용자가 문자를 통해 명령을 수행하는 것을 의미

GUI: 사용자가 그래픽을 통해 명령을 수행하는 것을 의미