Knowledge/Algorithm (13) 썸네일형 리스트형 합병 정렬 (Merge Sort) 합병정렬(Merge Sort)이란? 합병정렬은 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법이다. 합병정렬을 쉽게 말하면 배열을 나눌 수 있는 데까지 나누고 합치면서 정렬하는 방식이다.시간복잡도는 모든 케이스에 대해 O(n logn)이다. 합병정렬(Merge Sort) 구현 (Java)https://github.com/jobcing/Algorithm/blob/master/src/imple/MergeSort.java 페이지 교체 알고리즘 (Page Replacement Algorithm) 페이지 교체 알고리즘이란?메모리를 관리하는 운영체제에서 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. OPT (Optimal)앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법이다.미리 페이지의 사용 여부를 예측해야하므로 실현 가능성이 희박하다. FIFO (First In First Out)주기억장치에 가장 오래 있었던(가장 먼저 들어온) 페이지를 교체하는 방법이다. LRU (Least Recently Used)가장 오랫동안 사용하지 않은 페이지를 선택하여 교체하는 방법이다.페이지 참조의 시간적 구역성을 고려하여 FIFO 알고리즘의 모순을 개선하기 위해 고안된 방법 LFU (Least Frequently Used)사용된 횟수를 .. 꼬리재귀호출 (Tail Recursion) 재귀 호출이란?하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.코드가 짧아져 가독성을 높일 수 있다는 장점이 있지만, 스택 오버 플로우를 일으킬 수 있다. 함수를 호출할 때 함수의 입력 값, 리턴 값, 돌아갈 위치 값 등을 스택에 저장한다.재귀 함수를 사용하면 함수가 끝나지 않은 채 계속해서 함수를 호출하므로 스택에 메모리가 쌓이게 되고,오버플로우가 발생하는 것이다. 이러한 재귀 호출의 단점을 보완하기 위한 방법으로 꼬리 재귀라는 방법이 있다. 꼬리재귀호출이란?재귀호출이 끝난 후, 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태이다.이를 이용하면 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로처리하도록 바꿔 스택을 재사용할 수 있.. 백준 알고리즘 2579번 이 문제는 각 단계마다 경우의 수가 몇가지 존재하고 그 중 가장 큰 값만을 저장하고 단계를 진행하는다이나믹 프로그래밍문제이다. 하지만 몇가지 제약이 존재하는 DP라고 볼 수 있다. 조건을 회피하고 생각하는 것보다 조건을 처음부터 생각하며 DP 점화식을 세우는 것이 적절하다.DP문제는 이 점화식을 세우는 것이 관건인데, 뒤에서부터 고려하여 식을 짜는 것이 수월하다. 제약 조건을 살펴보면한번에 1칸 또는 2칸을 오를 수 있다.연속 3칸을 밟은 순 없다.마지막 계단은 반드시 밟아야 한다. 뒤에서부터 생각하면, 마지막 계단은 반드시 밟아야하고 연속적으로 3칸은 밟을 수 없으므로나올 수 있는 경우의 수는 2가지이다.전 단계의 계단을 밟는 경우전 단계의 계단을 밟지 않는 경우 즉, 위와 같은 경우의 수 2가지를 점.. 백준 알고리즘 1149번 마찬가지로 문제를 풀기 전에 어떠한 알고리즘을 써야할지 생각을 해보자.각 단계마다 경우의 수가 존재하고 그 경우의 수 중에 가장 최소값을 구하는 문제이다. 사용해야할 기법은 다이나믹 프로그래밍 ! 단순하게 생각하자면 점화식은 [n - 1]의 최소값 + [n]의 최소값이다.전 단계의 최소값과 지금 단계의 r,g,b 중 가장 작은 값을 더하는 것이다. 하지만 여기서 하나 더 생각해야되는 조건이 있다.바로 전 단계의 r,g,b와 겹치면 안된다는 것이다. 내가 만약 r을 선택했다면 그 전 단계는 b, g중 최소 값을 더해야 된다는 뜻이다. 이 조건을 생각해서 다시 점화식을 세우면min = Min([n - 1][g] + [n - 1][b]) + r 이 된다. r,g,b 선택한 3가지 경우의 수중 제일 작은 값 하.. 백준 알고리즘 1463번 1로 만들기 성공 풀이문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB306589750653433.225%문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.예제 입력 복사2 예제 출력 복사1 예제 입력 2 복사10 예제 출력 2 복사3 힌트10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. #.. 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘은 여러개의 Spanning Tree 중 최소 비용을 가지는 Tree를 구하는 알고리즘이다.주로 간선의 방향성이 없고, 모든 노드를 방문해야 하며, 간선에 가중치가 주어질 때 주로 사용된다. 이러한 최소비용을 가지는 Spanning Tree를 MST(Minimum Cost Spanning Tree), 최소비용신장트리라고 한다.MST 문제를 해결하기 위한 알고리즘으로는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘은 Merge Sort와 Union-Find를 사용하여 구현한 알고리즘이고,프림 알고리즘은 Heap을 사용하여 구현하는 알고리즘이다. 우선 Spanning Tree(신장트리)가 무엇인지 알아보자. S.. 백준 알고리즘 2156번 문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6개의 .. 이전 1 2 다음
