1. 시간 복잡도란?시간 복잡도란 알고리즘이 실행하는 데, 걸리는 시간을 입력크기에 대한 함수로 나타내는 것이다. 즉, 입력 크기가 증가할때 알고리즘의 실행 시간은 어떻게 변하는 지 분석하는 것이다. 빅오 표기법을 사용하여 최악의 경우를 기준으로 나타내는 것이 일반적이다. 1-1. 상수 시간 - O(1)입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우예시) 배열의 첫 번째 요소를 출력하는 경우def get_first_element(arr): return arr[0] # 항상 한 번만 실행됨 → O(1) 1-2. 선형 시간 - O(N)입력 크기가 n이면 실행 횟수도 n번 증가하는 경우예시) 리스트의 모든 요소를 출력하는 경우def print_all_elements(arr): for ele..
Python/알고리즘 - 이론
1. 함수의 재귀적 호출의 이해1-1. 재귀란?재귀는 어떤 함수가 자기 자신을 다시 호출하는 방식을 의미한다.쉽게 말해서, 어떤 문제를 해결 할 때, 작은 문제로 나누고, 그 작은 문제를 해결하는 방식이 동일하다면 재귀를 사용할 수 있다. 1-2. 재귀 함수의 기본 구조재귀 함수를 작성할 때, 두가지 중요한 요소가 있다.기본 조건무한히 자기 자신을 호출하면 안되니깐, 탈출 조건(종료 조건)이 필요하다.이 조건이 없으면 무한 루프에 빠져서 프로그램이 멈추지 않게 된다. 재귀 호출자기 자신을 호출하는 부분이 필요하다.이때, 문제의 크기를 점점 줄여서 기본 조건에 도달할 수 있도록 만들어야 한다. 1-3. 예제) 펙토리얼 함수팩토리얼은 자연수 n에 대해서 아래와 같이 정의할 수 있다.n != n x (n-1)..
BFS 이론BFS는 너비 우선탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 아래와 같다.탐색 시작 노드를 큐에 삽입하고 방문 처리한다.큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문처리한다.2번의 과정을 수행할 수 없을때 까지 반복한다. 기본 형태from collections import deque# BFS 함수 정의def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True ..
2주차13023번 ABCDE, 12865 평범한 배낭3주차6064번 카잉 달력, 31671번 특별한 오름 등반
이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 동장 예시 이미 정렬된 10개의 데이터 중에서 값을 찾는 방법 시작점, 끝점과 중간점을 설정한다. - 중간 값이 2개일 경우 소수점 이하 제거 중간점을 기준으로 찾는 데이터가 우측에 있는지 좌측에 있는지 구분 만약 좌측에 있다면 시작점은 그대로 내버려두고 현재의 중간점을 끝점으로 수정 수정한 시작점과 끝점을 기준으로 중간점을 다시 설정 이후 중간점 위치의 값이 찾고자하는 데이터가 같아질 때까지 반복 시간복잡도 단계마다..
