모-코드

DFS & BFSBFS와 DFS 정리BFS (너비 우선 탐색)탐색 순서만 구할 때목적: 그래프의 모든 노드를 방문하거나, 특정 노드를 찾고자 할 때.특징: 시작 노드에서 가까운 노드부터 차례대로 방문합니다. 큐(Queue)를 사용하여 구현하며, 레벨별로 탐색합니다.구현:from collections import dequedef bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=' ') for neighbor in graph[vertex]: i..

Hash Table 탄생 배경 Direct Access Table 인 배열인덱스 방식으로, key-value쌍을 가져올 때 시간효율은 O(1)이므로 빠르다. 하지만 사용하지 않는 index에 대한 공간낭비가 상존함 1. 해시 함수의 조건 (1) 의의 특정 값을 원하는 범위의 자연수로 바꿔주는 함수 (2) 조건 1) 한 해시테이블의 해시 함수는 결정론적이어야 한다 같은 key 는 같은 결과가 나와야함 2) 결과 해시값이 치우치지 않고 고르게 나온다 각 리턴 값이 나올 확률이 비슷해야한다 3) 빠르게 계산 할 수있어야한다. 해시테이블은 연산할 때 마다 해시함수 사용함. 본 함수가 비효율적이면 해시테이블도 비효율적임 2. 해시함수 만들기 (1) 나누기 방법 자연수 key를 해시테이블의 크기로 나눈 나머지를 리..

Dynamic Programming - Memoization 정리 핵심개념 피보나치 수열의 동적 프로그래밍과 메모이제이션 방식의 핵심은 중복 계산을 방지하기 위해 캐시를 사용하여 이미 계산된 값을 저장하고 재사용함으로써, 재귀 호출의 효율성을 높이고 시간 복잡도를 지수적인 O(2^n) 에서 선형적인 O(n)으로 줄이는 데에 있습니다. 기저 사례를 적절히 처리하여 재귀 호출의 종료 조건을 제공하며, 이를 통해 계산 속도를 크게 향상시킵니다.

Divid and Conquer 의 형제 합병정렬 정리 핵심개념: 리스트를 반으로 나누고, 각 부분을 재귀적으로 정렬한 다음, 두 부분을 합병합니다. 시간복잡도: 최선, 평균, 최악 모두 O(nlogn) → + : 일관된 시간복잡도 공간복잡도: O(n) (추가 배열을 사용하기 때문에) → - : 추가 메모리 필요 퀵정렬 정리 핵심개념: 피벗을 선택하여 이보다 작은 요소와 큰 요소를 분할한 후(파티션), 각 부분을 재귀적으로 정렬합니다. 시간복잡도: 평균 O(nlogn), 최악 O(n2) (피벗 선택에 따라 달라짐) → + 평균적으로 빠름, 최악 크게 증가 공간복잡도: 평균 O(logn) (재귀의 깊이), 최악의 경우 O(n) (피벗 선택이 최악일 때) → + 추가 메모리 적게 소모 이름이 퀵정렬인 이유 ..

