코딩테스트 준비4 220109 최단 경로 알고리즘 개념 최단 경로 알고리즘 개념 가장 빠른 길찾기 최단 경로 Shortest path 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 "길 찾기" 문제 라고도 한다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어있다. '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등이 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고있다면 문제를 좀 더 쉽게 풀 수 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데, 각 지점은 그래프에서 '노드'*로 표현되고, 지점간 연결된 *도로는 '간선' 으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로.. 2022. 1. 16. 211227 다이나믹 프로그래밍 다이나믹 프로그래밍 피보나치 수열 피보나치 수열 구하는 과정 메모이제이션 (Memoization) 기법 결론 다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 중복되는 연산 줄이기 프로그래밍에서 다이나믹 이란, '프로그램이 실행되는 도중에' 라는 의미이다. 자료구조에서 동적 할당(Dynamic Allocation) 은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다. 그러나 '다이나믹 프로그램' 에서는 이런 의미는 아니라는 것을 기억하자. 피보나치 수열 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 $n$ 번째 피보나치 수 = $(n - 1)$ 번째 피보나치 수 + $(n - 2)$ 번째 피보나치 수 단, 1 번째.. 2022. 1. 16. 211221 이진탐색 개념 이진탐색 순차 탐색 이진탐색 : 반으로 쪼개면서 탐색하기 트리 자료구조 이진 탐색 트리 이진탐색 리스트 내에서 탐색 범위를 반으로 좁혀가며 데이터를 빠르게 탐색하는 알고리즘 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 (일반적인 탐색) # 순차탐색 코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환 (인덱스 0 부터 시작하므로 1 더하기) print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열 입.. 2022. 1. 16. 211208 정렬 개념 정렬 (Sorting) 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 파이썬의 정렬 라이브러리 (sorted, sort) 정렬 (Sorting) 참고할만한 사이트 :: https://im-developer.tistory.com/133 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary) 이 가능해진다. 보통 정렬을 공부하면 '알고리즘의 효율성' 을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을 설명하는 경우가 많다. 정렬 알고리즘을 공.. 2022. 1. 16. 이전 1 다음
