다이나믹 프로그래밍이란? 다이나믹 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 풀고, 그 결과를 저장하여 중복 계산을 방지하는 기법이다. 다른 말로 동적계획법이라고도 한다. 이 기법은 주로 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 다이나믹 프로그래밍에는 대표적으로 2가지 방식이 있다. 첫 번째 방식은 탑다운이고, 두 번째 방식은 보텀업이다. 다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 살펴보자. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열이란 이전 두..

문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의..

문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 입력 조건 첫째 줄에 정수 N이 주어진다. (1

트리 자료구조 이진 탐색은 전제 조건이 데이터 정렬이다. 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree) 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 따라서 데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다. 그렇다면 트리 자료구조란 무엇일까? 트리 자료구조는 노드와 노드의 연결로 표현하며, 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다. 트리 자료구조의 특징에는 아래와 같은 것들이 ..

Collections 클래스 제공 유형 Collections 클래스는 제네릭을 지원하므로 모든 객체 유형에 대해 동작한다. 그러나 기본 데이터 유형 (예: int, double 등)은 자바 컬렉션 프레임워크의 일부가 아니므로 기본 데이터 유형을 직접 다루는 Collections 클래스의 메서드는 없다. 대신 이러한 기본 데이터 유형을 포함하는 래퍼 클래스 (예: Integer, Double 등)를 사용해야 한다. Collections 클래스의 메서드 1. sort(List list) 주어진 List를 오름차순으로 정렬한다. 이 메서드는 입력 List를 직접 변경한다. List numbers = new ArrayList(Arrays.asList(3, 1, 4, 1, 5)); Collections.sort(..

1. 순차 탐색 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다. 다음은 순차 탐색으로 Dongbin을 찾는 과정이다. Step 0. 초기 단계 Hanuel Jonggnu Donbin Taeil Sangwook Step 1. 가장 먼저 첫 번째 데이터를 확인한다. Haneul은 찾고자 하는 문자열과 같지 않다. 따라서 다음 데이터로 이동한다. Hanuel Jonggnu Donbin Taeil Sangwook Step 2. 두 번째 데..