I. 들어가며 모든 알고리즘은 사실 완전탐색(DFS, BFS)를 이용해서 정답을 도출할 수 있다 그럼에도 불구하고 알고리즘 기법이 탄생한 이유는 비효율적인 연산과 시간을 없애고 답을 효율적으로 도출하기 위함이다. 동적계획법(이하 'DP')은 가장 다양한 유형의 문제들을 논리적 사고로 효율적으로 풀 수 있는 알고리즘이다. II. 동적계획법 알아보기 1. 정의 동적계획법(Dynamic programming : DP) 는 1) 복잡한 여러문제를 간단한 문제로 분리하여 2) 부분의 문제를 해결함으로써 3) 최종적으로 복잡한 문제의 답을 구하는 방법을 의미한다. 2. 핵심이론 (1) 원리와 구현방식 [예 : 피보나치 수열] 1) 큰 문제를 작은문제로 나눌 수 있어야한다 (분리) [6번 수열 구하는 문제는 5번과 ..

I. 그리디알고리즘 정의 그리디 알고리즘은 '현재 상태에서 볼 수있는 선택지' 중 '최선의 선택'을 하는 알고리즘이다 (전체 선택지 중 항상 최적해를 구하지 못하는것이 한계이다. 그래서 선택시 늘 유의해야한다 인공신경망 구성시 local minimum과 global minimum 차이에서 최적해 문제를 이해하기 수월 할 수있다 II. 그리디 이론 1. 들어가며 3단계를 반복하면서 해결한다 2. 수행과정 (1) 해선택 현재 상태에서 가장 최선이라고 생각하는 해를 선택한다 (부분의 best) (2) 적절성 검사 현재 선택한 해가 전체문제 '제약조건'에서 벗어나지 않는지 검사 (3) 해 검사 현재 선택한 해 집합이 '전체 문제 해결'할 수 있는지 검사한다. 전체문제를 해결할 수 없다면 처음으로 돌아가 반복한다..

I. 탐색 탐색이란 '주어진 데이터'에서 '자신이 원하는 데이터'를 찾아내는 알고리즘이다. 탐색은 주어진 데이터의 성질(정렬, 비정렬 데이터)따라 탐색알고리즘을 채택하는것이 중요하다 탐색은 그래프를 탐색하기 때문에 선수공부로서 그래프 표현에 대해서 공부가 필요하다 II. 이진탐색 이론 1. 들어가며 (1) 정의 1) 이진탐색이란 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다 데이터 정렬 -> 데이터의 중간값에서 찾고자 하는 값 비교 -> 데이터 크기 반으로 줄이기 2) 특징 타깃 데이터 탐색 3) 시간복잡도 O(log N) 의 시간복잡도를 가진다. 4) 응용문제 (2) 핵심이론 오름차순으로 정렬된 데이터를 이용한다. (내림차순이면 조건을 반대로 한다) N개의 데이터에 대해서 O(nog..

I. 탐색 탐색이란 '주어진 데이터'에서 '자신이 원하는 데이터'를 찾아내는 알고리즘이다. 탐색은 주어진 데이터의 성질(정렬, 비정렬 데이터)따라 탐색알고리즘을 채택하는것이 중요하다 탐색은 그래프를 탐색하기 때문에 선수공부로서 그래프 표현에 대해서 공부가 필요하다 II. 너비 우선 탐색(BFS : breadth - first serach) 이론 1. 들어가며 가장가까운 노드부터 우선하는 점이 BFS과 비교가 된다. (1) 정의 1) DFS란 그래프 완전탐색기법 중 하나이다. 그래프의 시작노드(a)에서 출발 -> 시작노드와 가까운 노드(b) 먼저 방문 -> 시작노드와 가까운 다른노드(c) 방문 -> b노드와 가까운 노드(d) 방문 -> 반복 이러한 연유로 목표노드에 도착하는 경로가 여러개일 때 '최단경로'..

I. 탐색 탐색이란 '주어진 데이터'에서 '자신이 원하는 데이터'를 찾아내는 알고리즘이다. 탐색은 주어진 데이터의 성질(정렬, 비정렬 데이터)따라 탐색알고리즘을 채택하는것이 중요하다 탐색은 그래프를 탐색하기 때문에 선수공부로서 그래프표현에 대해서 공부가 필요하다 II. 깊이 우선 탐색(DFS : depth-first serach) 이론 1. 들어가며 한쪽 분기를 지정해서 최대깊이까지 탐색하는것과 다른방식인 BFS과 비교가 된다. (1) 정의 1) DFS란 그래프 완전탐색기법 중 하나이다. 그래프의 시작노드에서 출발 -> 탐색할 한쪽 분기 지정 -> 해당 분기 최대 깊이까지 탐색, -> 탐색할 다른쪽 분기 지정 -> 해당 분기 최대 깊이까지 탐색 2) 특징 두가지 방식으로 구현이 가능하다 재귀함수(이경우 ..