[Algorithm] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

사전 지식 탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택과 큐에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - 파이썬에서의 스택(Stack)과 큐(Queue) 재귀함수 자기 자신을 호출하는 함수. 수학의 점화식을 코드화한 것 점화식: 특정 함수를 자기보다 더 작은 변수와 함수의 관계로 표현한 것 재귀 함수는 점점 작아지는 자기 자신 + 종료 조건을 통해 동작한다. 그래프 그래프에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - [Data Structure] 그래프(Graph) DFS (깊이 우선 탐색, Depth-First Searc..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Data Structure] 그래프(Graph)

그래프(Graph) vertex(정점)과 edge(간선)으로 이루어진 자료구조 프로그래밍에서 이를 표현하는 방식으로는 인접 행렬과 인접 리스트가 있다. 인접 행렬 2차원 배열로 그래프의 연결 관계를 표현 INF = 987654321 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] # 0과 1의 연결 관계 graph[0][1] ( == graph[1][0]) 인접 리스트 연결 리스트 자료구조로 그래프의 연결 관계 표현 파이썬에서는 일반 리스트 자료형이 연결 리스트의 역할을 하므로 다음과 같이 구현한다. vertex = 3 graph = [[] for i in range(vertex)] # 0번 간선과의 연결 정보 graph[0].append((1, 7)) graph[0..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Data Structure] 파이썬에서의 스택(Stack)과 큐(Queue)

스택(Stack) 후입선출(LIFO) 구조라고도 한다. 나중에 들어온 게 먼저 나간다. 파이썬에서는 다음과 같이 리스트 자료형을 통해 구현할 수 있다. stack = [] stack.append(0) # [0] stack.append(1) # [0, 1] stack.pop() # [0], return 1 큐 (Queue) 선입선출(FIFO) 구조라고도 한다. 먼저 들어온 게 먼저 나간다. 파이썬에서는 큐를 구현하기 위해 collections 모듈의 deque(덱)을 이용한다. 덱(deque)이란 스택과 큐를 합친 자료구조로, 양 방향에서 삽입/삭제가 가능하다. from collections import deque queue = deque() queue.append(0) # [0] queue.append(..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Algorithm] 구현(Implementation)

구현 알고리즘 실생활의 문제를 코드로 나타내 해결하는 방식 완전 탐색과 시뮬레이션 유형으로 나뉜다. 완전 탐색 (Brute-force search) 모든 경우의 수를 다 계산하는 방식 즉 로직을 간단하게 하기 위해 시간, 공간 복잡도를 늘리는 방식이다. 따라서 주어진 입력의 범위가 적을 때만 사용해야 한다. 시뮬레이션 (Simulation) 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 방식 자주 등장하는 유형 실생활의 문제를 코드로 나타내기 위해서는 수식화 단계를 거쳐야 한다. 좌표로 나타내기 이동 가능한 경로를 계산하는 등의 방식에서 사용된다. # 상하좌우 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] literal = ['Up', 'Down', 'Left', 'Righ..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Algorithm] 그리디(Greedy)

그리디(탐욕) 알고리즘 가장 좋은 것만 취한다는 의미에서의 그리디이다. 이전 결과를 신경쓰지 않고, 현재 상황에서 자신이 가진 최적 값과 입력된 값을 비교해 최적인 값을 취한다. 언제 사용하는가? 최적의 해(최대, 최소 등)를 구해야 하는 경우 주의할 점 항상 최적해를 도출하는가에 대한 주의를 해야 한다. 자주 등장하는 유형 순회하며 최적해 고르기 처음부터 끝까지 쭉 훑으며 비교해 최적해를 계속 갱신하는 방식 배열에서 최대/최소값 찾기가 이에 해당한다. 최적해를 도출할 공식을 정한 뒤 예외를 쳐 냄 항상 최적인 공식이 정해져 있고, 이를 최대한 많이 적용하는 방식 웬만한 난이도에서면 최적인 공식만을 적용할 수 없도록 예외가 존재한다. 이를 빠짐없이 찾아내는 것이 어려워 은근 정답률이 낮은 유형 최대/최소..

• format_list_bulleted 학습/Algorithm
• · 2021. 1. 23.
• textsms

컴퓨터 네트워킹 : 계층, 보안

▶ 왜 계층화를 이용하는가? ＊ 복잡한 시스템을 다루기 위함. ＊ 명시적 구조는 복잡한 시스템 조각 간 식별과 관계 정의를 도움 ＊ 모듈화는 시스템의 유지보수를 쉽게 함 ​ ▶ ISO/OSI reference model ＊ network edge간 통신을 위해 ISO 회사가 만든 OSI 7계층 ＊ 계층을 거치며 데이터는 Encapsulation(캡슐화)되고, Decapsulation(캡슐화의 역과정)된다. ＊ Encapsulation은 헤더를 붙이는 과정, Decapsulation은 헤더를 해석하는(제거하는) 과정이다. ＊ 각 계층마다 데이터는 우측의 명칭대로 불린다. ＊ 애플리케이션 계층 : 네트워크 애플리케이션의 이용을 돕는다. FTP, SMTP, HTTP 등이 있다. source data → mes..

• format_list_bulleted 학습/Networking
• · 2020. 7. 13.
• textsms