SK_MOUSE 개발일기

우선 쌍방향(무방향) 그래프에 대해 알아보겠다. 1) ArrayList안에 ArrayList할당 그래프는 ArrayList중첩으로 표현이 가능하다. 그림으로는 아래에서 그림을 참고하면되고, 코드는 이런식이다. ArrayList graph; graph = new ArrayList(); for (int i = 0; i 안쪽ArrayList Index=수신자 무방향그래프인경우 이렇게 서로 화살표가 가게끔, 이..

백트래킹과 완전탐색에 대하여 헷갈려서 비교해보았다. 백트래킹의 대표적인 요소 DFS, BFS. 백준15649번: N과 M(1) www.acmicpc.net/problem/15649 DFS로 풀이한 방식이다. import java.io.IOException; import java.util.Scanner; class Main { static int n, m; static int[] arr = new int[9]; static boolean[] visited = new boolean[9]; public static void main(String[] args) throws IOException { //input Scanner scanner = new Scanner(System.in); n = scanner.ne..

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. DynamicProgramming 기술에 의거한다. "거쳐가는 정점"을 기준으로 최단거리를 구한다. 코드는 단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 구현에 있어 크게 어려운 부분은 없다. 단, 유의하여야 할 점은 for문에서 가운데 노드(m)이 제일 위에 있어야 한다는 점이다. 시간복잡도는 O(V^3)O(V3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다. 1을 거쳐가는 경우를 갱신한다 하면 => D[2,3] 과 ( D[2,1] + D[1,3] ) 을 비교하여 최솟값으로 업..

先요약 일반적인 그래프를 구성할때는 싸이클이 있는지를 확인한다 : findParent 메소드 이용 두개의 노드를 간선으로 잇는 작업은 unionParent 메소드를 이용한다. 신장트리는 싸이클이 없어야하며, 모든 노드가 연결되어있어야한다 : 크루스칼 알고리즘으로 만든다. 위상정렬은 싸이클이 없고 방향그래프(DAG)인 상황에, 방향성에 거스르지 않도록 순서대로 나열하는 것. 그래프의 기본적인 이론에 대하여 알아보겠다. 아래의 메소드는 그래프 문제를 풀때 구현해놓으면 좋은 메소드이다. 1. findParent(int x) 메소드 : 루트노드가 아니라면, 해당 루트 노드를 찾을때까지 재귀적으로 findParent메소드 재귀호출. ex) findParent(3번노드) -> 재귀 findParent(2번노드) -..

1. DFS(Depth-First Search) : 깊이 우선탐색 =>전체적으로 재귀형식이다. 예제 코드 참고. 큐에 넣어서 구현하는 방식. 최상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 방문(번호 낮은 인접노드부터) 그다음은 8. 돌아가서 3-4-5 탐색순서 : 1-2-7-6-8-3-4-5 순으로 깊게 들어가는것을 우선으로 한다. DFS 소스코드 예제 인접한노드를 for문으로 낮은 인덱스값부터 검사하여 인접하면 방문(dfs재귀) 2. BFS(Breadth-First Search) : 너비우선탐색 큐에 넣어서 구현 인접노드중에서 방문하지 않은 노드를 모두 큐에 넣어서(낮은 인덱스부터) 하나씩 뽑으면서 방문하며 방문하지않은 노드를 큐에 계속 넣는다. 그리고 3을꺼내서 4와 5를 큐에 넣는다..

재귀함수형태로 점화식이 생기는 문제에서 일대일함수임이 만족될때 각 함수의 파라미터를 키로 결과를 캐싱하는걸 dp라함 이때 캐싱하는 자료구조를 편의상 상태공간이라 부르는데 별 의미는 없고 동적계획법(Dynamic programming)은 자료구조에서 동적할당(Dynamic Allocation)과는 다르다. 알고리즘에서 사용되는 "다이나믹(Dynamic)"은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍 문제인지 확인하려면 아래 조건을 만족하는지 확인하면 된다. 1. 최적 부분구조(Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은..

Greedy 계획법과 Dynamic 계획법에 대해 알아보자. 예시 당신은 출발지A에서 도착지B로 가려고 한다. A에서 B로 가는 방법은 2가지가 있다. 출발하기전 신호등, 교통상황, 대중교통, 가는거리를 모두 알아보고 가는방법과, 일단 출발해서 그때 그때 상황에 따라서 가장 빠른 방법으로 앞으로 나아가는 방법이 있다. 전자의 경우를 동적계획법, 후자의 경우를 탐욕법 장단점 동적 계획법의 경우, 점화식을 이용하여 모든 상황을 계산하기 때문에 최적의 경로를 구할 수 있다. 하지만, 그만큼 계산하는데 오랜 시간이 걸린다는 단점이 있다. 탐욕법의 경우, 각 단계에서 최적의 상황만을 선택하기 때문에, 빠르게 문제 해결이 가능하다. 하지만, 모든 경우를 살펴보지 않기 때문에 최적이 아닌경우가 있거나, 혹은 풀리지 ..