1-1. 순열▪︎ itertools 사용permutations(iterable, r =  None) : iterable에서 원소 개수가 r개인 순열 뽑기from itertools import permutationsarr = ['A', 'B', 'C']# r을 지정하지 않거나 r = None으로 하면 최대 길이의 순열 리턴for i in permutations(arr): print(i) '''출력결과:('A', 'B', 'C')('A', 'C', 'B')('B', 'A', 'C')('B', 'C', 'A')('C', 'A', 'B')('C', 'B', 'A')'''▪︎ 백트래킹1, 2, 3, != 3, 2, 1이므로 이전에 방문했던 곳도 재방문 해야 함.-> visited 방문 여부 표시 필요 O1..

이진탐색이란?이진탐색(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,..