시간 제한이 1초인 문제를 만났을 때 N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘 설계 N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘 설계 N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘 설계 N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계 수행 시간 측정 소스코드 예제) import time start_time = time.time() # 측정 시작 # 프로그램 소스코드 end_time = time.time() # 측정 종료 print("time:", end_time - start_time) # 수행 시간 출력
Algorithm/개념
신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 크루스칼 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데 대표적인 최소 신장 트리 알고리즘이 '크루스칼 알고리즘'이다. 최소 신장 트리는 일종의 트리 자료구조이므로, 최종적으로 신장 트리에 포함되는 간선의 개수가 '노드의 개수 - 1'과 같다는 특징이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. [알고리즘] 1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 2. 사이클이 발생하는 ..
그래프 vs 트리 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드 없음 루트 노드 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 그래프의 구현 방법 1) 인접 행렬 : 2차원 배열을 이용하는 방식 노드 개수 V, 간선 개수 E인 그래프에서 인접 행렬을 이용할 때는 간선 정보를 저장하기 위해 O(V2)만큼의 메모리 공간이 필요하다. 또한, 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있다. ex : 플로이드 워셜 알고리즘 2) 인접 리스트 : 리스트를 사용하는 방식 노드 개수 V, 간선 개수 E인 그래프에서 인접..
최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 ('길 찾기' 문제) 다양한 유형에 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 '음의 간선(0보다 작은 값을 가지는 간선)'이 없을 때 정상적으로 동작한다. 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘 으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘 -> 기본적으로 그리디 알고리즘으로 분류 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복 원리 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을..
다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 조건) 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션 기법 (캐싱) 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 # 피보나치 수열 소스코드 - 메모이제이션의 예 [탑다운] # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x ==..
이진탐색 : 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 찾는 과정 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서 수행된다. # 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): ..
정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정의 반복. 데이터가 N개일 때, '가장 작은 것을 선택'하는 과정을 N-1번 반복하면 정렬이 완료된다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 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], array[min_index] = array[min_index], array[..
당장 좋은 것만 선택하는 그리디(탐욕법) * 현재 상황에서 지금 당장 좋은 것만 고르는 방법 * 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 예제 1) 거스름돈 문제) 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 문제 해설) '가장 큰 화폐 단위부터' 돈을 거슬러 준다. => 근거 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다. (그리디 알고리즘..
