데이터사이언스 기록기📚

1. 가장 빠른 길 찾기 가장 빠르게 도달하는 방법 - 최단경로(Shortest Path): 가장 짧은 경로 찾는 길 찾기 문제 - 문제 보통 그래프 이용하여 표현 (지점 - 노드, 지점 간 연결된 도로 - 간선) 코테 : 최단 거리 출력 >> 최단 경로 출력 - 최단 거리 알고리즘 최단 거리 = 그리디 + 다이나믹 프로그래밍 종류 : 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 - 다익스트라(Dijkstra) : 특정한 노드 출발 → 다른 노드로 가는 각각의 최단 경로를 구함 음의 간선(0보다 작은값)이 없을 때 정상적으로 동작 그리디 알고리즘으로 분류 (가장 비용이 적은 노드 선택하여 임의의 과정 반복) - 원리 방문하지 않은 노드 중에서 가장 최..

1. 다이나믹 프로그래밍 중복되는 연산을 줄이자 - 컴퓨터를 활용해도 해결하기 어려운 문제 최적의 해를 구하기에 시간이 매우 많이 필요 (연산 속도의 한계) 메모리 공간이 매우 많이 필요한 문제 (메모리 공간을 사용할 수 있는 데이터 개수 한정) → 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성 - 다이나믹 프로그래밍 / 동적 계획법(Dynamic Programming) 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 - 예시) 피보나치 수열 : 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 점화식 - 인접한 항들 사이의 관계식, 점화식으로 수열의 항이 이어지는 형태 간결하게 표현. 프로그래밍에서 피보나치 수열을 배열, 리스트로 표..

1. 범위를 반씩 좁혀가는 탐색 순차 탐색 - 이진 탐색 알고리즘 : 리스트 내에서 데이터를 매우 빠르게 탐색 - 순차 탐색(Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 정렬되지 않은 리스트에서 데이터 찾아야 할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 항상 원하는 데이터를 찾을 수 있다. - 사용되는 예시 리스트에 특정 값의 원소가 있는지 체크 리스트 자료형에서 특정한 값을 가지는 원소의 개수 세는 count() 메서드 이용 - 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in r..

1. 기준에 따라 데이터를 정렬 정렬 알고리즘 개요 - 정렬(Sorting) : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것. 정렬 알고리즘 특징 : 이진 탐색의 전처리 과정 정렬 알고리즘 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 알고리즘의 효율성 이해할 수 있음(상황에 적절하지 못한 알고리즘 사용 → 비효율적 동작) 더보기 리스트를 뒤집는 연산 : O(N)의 시간복잡도 선택 정렬 - 선택 정렬(Selection Sort) : 매번 가장 작은 것을 선택 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택하여 맨 앞 데이터와 바꿈. 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복. - 예제 가장 작은 데이터를 앞으로 보내는 과정 N - 1..