점화식 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이 된다. 왜 ..
개요 조합은 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를 들어가기에 앞서 스택과 큐를 간단하게 알아보겠습니다. 스..
인접 행렬 : 2차원 배열로 그래피의 연결로 표현하는 방식 public class AdjacencyMatrix { public static int INF = Integer.MAX_VALUE; public static List graph = new ArrayList(); public static void input() { // INF는 이동이 불가능한 경우를 뜻한다. graph.add(Arrays.asList(0, 7, 5)); graph.add(Arrays.asList(7, 0, INF)); graph.add(Arrays.asList(5, INF, 0)); } public static void print() { input(); System.out.println(graph); } public static ..
dfs와 bfs는 역할은 비슷하지만 그 표현방법이 다릅니다. 대표적으로 dfs는 스택으로 표현하고 bfs는 큐로 표현을 합니다. bfs와 dfs를 들어가기에 앞서 스택과 큐를 간단하게 알아보겠습니다. 스택 : push(), pop() 으로 데이터를 넣고 뺍니다. 즉, 박스 쌓기와 비슷합니다. 하지만 프로그래밍의 특이성 때문에 실제처럼 구현하기는 어렵습니다. 그래서 하얀게 박스이고 노란게 pop, 초록색이 push라 생각했습니다. 즉, 스택은 한쪽에서 pop과 push가 진행이 된다는 것을 알 수 있었습니다. 또, 스택은 선입 후출입니다. 그러면 큐는 어떨까요? 큐 : append(), pop() 스택과 마찬가지로 위의 명령어로 데이터를 넣고 빼는 형식입니다. (언어마다 조금씩 다른것 같군요.) 아무튼 큐..
피지컬로 승부하자! - 프로그래밍 언어를 정확히 알고 있어야 하며, 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한 다 - 구현 유형의 문제는 풀이는 떠올리기 쉽지만, 소스코드로 옮기기 어려운 문제'를 의미한다. - 이러한 유형들은 알고리즘을 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 게 좋다'라고 설명했다. - 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 - 특정 소수점 자리까지 출력하는 문제 - 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등 완전 탐색 - 모든 경우의 수를 주저없이 다 계산하는 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 메모리 제약! 구현 문제에 접근 하는 방법 - 보통..
- 이름에서 알 수 있듯이 Greedy는 단순, 무식하게 탐욕적으로 푸는 알고리즘이다. 하지만 단순, 무식하게 푼다는것은 생각보다 쉽지 않다. 여기서 무식하게 푼다는 의미는 예를 들어 우리가 여러 지폐들중 하나만 가질 수 있다고 한다면, (무조건 한 장만 가능하다.) 가장 값어치가 가장 큰 지폐를 선택하게 된다. 이것은 어쩔 수 없다. 이런게 그리디인데 코딩 테스트에서는 단순하게 문제가 나오지는 않는다. 그리디가 사전에 외우지 않고 있어도 풀 수 있는 가능성이 높은 유형이라고는 하지만, 다른 유형과 함께 등장하는 경우도 많다고 한다. 예를 들어, 정렬알고리즘과 함께 사용하던가, 최단경로를 구하는 알고리즘과 함께 사용한다고 할때 이들을 미리 알고 있지 않으면 문제를 풀지 못하는 상황이 발생할지도 모른다. ..