1. 최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 - 유형 : 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 2. 다익스트라 (Dijkstra) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - 조건 : 음의 간선이 없을 때 정상 작동 1 출발 노드를 설정 2 최단 거리 테이블을 초기화 3 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 5 3, 4번의 과정을 반복 2-1. 간단한 다익스트라 알고리즘 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언 후 단계마다 '방문하지 않은 노드 중..
1. 다이나믹 프로그래밍 (Dynamic Programming, 동적 계획법) - 조건 ㄴ 큰 문제를 작은 문제로 나눌 수 있다. ㄴ 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. Top-Down 방식 : 큰 문제를 해결하기 위해 작은 문제를 호출 Bottom-Up 방식 : 작은 문체부터 답을 도출 2. 메모이제이션 (Memoization) or 캐싱 (Caching) 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 📌 파보나치 수열 코드 - 재귀적 + 메모이제이션 - 탑다운 #한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 파보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) d..
1. 순차 탐색 (Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용 - 시간 복잡도 ≤ O(N) 📌 순차 탐색 코드 def sequential_serch(n, target, array) : #각 원소를 하나씩 확인하여 for i in range(n): #현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target : return i+1 #현재의 위치반환 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(input_data[0]) #원소의 개수 ..
1. 정렬 (Sorting) - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 1-1. 선택 정렬 (Selection Sort) - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복 (가장 작은 것을 선택) - 시간 복잡도 : O(N^2) 👎 📌 선택 정렬 예제 array = [7,4,9,0,3,1] for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스 for j in range(i+1,len(array)): if array[min_index] > array[j]: min_index = j #더 작으면 교체 array[i..
1. 자료구초 기초 탐색 (search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 대표적인 탐색 알고리즘 : DFS, BFS 자료구조 (data structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조 스택 (stack) - 선입후출 (First In Last Out) 또는 후입선출 (Last In First Out) 구조 ex) 상자 쌓기 큐 (queue) - 선입선출 (First In First Out) 구조 ex) 대기 줄 - 큐를 구현할 때는 collections 모듈에서 deque 자료구조를 활용 - deque는 스택과 큐의 장점을 모두 채택하여 데이터 삭입/삭제 속도가 리스트 자료형에 비해 효율적 📌 deque 구현 예제 from collections import..
1. Implementation (구현) 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 구현유형 완전탐색 ; 모든 경우의 수를 주저 없이 다 계산하는 해결방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차레대로 직접 수행 2. 상하좌우 / 왕실의 나이트 이동 유형이 구분되는 경우 'dx, dy 리스트' 또는 'steps' 변수를 선언하여 이동할 방향을 기록 행과 열의 형태가 정수형이 아닐 경우 등의 예외 처리에 대비 必 # dx, dy 리스트 dx = [0,0,-1,1] dy = [-1,1,0,0] move_types=['L','R','U','D'] # steps 리스트 steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)] # 행..
1. Greey Algorithm (그리디 알고리즘) 현재 상황에서 당장 좋은 것만 고르는 방법 기준에 따라 좋은 것을 선택 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시 그리디 알고리즘의 정당성 문제풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출 가능 그리디 알고리즘으로 해결할 수 없을 경우 → 다이나믹 프로그래밍, 그래프 알고리즘 2. 큰 수의 법칙 N개의 숫자로 이루어진 배열을 사용하여 숫자를 M번 더하여 가장 큰 수 만들기 가장 큰 수와 두번째로 큰 수만 저장 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복 N = 배열의 크기 M = 숫자가 더해지는 회수 K = 특정한 인덱스에 해당하는 수가 연속해서 k번 초과하여 더해질 ..
1. 복잡도 (complexity) 알고리즘의 성능을 나타내는 척도 (1) 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는가 알고리즘을 위해 필요한 연산의 횟수 (2) 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는가 알고리즘을 위해 필요한 메모리의 양 (3) 빅오(Big-O) 표기법 가장 빠르게 증가하는 항만을 고려하는 표기법 Big-O 표기법 명칭 속도 O(1) 상수 시간 ↑ 빠름 ↓ 느림 O(logN) 로그 시간 O(N) 선형 시간 O(NlogN) 로그 선형 시간 O(N^2) 이차 시간 O(N^3) 삼차 시간 O(2^N) 지수 시간 2. 시간 측정 수행 시간 측정 코드 import time start_time = time.time(..
