earthssu 개발 공부

다익스트라(dijkstra) 알고리즘은 '최단 경로'를 찾을 때 유용하게 쓰인다. 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이라고 할 수 있다. 알고리즘의 아이디어 1. 출발 노드와 도착 노드를 설정한다. 2. 알고 있는 모든 거리값을 부여한다. 3. 출발 노드부터 시작하여 방문하지 않은 인접 노드를 방문하여 둘 사이의 거리를 계산한다. 이때 이미 알고 있는 거리보다 짧으면 해당 거리를 갱신한다. 4. 현재 노드에 인접한 모든 노드를 방문했다면 해당 노드는 모든 방문을 끝낸 것이므로 미방문 노드에서 없앤다. 5. 모든 미방문 노드를 방문했다면 알고리즘을 종료한다. 해당 알고리즘은 파이썬에서 heap을 이용해 구현할 수 있다. 보통 최소 힙으로 정렬이 되기 때문에 최단 경로를 찾을 때 유..

python에는 너무 유용한 내장 함수가 많이 있는데, 그 중에서도 경우의 수를 구할 때 사용되는 내장 함수를 다뤄보겠다. 경우의 수는 전체 탐색이 필요한 알고리즘 문제에서 은근 자주 쓰이므로 기억해둘 것! 경우의 수를 구할 땐 itertools라는 모듈을 활용한다. import itertools 순열 서로 다른 n개 중에서 r개를 '순서'대로 나열하는 경우의 수 # 배열 ['1','2','3','4'] 중에서 서로 다른 원소 두 개를 순서대로 나열하는 경우의 수를 출력한다. itertools.permutations(['1','2','3','4'], 2) 중복순열 중복 가능한 n개 중에서 r개를 '순서'대로 나열하는 경우의 수 # 배열 ['1','2','3','4'] 에서 중복 가능한 원소 두 개를 순서..

배울 때마다 헷갈리고 이해되지 않던 우선 탐색들... 오늘 드디어 완전히 이해 완료했다 생각보다 간단한 원리로 제작! 그래프로 문제를 해결할 때 어떤 방식으로 해결해야 적절한지에 따라 갈린다. 알고리즘에 큰 차이는 없다! 너비 우선 탐색 (Breadth First Seartch) 말 그대로 '너비를 우선적으로 탐색하는 알고리즘'이다. 즉, 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문한다고 생각하면 쉽다. '큐(queue)'를 사용하는 것이 이 알고리즘의 핵심! 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 '먼저 큐에 들어있던 순서대로' 노드를 방문하면 된다. 이때, python 라이브러리 중 deque 를 사용하면 시간을 절약할 수 있다. 코드 from co..

여러 노드(또는 정점, vertex) 들이 간선(edge, 또는 arc)으로 연걸된 추상 네트워크 이를 수식으로 표현하면, G는 그래프, V는 노드의 집합이고 E는 간선의 집합이다. 이와 같은 그래프에서 V는 {a, b, c, d} , E는 {{a, b}, {b, c}, {c, d}, {d, a}} 이다. 그래프의 종류 무방향 그래프 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있다. 보통 노드 A, B가 연결되어 있을 경우 (A, B) 또는 (B, A)로 표기 방향 그래프 간선에 방향이 있는 그래프 보통 노드 A, B가 A -> B 방향일 경우, 로 표기 가중치 그래프 (네트워크) 간선에 비용 또는 가중치가 할당된 그래프 연결 그래프 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재..

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 동적 계획법은 부분 문제를 풀고 결과를 저장한 후, 다음 부분 문제를 푸는 과정에서 저장된 결과를 사용한다. 그렇기 때문에 문제가 '최적 부분 구조'와 '중복되는 부분 문제'를 갖고 있다면 동적 계획법으로 해결이 가능하다 최적 부분 구조 : 답을 구하기 위해서 했던 계산을 반복해야 하는 문제의 구조 상향식 접근을 사용하는 것이 중요! 메모이제이션 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거해 프로그램의 실행 속도를 빠르게 하는 기법이다. 예제 - 최장 증가 부분열 주어진 리스트에서 '최장 증가 부분열'을 찾아보자. 최장 증가 부분열이란, 증가하는 순서대로 숫자를 고른 부분열의 길이가 최대..