가수면

그래프 관계에서 합집합을 찾을 때 유용 parent = [i for i in range(5)] # 부모테이블 초기화 (자기 자신을 부모로 갖도록) # 재귀적으로 파고들어 같은 것을 가리키도록 설정함 def find(x): # parent는 0부터 시작함(parent[0]은 0임) if x == parent[x]: return x else: p = find(parent[x]) parent[x] = p return parent[x] # x와 y가 같은 값을 가리키도록 하여 집합을 묶음 def union(x, y): x = find(x) y = find(y) if x != y: # 더 작은 원소를 부모로 삼도록 설정(=오른쪽 원소의 부모값을 왼쪽 원소로 설정) parent[y] = x union(1, 4) #..

요소를 낱개로 다 쪼갠 뒤 쪼갠 것을 비교해가며 합치는 방식 합칠 때는 다음 과정을 따른다. 1. 2덩어리씩 합침. 이때 정렬해서 합침 2. 2덩어리(a, b) 와 하나로 합쳐질 덩어리(c) 3개에서 각각 index 역할을 해줄 변수들을 3개 만듦 3. index를 활용해 a, b를 비교하고 작은 것을 c에 추가하며 index들을 1씩 증가시키는 것을 반복 4. a, b 한 쪽을 다 채워넣었다면 나머지 한 쪽은 그냥 순차적으로 채워넣으면 됨(a, b모두 이미 반복되는 과정에서 정렬이 보장된 것들임) def merge_sort(array): # 1개가 될 때까지 재귀적으로 쪼갬 if len(array) i and len(right) > j: if left[i] > right[j]: array[k] = le..

그래프 내 특정 노드와 그래프 내 존재하는 모든 노드들 간의 각각 최단 거리를 구하는 알고리즘 원리 1. 초기값 세팅. (기준 노드를 0으로 놓고 나머지 노드들까지의 거리를 inf로 설정) 2. 그래프를 순회하며 순회한 노드들을 우선 순위 큐에 거리가 짧은 순으로 쌓음 3. 하나씩 dequeue하면서 해당 노드까지의 거리로 inf를 수정함 4. dequeue한 노드와 연결된 노드들을 우선 순위 큐에 다시 거리가 짧은 순으로 추가 5. 3번의 과정을 반복하면서 중복된 노드들이 있다면 거리값을 더 작은 값으로 수정 (ex. A->b까지 5인데 A->C->B거리가 3이라면 B의 값은 3으로 교체) 6. 우선 순위 큐를 사용하면 우선 순위가 떨어지는(거리가 먼) 노드들의 계산은 뒤로 갈수록 스킵되기에 빠른 계산..

모든 경우의 수를 놓고 최적의 경우를 고른다기보다는 각 단계에서 최적의 경우를 고르는 전략임 그렇기 때문에 최적의 경우가 아닌 결과가 도출될 수 있음 (탐욕이라는 말이 정말 적절하다...) 문제1: 동전 문제 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) for coin in coin_list: coin_num = value // coin total_coin_count += coin_num value..

이진 탐색 def binarySearch(data, searchValue): if len(data) == 1 and searchValue == data[0]: return True if len(data) == 1 and searchValue != data[0]: return False if len(data) == 0: return False medium = len(data) // 2 if searchValue == data[medium]: return True else: if searchValue > data[medium]: return binarySearch(data[medium + 1:], searchValue) else: # 리스트 슬라이싱에서 [:medium]는 medium을 포함하지 않음 ret..

