Knowledge (36) 썸네일형 리스트형 꼬리재귀호출 (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개의 .. Insertion Sort (삽입정렬) 삽입정렬(Insertion Sort)란? 삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여,자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.선택정렬이나 버블정렬과 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않기 때문에 시간 복잡도가 O(n)이 된다. 예를 들어 카드 게임을 할 때, 내 손에는 이미 정렬된 카드가 있고, 새로운 카드를 받아 카드 사이의 올바른 자리를찾아 삽입함으로써 정렬이 유지되게 하는 것이다. import java.util.Scanner; /** * Created by Itner o.. Bubble Sort (버블 정렬) 버블 정렬(Bubble Sort)란? 버블정렬은 두 인접한 원소를 비교하여 정렬하는 방법이다. 시간복잡도가 로 상당히 느리지만,코드가 단순하기 때문에 자주 사용된다. 레코드의 이동이 마치 거품이 수면 위로 올라오는 듯한 모습을 보이기 때문에 붙여진 이름이다. 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다.이러한 비교-교환 과정을 스캔이라 하며, 스캔이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽끝으로 이동하게된다. 이러한 스캔은 정렬이 완료될 때까지 반복된다. import java.util.Scanner; /** * Created by Itner on 2017. 7. 19.. */ public class BubbleSort_Rz { public static vo.. 이전 1 2 3 4 5 다음
