다이나믹 프로그래밍은 쉽게 말해 점화식이용하는 알고리즘이다. 점화식을 구하는 방법은 2가지가 있는데 탑다운 방식과 보텀업 방식이 있다. 탑다운 : -> 큰 문제를 해결하기 위해 작은 문제를 호출 한다. public class Top_Down { static long d[] = new long[100]; static long fibo(int x) { System.out.print("f(" + x + ')' + " "); if (x == 1 || x == 2) { return 1; } if (d[x] != 0) { return d[x]; } d[x] = fibo(x-1) + fibo(x-2); return d[x]; } public static void main(String[] args) { System.o..
확실히 다익스트라 알고리즘에 비하면 쉽긴하다. 다익스트라가 음수는 되지 않는다는 문제점이 있었는데 이걸로 사용하면 될것 같다, 플로이드 워셜의 핵심 코드는 for(int k = 1; k
static void dijkstra(int start) { Queue q = new PriorityQueue(); q.offer(new Node(start,0)); distance[start] = 0; while(!q.isEmpty()) { Node shortest = q.poll(); int dist = shortest.distance; int now = shortest.index; if (distance[now] < dist) { continue; } for(int i = 0; i
우선순위 큐는 일반적인 큐와 달리 철저히 우선순위에 의해 동작한다. 우선순위를 설정하는 방법은 여러가지가 있다. 간단하게 우선순위를 정할 경우, 리스트를 이용해도 된다. List list = new ArrayList(); Collections.sort(list); 이런식으로 작성하면 리스트로 우선순위 큐를 만들 수 도 있다. 하지만 리스트로 이용할시, 많은 시간이 발생한다. 그래서 리스트보다는 힙 자료구조를 이용해서 우선순위 큐를 이용한다. 즉, 이름은 큐이지만 사실은 힙인듯 싶다. 보통 힙 알고리즘은 이런식으로 시작된다. 하지만 이건 아직 힙 정렬을 하지 않는 상태다. 위는 완전 이진 트리라고 하는데 이 부분은 추후에 설명할지도 모르겠다. 아무튼 힙 정렬은 2가지로 구분되는데, 최소 힙정렬과 최대 힙 ..
static void dijkstra(int start) { d[start] = 0; visited[start] = true; for(int j = 0; j 검색 -> 최소 -> 검색... 이런식으로 동작되는 것 같습니다. 뭐 이건 이해가 되지 않아도 상관없습니다. 마지막으로 방문은 그 노드에 방문해서 생기는 것이 아니라 그 노드에서 시작할때 발생하는 겁니다. 다익스트라 알고리즘은 최단거리를 구하는 알고리즘으로 잘 알려져 있지만, 간선(노드와 노드 사이)의 길이가 음수라면 불가는하..
점화식 if (array[i] < array[j]) { dp[i] = max(dp[i],dp[j]+1); } 가장 긴 증가하는 부분 수열에 위 점화식으로 모두 해결이 가능하다. 다음은 백준 11053번 문제이다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 여기서 우리가 알아야할 것은 부분 수열이다. 수열은 숫자가 열거된 형태를 말하기 때문에 배열이라 생각해도 무방할 것 같다. 부분수열이란? 그렇다면 부분 수열이라는것은 무엇일까? 위 수열 {10,20,10,30,20,50} 의 부..
* 주의 : 다이나믹 프로그래밍과 다이나믹, 프로그래밍은 아무런 관계없습니다. 처음 이 알고리즘을 만든 분에 따르면 단지 멋있어서 지으셨다는 이야기가 있네요.ㅎㅎ(믿거나 말거나) 중복된 연산을 줄이는 방법으로 사용된다. 여기서 우리는 어떻게 중복된 연산인지 알 수 있을까? 에 대해 생각할 수 있다. 모든 문제들이 중복된 연산이 있는것도 아니고... 어떻게 파악을 해야할까? 많은 방법이 있겠지만... 그 전에 한 가지 공식을 살펴볼 것이다. 이 공식은 고등학교 시절때 배운 공식 중 하나로 등차 수열이라는 공식이다. 등차 수열은 일반적으로 1 3 5 7 9 ..... 이런식으로 증감의 형태로 진행이 되는 특징을 가지고 있다. 우리는 이 식의 점화식을 세울 수 있는데.. 점화식은 x = 2x+1이 된다. 왜 ..
문제는여기에 있습니다. [백준] 14888번 연산자 끼워넣기 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우 b-programmer.tistory.com 전에는 메소드에 변수를 담아 사용했지만... 이번에는 다른 방법을 사용해봤다. 하지만 이 방법은 전에 사용했던 방법과 크게 차이는 없지만, 하나가 차이가 있다, 바로 메소드에 변수를 할당하지 않고 문제를 풀어보았다. package _13.dfs.bfs; import java.util.Scanner; public class Operator3 { static int[] op = n..
개요 조합은 n개 중에서 k를 골라서 뽑는 방법을 구하는 통계용어다. 예를들어 10개 중에서 3개를 고른다고 가정하자. 그러면 10*9*8 / 3 * 2 * 1 => 120가지다. 물론 크기가 너무 크기 때문에 조금더 작은 걸로 교채해보면 5개중애 2개를 고른다면 총 10가지가 나온다. 공을 5개 가지고 있다고 생각해보자. 이들을 2개씩 나눠 보자. 이런식으로 나눌 수 있다는 것을 확인 할 수 있다. 물론 순서는 상관이 없냐고 물어볼 수 있다. 결론부터 말하면 상관없다. 검파나 파검이나 뽑는 사람 입장에서는 파란색 공과 검정색 공을 뽑기 때문이다. 즉, 아무 상관없다는 뜻이다. 이제 이 방법을 토대로 코드를 작성해보자. c++이나 파이썬같은 경우, 조합과 관련해서 라이브러리를 재공해준다. 하지만 자바는 ..
스와핑이라는게 도대체 뭘까? swap 뭘 바꾼다는 말일까? 다양한 프로그래밍언어에서 스와핑 방식을 지원한다고 한다. 하지만 c나 자바같은 언어는 이 방식을 지원되지 않는다. 그렇다고 스와핑을 하지 못하는것은 아니다. 왜냐하면 스와핑이라는게 그리 어렵지만은 않기 때문이다. 이 두개의 상자에는 물감이 들어있다고 가정하자. 물감은 서로 잘 섞이기 때문에 함부로 옮겨담을 수 는 없다. 이 물감은 특이하게 나중에 들어온 물감이 더 강력하다. 즉, 주황색 상자에 파란물감을 부으면 파란색이된다. 그런데 상자 두개안에 들어있는 물감의 위치를 바꾸고 싶어졌다. (단, 위치는 바꾸지 못한다.) 라는 문제가 존재한다고 하자. 그러면 어떤 방법을 사용해야 물감을 잘 옮길 수 있을까? 바로 비어있는 상자를 준비해서 하나의 색깔..
선택 정렬은 데이터들 중에서 가장 작은 데이터를 선택한 뒤, 가장 맨앞에 있는 데이터와 바꾸는 정렬방법이다. 예를들어 위와 같은 그림이 있다고 가정하자. 그러면 가장 작은 값을 선택한다. 가장 작은 값은 1이다. 그러므로 움직이지 않는다. 이 자리는 이제 정렬이 된 상태이므로 더 이상 움직일 필요는 없다. 만약 3처럼 움직여야 되는 상황이라면, 두 번째 숫자인 7과 자리를 바꾸면 된다. 그리고 3도 역시 더 이상 움직이지 않는다. 이제 이와 같은 방법으로 진행하면 자연스럽게 정렬이 되어 있다. 하지만 이 정렬의 가장 큰 문제점은 느리다는 점이다. '그 이유는 가장 작은 값을 찾기 위해 마지막 까지 가야 비로서 찾을 수 있기 때문이다. 즉, 100개끝에 가장 작은 번호가 있을 경우, 100번까지 도달해야 ..
드디어 dfs/bfs는 끝이다! 이글에서는 DFS/BFS가 대략적인 내용을 설명하고 내 나름대로 DFS와 BFS를 분석한 내용을 말하려고한다. 두개의 공통점은 DFS나 BFS둘다 그래프를 이용하는 알고리즘이다. 하지만 극명히 달리는 차이점이 있는데, 그건 바로 값을 어떻게 읽는지가 다르다. 즉, DFS는 스택형식으로 값을 읽고 BFS는 큐형식으로 값을 읽는다. 스택과 큐를 잘 모르시는 분들은 2020/09/03 - [알고리즘/코테 알고리즘 정리 노트] - dfs/bfs 정리(1) dfs/bfs 정리(1) dfs와 bfs는 역할은 비슷하지만 그 표현방법이 다릅니다. 대표적으로 dfs는 스택으로 표현하고 bfs는 큐로 표현을 합니다. bfs와 dfs를 들어가기에 앞서 스택과 큐를 간단하게 알아보겠습니다. 스..