1. 그래프 관련해서 이미 배운 내용 정리 - 그래프랑 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다. - 그래프와 트리 비교 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 - 그래프의 구현 방법 : 노드의 개수가 V, 간선의 개수가 E인 그래프일 때 인접 행렬 인접 리스트 방식 2차원 배열을 사용하는 방식 리스트를 사용하는 방식 메모리 공간 O(V^2) O(E) 특정 노드에서 다른 노드로 이어진 간선의 비용을 알기 위한 시간 복잡도 O(1) O(V) 2. 서로소 집합 - 서로소 집..

1. 다익스트라 최단 경로 알고리즘 - 다익스트라 (Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 떄, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. => '음의 간선'이 없을 때 정상적으로 동작한다. => 따라서, 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. - 다익스트라 알고리즘은 일반적으로 그리디 알고리즘으로 분류된다. => 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. (1) 다익스트라 알고리즘의 간략한 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. (모든 값을 무한으로 초기화한다) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른..

1. 다이나믹 프로그래밍을 사용할 수 있는 경우 : 다음 조건을 만족할 때 사용할 수 있다 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 2. 메모이제이션 (Memoization) 기법 - 다이나믹 프로그래밍을 구현하는 방법 중 한 종류이다. - 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 - 캐싱(Caching)이라고도 한다. - 메모이제이션으로 구현한 피보나치 수열 d = [0] * 100 def fibo(x): if x== 1 or x == 2: return 1 if d[x] != 0 : return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x]..

1. 선택 정렬 (Selection Sort) - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸고 .... => 정렬되지 않은 부분에서 가장 작은 것을 선택해서 정렬되지 않은 부분의 가장 앞의 원소와 바꾸는 것 - 시간 복잡도 : O(N^2) def selectionSort(array): for start_index in range(len(array)): minimum_index = start_index for now_index in range(start_index+1, len(array)): if array[now_index] < array[minimum_index]: minimum_index = now_index array[st..

1. 그래프 (1) 인접 행렬 방식 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식 INF = 999999999 graph = [ [0,7,5], #0번 노드는 0번 노드와 거리가 0, 1번 노드와 거리가 7, 2번 노드와 거리가 5 [7,0,INF], #1번 노드는 0번 노드와 거리가 7, 1번 노드와 거리가 0, 2번 노드와 연결되어있지 않음 [5,INF,0] #2번 노드는 0번과 거리가 5, 1번 노드와는 연결되어있지 않음, 2번 노드와 거리가 0 ] - 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨 (2) 인접 리스트 방식 - 리스트로 그래프의 연결 관계를 표현하는 방식 INF = 999999999 graph = [ [(1,7),(2,5)], #0번 노드는 1번 노드..

- 흔히 '피지컬'을 보기 위한 문제라고 여겨지는 것 같다 - 메모리 제약 사항을 고려하자 - '완전 탐색' : 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 사용하면 적절하다 1. 왕실의 나이트 (책 '이것이 코딩 테스트다' 中) 행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 × 8 ..