본문 바로가기

알고리즘

 (60)
DP 기본문제인 막대기 자르기(백준에 없는문제) 코드&그림매칭 자식들간 비교를 하여 그 중 최대값을 반환하는 코드 1. 막대기 자르기 문제의 일반화 나누어지는 대상이 1차이로 나누어지고 각각의 값(길이)에 대한 가치 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할 수 있다. 좀더 일반화 나누어지는 대상이 n차이로 나누어지고 각각의 값(길이)에 대한 가치가 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할수 있다. Bottom-up 방식으로 해결: 반복문을 사용하여 값을 1부터 시작하여 1일때의 최대 가치, 2일 때의 최대가치를 차근차근 구하여 이전에 얻은 값을 다음에 얻을 값을 계산할때 이용한다. 값이 가장 작을 때 그 값을 구성할수 있는 경우는 오직 한가지 뿐임을 이용한것. 예를들어 숫자 50을 쪼개는 방법은 여러가지다..
동적프로그래밍의 개념과 기본 개념을 잡아주는 피보나치 문제 동적 프로그래밍은 이름이 조금 이상한데요. 프로그래밍은 컴퓨터 프로그래밍이라는 뜻이 아니라 테이블을 만든다는 뜻입니다. 그리고 전혀 다이나믹하지도 않습니다. 그래서 어떤 서울대 교수님은 동적 프로그래밍 대신 기억하기 프로그래밍이라는 용어를 쓰기도 합니다. 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다. 알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사..
위상정렬 대표적인 2문제 비교 처음문제를 풀당시 기존의 위상정렬에서 정점들의 선행순서를 위반하지만 않는다면 어떤 순서로 정렬해도 상관이 없었지만 14567, 선수과목 (Prerequisite) 문제에서는 각과목의 누적학기를 표시해 주어야 했다. 이걸 어떻게 누적시키지? 생각하며 재귀를 이용해야 하나? 라는 생각도 잠시 했었다. 하지만 심플하게 반복문을 돌면서 기존에 deque에 저장되어있던 학기정보인 cnt를 popleft하고 append하는 과정에서 자연스럽게 누적되는 학기수를 다룰수 있었다. 두 코드의 비교! 1. 전형적인 (위상)정렬 코드에서는 그래프를 표현하기위해 인접행렬을 사용하였지만 선수과목 문제에서는 사전과 리스트를 사용해 그래프를 표현하였다! 2. (위상)정렬 코드에서는 진입차수가 0인 정점을 저장하기 위해 vacant..
School algo02 전수조사 재귀를 이용한 전수조사문제는 거시적 관점에서는 대부분 재귀트리를 내리락 오르락 하면서 답을 찾아나간다. 다만 세부적으로보면 올라가면서 답을 찾는 경우가 있고 완전히 내려와서 찾는 경우가 있다(물론 내려가면서 찾을수도 있지만 이 경우는 내가 경험해 본 바에 의하면 올라가면서 찾는 경우로 바꿀수 있고 그렇게 바꾸는게 더 코드가 좋다). 이는 어디까지나 세부적으로 보았을때 그렇다는 말이지 거시적으로는 대부분 내리락 오르락 하면서 답을 낸다. import java.util.Scanner; public class Main { // int[블록을 놓는 모양][모양에 따른 블록들의 상대좌표][상대 좌표] // 가장 왼쪽 위 블록을 기준으로 상대좌표를 산정한다. // (y좌표,x좌표) private static int..

티스토리툴바