기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 알고리즘 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함 def quickSort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return quickSort(left) + [pivot] + quickSort(right) list comprehension을 적용 def quickSort(data): if len(data) item ] right = [ item for item in..

상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식Memoization 기법을 사용함 모든 경우의 수를 완전 탐색할 때 사용 하위의 문제들이 중복되어 재활용되는 특징이 있음 대표 예시 - 피보나치 수열 def fibo_dp(num): cache = [ 0 for index in range(num + 1)] cache[0] = 0 cache[1] = 1 for index in range(2, num + 1): cache[index] = cache[index - 1] + cache[index - 2] return cache[num] 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. (1 ≤ ..

예시 배열 - [4, 3, 1, 2] 1회차 - 0 vs 1부터 가장 작은 값 [1, 3, 4, 2] 2회차 - 1 vs 2부터 가장 작은 값 [1, 2, 4, 3] 3회차 - 2 vs 3부터 가장 작은 값 [1, 2, 3, 4] 턴 수 - length - 1 비교값 - (턴 수 - 1)탐색 시작값 - (턴 수) 정리 1. length -1만큼 반복문 2. 1번 안에 전체를 탐색하는 중첩 반복문 (탐색 시작값부터 length -1까지) 3. 제일 낮은 숫자의 인덱스 저장 4. 비교값과 제일 낮은 숫자 비교 후 교체 def selectionSort(data): for index in range(len(data) - 1): lowestIndex = index for index2 in range(index +..

예시 배열 - [9, 3, 2, 5] 1회차 - 1과 0을 비교 후 교체 [3, 9, 2, 5] 2회차 - 2와 1을 비교 후 교체 [3, 2, 9, 5], 1과 0을 비교 후 교체 [2, 3, 9, 5] 3회차 - 3과 2를 비교 후 교체 [2, 3, 5, 9], 2과 1를 비교 후 교체 [2, 3, 5, 9], 1과 0을 비교 후 교체 [2, 3, 5, 9] 턴 수 - length - 1 각 턴의 순회 횟수 - length - 1 비교 후 뒤에 값이 더 클 경우 반복문 종료 앞에 회차에서부터 거슬러오면서 정렬을 했기 때문에 비교 시 값이 더 큰 경우 앞에 값들은 이미 정렬된 값들이라는 확신을 할 수 있음 정리 1. length -1만큼 반복문 2. 1번 안에 index + 1(시작), 0(1 까지),..

2개일 경우 0 1 5 2 0과 1을 비교 3개일 경우 0 1 2 5 2 1 0과 1을 비교, 1과 2를 비교 0 1 2 2 1 5 한번 더 해야함. 4개일 경우 - 0과 1을 비교, 1과 2를 비교, 2와 3을 비교 x 3 순회 횟수 = length -1 반복 횟수 = length -1 기본 로직 1. length -1만큼 반복문 2. 1번 안에 length - 1만큼 중첩 반복문 3. 비교 후 바꿔주는 로직 반복 시 불필요한 순회 빼기 순회할 때마다 해당 순회차의 마지막 값은 확실하게 정렬된 값임 순회차 = i i = 1일 때 반복 횟수 - 1 i = 2일 때 반복 횟수 - 2 반복횟수 = length - 1 - i 순회 시 스왑이 한번도 일어나지 않았을 경우 조기 종료 정리 1. length -1만..

너비 우선 탐색 2개의 큐를 이용 A큐 - 방문한 노드들을 쌓는다. 쌓일 때 연결된 노드들을 B큐에 추가한다. B큐 - 초깃값을 설정한 뒤 큐에 값이 없을 때까지 실행한다. 맨 앞의 노드를 A로 내보낸 뒤 해당 노드와 연결된 노드를 큐에 추가한다. 이때 A에 중복된 노드가 있다면 A에 저장하지 않는다 자바스크립트 ver. class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } addEdge(vertex1, vertex2) { this.adjacencyList[vertex1].push(vertex2); t..

그래프 (Graph) 관련 용어 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로 (Simple Path): 처음 정점과 끝 정점을 제외하고 중복된 정점이 없..

해시 함수 조건 1. 빨라야 함 루프를 최대한 줄여야 함 조건 2. 특정값'만' 뱉으면 안 됨 (충돌 조건임) 예) return 0 조건 3. 같은 값에 대해선 같은 값을 뱉어야 함 Math.floor같은 것을 사용하면 안 됨 소수를 곱해주면 충돌 확률이 낮아짐 function hash(key, arrayLen) { let total = 0; let PRIME_NUMBER = 31; for (let i = 0; i < Math.min(key.length, 100); i++) { let char = key[i]; let value = char.charCodeAt(0) total = (total * PRIME_NUMBER + value) % arrayLen; } return total; } 해시 테이블 ge..

이진 탐색 트리와 이진 힙 비교 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우) 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음 최대 이진 힙 왼쪽 오른쪽 구분 없이 부모 노드가 자식 노드보다 항상 큰 트리 구조 왼쪽 자식 노드 인덱스 => 2n+1 오른쪽 자식 노드 인덱스 => 2n + 2 부모 인덱스 => Math.floor((n - 1) / 2) insert 매소드 class MaxBinaryHeap { constructor()..

너비 우선 탐색 vs 깊이 우선 탐색 시간 복잡도는 같음. 다만, 공간 복잡도에서 효율 차이가 존재함. 깊이가 깊은 트리의 경우 =>너비 우선 탐색 사용 (너비가 넓으면 큐에 노드가 많이 추가됨) 너비가 넓은 트리의 경우 => 깊이 우선 탐색 사용 깊이 우선 탐색 종류 // 10 // 6 15 // 3 8 20 전위 순회 - [10, 6, 3, 8, 15, 20]을 반환하므로 10을 루트로 삼아서 다시 만들 때 좋음(데이터 이전, 복사 등) 후위 순회 - [3, 8, 6, 20, 15, 10] 중위 순회 - 반환되는 값이 오름차순을 이룸 [3, 6, 8, 10, 15, 20] 이진 트리를 예제로 함 너비 우선 탐색 class Node { constructor(value) { this.value = val..

이진 탐색 트리와 이진 힙 비교 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우) 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음 insert 매소드 class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } inser..

직접 구현하면 배열의 인덱스도 덜고 배열에 딸려오는 매서드들도 덜어낼 수 있다. 수 만 개의 요소를 저장하는데 push, pop과 같은 기능만 사용할 거라면 배열을 사용할 이유가 없음 스택 pop의 경우 시간복잡도가 O(N)이므로 shift와 unshift를 사용하는 것이 효율적이다. shift와 unshift의 기능을 수행하지만 편의상 push와 pop으로 만듦. class Node { constructor(val) { this.val = val; this.next = null; } } class Stack { constructor() { this.head = null; this.tail = null; this.length = 0; } push(val) { let newNode = new Node(va..

기본적으로는 단일 연결 리스트와 동일하지만 prev가 있어 탐색에 더 용이하 메모리가 더 많이 먹음 노드 자바스크립트 ver. class Node { constructor(val) { this.val = val; this.prev = null; this.next = null; } } 파이썬 ver. class Node: def __init__(self, data): self.data = data self.prev = None self.next = None push 매소드 만들기 자바스크립트 ver. class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } push(val) { let newN..

노드 = 데이터(value) + 다음 노드 참조 링크(next) 자바스크립트 ver. class Node { constructor(val) { this.val = val; this.next = null; } } 파이썬 ver. class Node: def __init__(self, data): self.data = data self.next = None push 매소드 만들기 자바스크립트 ver. class SinglyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } push(val) { let newNode = new Node(val); if (!this.head) { this.head = newNode..

공간 복잡도 구하기 문제1. function logUpTo(n) { for (var i = 1; i