본문 바로가기

전체 글

(229)
[DP-예제 1] 블럭채우기 동적 계획법의 예제인 블록채우기에 대해서 공부하면서 DP를 공부해 보자.세로 길이가 2 이고, 가로 길이가 N 인 블럭에 세로 2, 가로 1의 블럭을 채우는 경우의 수를 구하는 예제이다.쉬운 이해를 위해서 입력 N 이 4일 때(가로 길이가 4) 블럭을 채우는 경우의 수는 5이다. 블럭을 채우는 방법을 보면 이러한 식으로 채울 수 있는 방법이 생각해 보면 5가지가 있다.그런데 이 문제를 코딩으로 어떻게 해결 할 수 있을까? 블럭 채우기 알고리즘을 세울려면 먼저 전체 경우를 어떻게 나눌 것인지 생각해야 한다.이 부분이 동적 계획법에서 가장 생각 해 내기 어려운 부분 문제를 정의하는 과정이다. 모든 경우의 수를 보면 위와 같은데, 어떻게 기준을 세우냐면 가장 마지막에 들어가는 블럭을 본다.그러면 1개가 세로로..
동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 은 각 단계에서 해결해야 할 일련의 문제들이 상호 관련성을 맺고 있을 경우에, 어느 단계에서 하나의 결정이 이루어지면 그 결정은 그 다음 단계의 문제를 결정하는 데 영향을 미치게 되고 그 결과 달성하고자 하는 목표에도 영향을 미치게 되기 때문에 이러한 문제를 해결하기 위해서 필요한 알고리즘이다. 대표적인 예로 [피보나치 수] 가 있다. 피보나치 수는 1 1 2 3 5 8 ... 형식으로 이루어져 있는 수열을 의미하는데,초기값인 첫번째 항과 두번째 항은 1이고, n-2 번째 항과 n-1 번째 항을 더해서 n번째 항을 구한다.n 번째 피보나치 수열을 구하는 코드는 위와 같다. 하지만 피보나치 수를 구하는 알고리즘을 위의 코드 같이 재귀적으로 짜면 문제가 발..
분할정복법 (Divide & conquer) 분할정복법은 문제를 여러 개로 분해하여 해결한 후 풀린 부분 문제들을 거꾸로 조합하여 원래의 문제를 푸는 방식이다.대표적인 예로 합병, 퀵 정렬이 있는데, 합병 정렬에서는 정렬을 반으로 나눠서 숫자를 비교해서 합치는 것이 분할정복법의 원리라고 할 수 있고,퀵정렬도 마찬가지로 pivot 보다 작은 왼쪽부분, pivot 보다 큰 오른쪽 부분을 구해서 pivot 의 자리를 찾아가는 과정이 분할정복법이라 할 수 있 다. 출처 : Algorithm LABS
연속부분최대합 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9 예제 출력11 예제 입력5 -1 -2 3 -2 4 예제 출력5 주어진 숫자들 중에서 연속부분의 최대합을 구하는 문제이다. 완전탐색을 해서 범위를 점점 늘리거나 줄여가면서 구하면 쉽게 구할 수 있는 문제이지만, 입력을 보면 범위가 100,000 까지 이기 때문에, 완전탐색으로 시간복잡도가 이 되면 시간..
힙을 이용한 우선순위 큐 구현 1) 삽입연산 (push)- 힙은 완전 이진 트리 형태이기 때문에 삽입연산을 할 때에는 배열의 길이면서 원소를 삽입해주는 인덱스를 표현해주는 len 변수를 선언해서 큐의 len에 원소를 삽입해주고 len의 길이를 1 늘린다.- 그리고 나는 idx 라는 변수를 선언해서 새로운 원소가 삽입된 자리의 인덱스를 기억해서 부모와 우선순위를 비교 했다.- 부모의 인덱스, 즉 idx / 2 와 비교 해서 idx가 더 작게 되면 자리를 계속해서 바꿔주고, 아니면 반복문을 빠져나간다. 여기서 주의 할 점은 삽입한 원소가 가장 우선순위가 높아 루트노드 까지 가게 되면 더이상 비교할 것이 없기 때문에 반복문을 멈춰줘야 하는데, while 문의 조건을 보면 idx > 1일때만 실행 되게 하여 idx 가 1이 되었을 때 (루트..
힙 (Heap) 힙은 부모의 값이 항상 자식보다 우선순위가 높은 (사진상에서는 작은 숫자가 우선순위가 높다고 가정) 완전 이진 트리이다.완전 이진 트리는 자식이 항상 2개이고, 왼쪽에서 오른쪽방향으로 원소가 추가 되는 트리를 말한다. 힙에서는 2가지 연산을 할 수 있다.1) 원소를 추가하는 연산2) 원소를 삭제하는 연산 힙에 값을 삽입할 때 힙은 완전 이진 트리이기 때문에 무조건 사진의 화살표 방향으로 원소를 추가해야 한다.위의 사진상에 4를 추가한다고 해보자. 4를 추가하면 사진처럼 완전이진트리에 삽입된다. 근데 힙은 항상 부모 노드의 값이 자식노드보다 우선순위가 크기 때문에 4를 삽입했을 때 올바른 자리가 아니다.그러기 때문에 4노드의 부모노드인 7과 우선순위를 비교해서 자리를 바꿔줘야 한다. 4와 7의 자리를 바꾼..
우선순위 큐 (Priority Queue) 우선순위 큐는 원소를 push하는 방법은 기존의 큐와 똑같지만 삭제 연산을 할 때 우선순위가 높은 원소 순서대로 제거 하는 큐이다. 그림처럼 원소를 1 -> 3 -> 4 -> 5 순서로 push한다. 큐 안에 push 된 원소들은 1, 3, 4, 5 순서대로 있지만 우선순위 큐에서는 우선순위를 부여하여 우선순위가 가장 높은 순서대로 원소를 제거 한다.그림상에서는 숫자가 큰 순서대로 우선순위가 크다고 가정했다. 우선순위 큐는 배열로 구현 할 수 있는데, 삽입 연산은 그대로 큐의 끝에 원소를 삽입하여 O(1)의 시간이 걸린다.하지만 삭제 연산을 할 때, 배열의 처음부터 큐의 길이 까지 우선순위를 탐색하여 가장 큰 원소를 삭제하고그 다음에 삭제한 원소의 빈자리를 오른쪽에서 부터 한칸씩 당겨야 하기 때문에 O(..
트리순회 결과 출력하기 문제루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 아래 그림은 이진트리의 예제와, 이 이진트리를 전위순회, 중위순회, 후위순회 한 결과를 나타낸다. 입력첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다. 출력첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다. 예제 입력6 0 1 2 1 3 4 2 -1 5 3 -1 -1 4 -1 -1 5 -1 -1 예..