전체 글
[Algorithm] 최단경로 알고리즘 - 다익스트라, 플로이드 워셜 (Python)
Shortest Path 가장 짧은 경로를 찾는 알고리즘 대표적인 최단 거리 알고리즘으로는 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있다. 최단 경로 문제의 종류 단일 출발(single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제 단일 도착(single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제 그래프 내의 간선들을 뒤집으면 단일 출발 최단 거리 문제가 된다. 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 Dijkstra 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리..
[Algorithm] Binary Search
Binary Search Sequential Search 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i + 1 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 하므로 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하다. 따라서 순차 탐색의 시간 복잡도는 \(O(N)\)이다. Binary Search 이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있으며, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. 시작점 끝점 중간점 이진 탐색은 위치를 나타내는 ..
[Algorithm] Sorting - 버블, 선택, 삽입, 병합, 퀵 정렬 (Python)
정렬 데이터를 특정한 기준에 따라 순서대로 나열 Bubble Sort 인접한 두 데이터를 비교하여 작은 데이터는 앞쪽, 큰 데이터는 뒤쪽으로 보낸다. (swap) 앞에서부터 시작하여 맨 뒤에 가장 큰 값을 보내고 두 번째로 큰 값을 뒤에서 두 번째로 보내는 과정을 반복하여 정렬한다. \(O(N^2)\)의 시간 복잡도를 갖는다. 최선의 경우에는 시간 복잡도를 \(O(N)\)까지 줄일 수 있다. def bubble_sort(arr): for i in range(len(arr) - 1): for j in range(len(arr) - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr Selection Sort 가..
[Algorithm] DFS & BFS
DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 DFS와 BFS를 공부하기 전, 먼저 스택과 큐, 재귀함수에 대한 이해가 필요하다. 스택 (Stack) FILO (First In, Last Out) 먼저 들어온 데이터가 나중에 나가는 선입후출의 구조 Python에서 스택을 사용할 경우에는 별도의 라이브러리가 필요하지 않다. 기본 리스트에서 append()와 pop() 메서드를 사용하면 스택 자료구조와 동일하게 동작한다. append() : 리스트의 가장 뒤쪽에 데이터 삽입 pop() : 리스트의 가장 뒤쪽에서 데이터를 삭제하고 리턴 큐 (Queue) FIFO (First In, First Out) 먼저 들어온 데이터가 먼저 나가는 선입선출..
[Algorithm] Greedy
Greedy 알고리즘 그리디(Greedy) 알고리즘은 Greedy(탐욕스러운)라는 이름 그대로 선택의 순간마다 현재 상황에서 가장 최적이라고 생각하는 해를 선택하는 방법이다. 그리디 알고리즘은 국소 최적해(locally optimal solution)를 찾음으로써 최종적으로 전역 최적해(global optimal solution)를 구하는 방법으로, 현재의 선택이 앞으로 끼칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 최적해를 보장하지 않기 때문에 특수한 조건에서 사용된다. 그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있는 경우, 그리디는 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 그리디 알고리즘 문제에서는 문제 해결을 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토..
![[Java] Collection](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbveHZZ%2FbtrVjmIjJ3l%2Fr145XDJYNi5dmU2mTlugY0%2Fimg.png)
[Java] Collection
Collection 데이터의 집합, 그룹 Java에서 모든 컬렉션 클래스와 인터페이스를 포함하는 Collection Framework라는 개념이 JDK1.2에서 정의되었다. Collection 인터페이스(java.util.Collection)와 Map 인터페이스(java.util.Map)는 자바 컬렉션 클래스의 주요 루트 인터페이스이다.
[Algorithm] Prime number - 에라토스테네스의 체
Prime Number 소수(Prime number)란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 정수론의 기본 정리에 따라, 모든 자연수는 단 한 가지 방법의 소수의 곱으로 표현할 수 있다. 소수 찾기 어떤 정수 n이 소수인지 판별하는 방법에는 여러 가지가 있다. 먼저 소수의 정의에 따라 2부터 n-1까지 모든 수로 나누었을 때 나누어 떨어지는 수가 없다면 n은 소수이다. def isPrime(n): for i in range(2, n): if n % i == 0: return False return True 하지만 위의 경우 n-1까지 모든 수를 확인해야하므로 시간 복잡도가 \( O(n) \)이 된다. 연산의 횟수를 줄이기 위해 \( n/2 \)까지의 숫자만 확인하는 방법도 있지..
[CS231n] 강의 정리
CS231n Convolutional Neural Networks for Visual Recognition Notion 정리 CS231n Stanford의 [CS231n: Convolutional Neural Networks for Visual Recognition] 을 기반으로 한 인공지능응용 강의를 듣고 정리한 내용입니다. flossy-vulcanodon-74c.notion.site CS231n (Spring 2021) Assignment https://cs231n.github.io/