그냥 개발블로그에요

알아보기 큰 문제를 직관적으로 이해할 수 있는 작은 문제로 바꾸어서 소형화시킴. 작은 문제의 답을 메모이제이션, 그렇게 점점 큰 문제로 확장시켜 나간다. 사용 예시 예를 들어 계단오르기 문제가 그렇다. 계단을 오를때 한번에 한 계단 또는 두 계단씩 올라갈 수 있을 때, 총 7 계단을 올라간다면 그 방법의 수를 구해보자. 차근차근 처음부터 알 수 있는 것부터 따져보자. 먼저 첫번째 계단을 올라가는 방법은 한가지다. 두번째 계단을 올라가는 방법은 한칸+한칸, 두칸으로 두가지다. 세번째 계단을 올라가는 방법은, 두번째 계단에서 올라갈때와 첫번째 계단에서 올라갈때 경우로 나눠진다. 첫번째 계단으로 가는 방법은 한가지였고, 두번째 계단으로 가는 방법은 두가지였으므로, 세번째 계단으로 가는 방법은 세가지이다. 그렇..

알아보기 Greedy는 탐욕스러운 이라는 뜻이다. 선택의 순간마다 당장 제일 좋아보이는 경우를 선택한다. 여러 경우 중에 하나를 선택해야할 때, 그 순간 최적이라고 생각하는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 그 순간 선택한 결정은 지역적으로는 최적이지만, 전역적인(최종적인) 해답이 최적이라는 보장은 없다. 따라서 그리디 알고리즘을 적용하려면, 지역적으로 최적이면서 전역적으로 최적이어야 한다. 조건 Greedy choice property - 탐욕적 선택 속성 - 앞의 선택이 이후의 선택에 영향을 주지 않는다. optimal substructure - 최적 부분 구조 - 문제에 대한 최종 해결법은 부분 문제에 대한 최적해이다. 이러한 조건이 성립하지 않을때에도, 근사 알고리즘..

알아보기 다익스트라 알고리즘은 가중치 그래프에서 가중치의 값이 모두 양수일 때 한 노드에서 각 노드까지의 최소거리를 구할때 사용한다. 기본적으로 그리디과 다이나믹을 사용한다. 방문한 노드들을 체크하여, 체크하지 않은 노드들 중 가장 비용이 적은 노드를 선택(그리디)하고, 그 비용과 기존의 비용을 비교하여 값을 갱신(프로그래밍)하는 방식이다. 적용해보기 위의 그래프를 이용하여 1번 노드에서 각 노드까지의 최소비용 구해보도록 하자. 각 노드로 가는 최소 비용을 담는 배열 dis을 생성한다. 그 값들은 최대값으로 일단 해놓고, 1번정점을 0으로 한 뒤 시작한다. 배열 값 중 0의 값이 최소이므로 체크해 놓고, 1번노드에서 바로 갈 수 있는 노드에 대한 비용을 각 노드가 가진 현재 값과 비교하여 더 작다면 바꾼..

알아보기 Breadth-First Search 너비 우선 탐색이다. 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. BFS 는 재귀적으로 동작하지 않는다. 위의 그림에서도 볼 수 있듯이, 같은 레벨에 있는 노드들을 방문한 뒤 다음 레벨의 노드들을 방문하는 방식이다. 노드들은 큐에 집어넣어, 레벨이 바뀌면 뺀다. 이 과정은 아래의 그림을 통해 이해해 볼 수 있다. 적용하기 미로의 최단거리, 그래프 최단거리등 최단거리를 구하고자 할 때 사용된다. 말단 노드까지의 가장 짧은 경로를 구해보자. import java.util.LinkedList; import java.util.Queue; class Node{ int data; Node2 lt, rt; public Node2(int val){ da..

알아보기 Depth-First Search 깊이 우선 탐색이다. 임의의 노드에서 시작하여 다음 분기로 넘어가기 전까지 해당 분기를 끝까지 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 쭉 가다가(깊이) 갈 수 없는 상황이 되면, 그 전 노드로 돌아와(**백트래킹**) 인접한 다른 노드를 탐색하고, 그 노드 아래에 있는 노드들을 쭈욱 탐색하는 경우가 dfs를 사용하는 예라고 볼 수 있다. 따라서, 어떤 노드를 방문했었는지 반드시 체크하여 검사를 해야한다. 그렇지 않으면 무한 루프에 빠질 수도 있다. 적용하기 미로 탐색뿐만아니라, 순열, 중복순열,조합,메모이제이션에서도 응용이 가능하다. 순열 예를 들어 1~N까지의 자연수 중 M개를 뽑아 일렬로 나열하는 경우의 수가 순열이다. N=3, M=2이라고 가정하..

알아보기 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정점은 노드, 간선은 노드를 연결하는 선으로 생각하면 된다. 그렇다고 해서 노드 간 부모 자식이라는 관계는 존재하지 않고 그냥 연결관계만 나타낸다. Tree와 비슷하지만, 그래프는 간선이 없는 노드도 존재한다는 점에서 차이를 나타낸다. 탐색방법 그래프 탐색이란 하나의 정점으로 부터 모든 정점들을 한번씩 방문하는 행위를 뜻한다. 예를 들어 섬끼리 이동할 수 있을지, 이동할 수 있다면 시간이 얼마나 걸리는지 등의 예시에서 사용될 수 있다. 어떤식으로 방문해야 할까? 여기서 두가지 방법이 있다. DFS 깊이 우선 탐색 BFS 너비 우선 탐색 구현 인접 행렬과 인접리스트 방식으로 구현할 수 있다. 인접행렬 2차원 배열 안에 모든 정점들의 ..