공부하는 블로그

동적 프로그래밍과 탐욕법은 문제를 해결하여 최적의 해를 구하는 방법이다. Dynamic Programming? 동적 프로그래밍(Dynamic Programming)은 큰 문제를 하위의 작은 문제들로 나누어 풀어 최적의 해를 구하는 기법이다. 이러면 분할정복 기법과 다를게 없어 보인다. 하지만 분할정복 기법은 작은 문제들을 풀다보면 같은 작은 문제를 반복해서 푸는 경우가 생기게 된다. 이 때, 작은 문제를 매번 다시 계산하지 않고 값을 배열에 저장(Memoization)해두었다가 재사용하는 것이 동적 프로그래밍이다. 동적 프로그래밍을 이용하여 풀 수 있는 대표적인 문제는 피보나치 수열, 최장 공통부분 수열문제, 배낭 문제 등이 있다. 간단하게 피보나치수열 문제를 풀어보자. package fibonacci;..

Queue? 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. Queue Method · add() : 리스트의 끝 부분에 새로운 요소를 추가한다. · remove() : 리스트의 첫 번째 항목을 제거한다. · peek() : 큐에서 가장 위에 있는 항목을 반환한다. · isEmpty() : 큐가 비어 있을 때에 true를 반환한다. Queue Code(JAVA) import java.util.ArrayList; import java.util.List; class MyQueue { private List que = new ArrayL..

Stack? 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO - Last In First Out)로 되어있다. 자료를 넣는 행위를 푸시(Push), 넣어둔 자료를 꺼내는 행위를 팝(Pop)이라고 한다. *LIFO : 나중에 넣은 값이 가장 먼저 나오는 것을 LIFO 구조라 한다. 스택은 프로그래밍 언어마다 라이브러리로 구현되어 있지만 직접 사용자가 연결 리스트를 이용하여 구현해낼 수도 있다. Stack Method · pop() : 스택에서 가장 위에 있는 데이터를 제거한다. · push() : 스택의 가장 위에 데이터를 추가한다. · peek() : 스택의 가장 위에 있는 항목을 반환한다. · isEmpty() : 스택이 비어있을 때에 true를 반환한다. Stack C..