이진탐색이란?이진탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾거나, 그 값이 위치할 수 있는 인덱스를 찾는 데 매우 효율적인 알고리즘이다.즉, 최적의 값이나 인덱스의 위치를 찾는데 유용하다.이진탐색의 종류 1. 값이 삽입될 인덱스를 이진탐색하는 경우목적: 특정 값이 위치할 수 있는 배열의 인덱스를 찾는 것.방법: 배열에서 중간 인덱스를 선택하고, 찾고자 하는 값과 중간 인덱스의 값을 비교한다. 찾고자 하는 값이 중간 인덱스 값보다 작다면, 배열의 왼쪽 절반을 검색하고, 크다면 오른쪽 절반을 검색한다. 이 과정을 반복하여 값을 찾거나, 값을 찾지 못하는 경우 해당 값이 위치할 수 있는 인덱스를 반환한다.def binary_search_index(arr, target): left, r..

위상 정렬 (Topological Sorting)이란?정렬 알고리즘의 일종으로, 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.사이클이 없는 방향 그래프(DAG)의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다. 예시그림과 같이 총 3개의 과목이 있다고 가정하자.세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야한다.만약 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다. 진입차수와 진출차수위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 진입차수 (Indegree) : 특정한..

순열 [1,2,3] 중 2개를 뽑아 순열을 만드는 예시 def dfs(level): if level == r: print(result) return for i in range(len(arr)): if checked[i] == True: continue result[level] = arr[i] checked[i] = True # 중복순열이 안되게 -> 앞자릿수에서 선택한 값은 뒤에서 선택될 수 없음. dfs(level + 1) checked[i] = False # 다시 새로운 result를 만들어낼 때 숫자가 선택될 수 있게 print(level, checked) arr = [i + 1 for i in range(3)] r = 2 result = [0] * r checked = [False] * len(a..

이중 포인터 포인터를 가리키는 포인터는 다른 포인터의 주소를 보유하는 포인터로 생각하면 된다. 1) 단일 포인터 - int에 대한 일반 포인터 : 하나의 별표(*)만 사용해서 선언 int* ptr; 2) 이중 포인터 - int에 대한 포인터를 가리키는 포인터 : 두개의 별표(**)를 사용해서 선언 int** ptrptr; ▪︎ 단일 포인터와 이중 포인터 사용 예시 int value = 5; int* ptr = &value; cout

δ(A, B) : A->B로 가는 최단경로 w(A, B) : A와 B 사이의 연결된 edge의 weight if) A와 B 사이에 연결된 edge의 weight = 5 -> w(A,B) = 5 if) A와 B 사이에 edge가 X -> w(A, B) = ∞ (갈 수 없으므로) Single-Source Shortest Paths 시작 정점(s)이 하나 주어졌을 때, s에서 다른 모든 노드로 향하는 shortest path를 찾는 문제 Dijkstra Algorithm - S라는 이미 방문한 정점들에 대한 set 유지 -> 처음엔 비어있고, 시작과 동시에 시작 정점이 s에 들어가게 된다. - D라는 distance array를 정점 수만큼 유지 -> D[i]는 현재까지 밝혀진 경로들 중 최단 경로 (d(s,..

Go-Back-N과 Selective Repeat의 차이 - time out이 발생했을 때 어떻게 처리하냐가 이 둘의 큰 차이점 ▪︎ Go-back-N - N개를 실행하다 문제 발생 시 다시 뒤로 간다. - sender는 ACK를 받지 않고 최대 N개까지 파이프라인 형식으로 보낼 수 O - receiver는 오직 cumulative ack를 보냄. - 항상 자신이 정상적으로 받았던 마지막 seq #의 packet에 대해서만 ACK를 보냄. ex) 3번을 보냄. -> seq # 0,1,2,3에 대한 패킷은 모두 정상적으로 받았음을 의미 - 순서에 맞지 않게 온 packet은 모두 무시 -> gap은 허용 X - sender는 ack를 아직 받지 않은 가장 오래된 패킷에 대해 timer를 실행 (N개 단위로..