ASAC 빅데이터 분석가 7기/알고리즘 4

[알고리즘] 완전 탐색

가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 방식의 알고리즘입니다.가장 직관적이고 단순하지만, 계산량이 많아질 수 있기 때문에 입력 크기가 클 경우에는 성능 문제가 발생합니다.✅ 완전 탐색의 기본 개념정의: 문제의 해답을 얻기 위해 모든 경우의 수를 하나하나 확인하는 방식.특징:가장 단순한 방법정확한 해를 보장효율성은 떨어질 수 있음✅ 예시 문제와 접근 방식예시 1: 1~100 사이의 숫자 중에서 어떤 수를 맞추는 게임완전 탐색: 1부터 100까지 전부 시도하면서 정답을 찾는다.예시 2: 주어진 배열에서 두 수의 합이 특정 값이 되는 조합 찾기arr = [1, 2, 3, 4, 5]target = 6for i in range(len(arr)): for j in range(i+1, len(arr..

시간 복잡도(Time Complexity) 기본 이론 정리

시간 복잡도 기본 이론 정리1. 🔎 시간 복잡도란?정의: 알고리즘이 입력 크기 n에 따라 얼마나 많은 연산을 수행하는지를 수학적 함수로 나타낸 것.목적: 프로그램의 실행 시간 예측 및 알고리즘 성능 비교.2. 🧮 표기 방법 (Big-O 표기법)시간 복잡도는 주로 Big-O 표기법으로 표현됩니다.표기 설명 예시 알고리즘O(1)상수 시간배열에서 한 값 읽기O(log n)로그 시간이진 탐색O(n)선형 시간단순 반복문O(n log n)로그-선형 시간병합 정렬, 퀵 정렬 평균O(n²)이차 시간이중 반복문 (버블 정렬)O(2ⁿ)지수 시간피보나치 재귀O(n!)팩토리얼 시간완전 탐색(순열 생성)3. 📌 계산 방법예시 1: 선형 시간for i in range(n): print(i)print는 n번 수행됨 → ..

[알고리즘] 해시(Hash)

해시(Hash) 알고리즘해시 알고리즘은 데이터를 빠르게 검색하고 저장하기 위한 기술로, 키-값 형태의 데이터를 처리합니다. 이 알고리즘은 해시 함수를 통해 임의의 크기의 데이터를 고정된 크기의 해시 값으로 변환합니다.주요 구성 요소해시 함수(Hash Function)해시 함수는 입력된 키를 고정된 크기의 해시 값으로 변환하는 역할을 합니다. 좋은 해시 함수는 충돌을 최소화하고, 입력 데이터의 작은 변경에도 다른 해시 값을 생성해야 합니다.해싱(Hashing)해싱은 키를 해시 값으로 변환하는 과정을 의미합니다. 이 과정에서 키의 원래 순서는 사라집니다.해시 테이블(Hash Table)해시 테이블은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 데이터를 색인합니다. 해시 테이블은 빠른 검색과 삽입,..

[알고리즘] DFS(Depth-First Search) : 깊이 우선 탐색

1. 깊이 우선 탐색 (DFS,Depth-First Search)이란?트리나 그래프를 탐색하는 기법이다.   트리의 경우) 계층적 구조이기 때문에 시작 노드가 주어진다.순환 구조가 없으며, 노드의 방문 순서가 명확하다. 그래프의 경우) 네트워크 구조이기 때문에 노드들이 자유롭게 연결되어 있다.순환 구조가 존재할 수 있다.방향 그래프와 무방향 그래프로 나뉘며 노드의 방문 여부를 체크하지 않으면 무한루프에 빠질 수 있다. 2. DFS 탐색 과정 특징 (트리의 경우)기본적으로 특정 정점을 시작 노드로 설정한 후 각 분기를 따라 탐색을 진행한다.분기가 없는 노드에 도달하게 되면 역추적(backtracking)을 하여 되돌아온다.중간에 탐색하지 않은 노드를 발견하면 우선으로 탐색을 진행한다.모든 노드를 방문한 후..