1. 문제 2. 문제 풀이 다이나믹 프로그래밍 (DP) 문제이다. 현재의 상태를 저장시켜서 이를 지속적으로 활용하는 다이나믹 프로그래밍의 특성에 맞춰, 다음과 같은 문제 풀이 접근 방법을 활용하였다. '각각의 계단에 대해서, 이전 계단을 선택하는 경우와, 이전의 이전 계단을 선택하는 경우를 계산해나간다.' 즉, 각 계단에 대해서 다음의 알고리즘을 반복하는 것이다. (1) 이전 계단을 선택하는 경우, 이전 계단의 상태 중에서 '이전 계단을 선택하지 않았던 상태'를 선택할 수 있다. -> 이전 계단 중에서, '이전 계단을 선택했던 경우'를 선택하면 연속해서 세 계단을 오른 경우이므로 선택 불가 (2) 이전의 이전 계단을 선택하는 경우, 이전의 이전 상태 중 더 큰 값을 선택한다. -> 이전의 이전 계단의 경..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍(DP)의 대표적인 유형 중 하나인 LIS 문제이다. 현재의 상태를 지속적으로 저장시켜서 문제를 푸는 DP의 특성을 이용하여 문제에 접근한다. 나의 경우에는 다음과 같은 방법을 고안했다. 각 값들에 대해서, 그 값까지 만들어지는 LIS를 지속적으로 저장시켜 나간다. 이 때, 현재의 LIS를 구하는 방법은 다음과 같다. '자신보다 작은 이전의 Value들에 대해서, 그때까지의 LIS가 가장 큰 값에 1을 더한다.' 즉, 각 LIS 값은 다음과 같은 조건으로 구한다. (1) 현재 LIS 값보다 이전의 값들에 대해서 (2) 현재 자신의 Value보다 작은 값들에 대해서 (3) LIS 값이 가장 큰 값을 구한 후, 그 값에 1을 더한 값으로 구한다. (4) 만약 조건..

1. 언제 사용하는가? 정렬은 가장 기본적인 알고리즘임과 동시에 중요한 알고리즘이다. 하지만 그 구현이 쉽지 않고, 실제로 구현해서 사용하기에는 오류가 많기에 문제 하나 하나를 풀때마다 정렬을 코딩하는 것은 비현실적이다. 이를 위해, C++의 STL에서는 사용자가 빠르게 정렬할 수 있는 함수를 제공하는데, 이것이 'sort' 함수이다. 퀵소트를 기반으로 만들어졌다고 한다. 2. 사용 방법 다음과 같이, 'algorithm' 헤더를 include하여 사용한다. vector를 정렬하는 방법과, 배열을 정렬하는 방법은 다르므로 사용법을 익혀야 한다. 기본적으로 vector는 begin와 end 지점을 명시해주며, 배열은 그 크기를 입력해주는 것으로 사용한다. #include #include #include u..

1. 문제 2. 접근 방법 자료구조를 배울 때, '재귀' 하면 바로 떠오르는 것이 이 문제이다. 그 만큼 가장 재귀를 잘 설명하는 문제가 되며, 재귀의 강력함을 잘 보여주는 사례라고도 할 수 있다. 접근 방법은 이렇다. 첫 장대를 A, 가운데 장대를 B, 목적지 장대를 C라고 한다면 N개의 원판을 이동시키려면, N - 1 개의 원판을 B에 옮긴 후, 나머지 1개를 C에 옮긴다. 그 후, B에 있는 N - 1 개의 원판을 다시 C로 옮기면 되는 것이다. 이러한 접근 방식은 또 다시 N - 2개의 원판을 옮기는 문제로 분할되어 분할 정복 방식으로 문제가 풀어지는 것이다. 3. 코드 #include #include void hanoi(int from, int to, int by, int num) { if (n..

1. 소수 구하기 알고리즘에 대하여 알고리즘을 공부하는 사람이라면 누구나 소수를 찾는 문제에 직면하게 된다. 가장 쉽게는 가능한 모든 수 범위에서 소수를 구할 수 있지만, 범위가 클 경우 시간이 매우 오래 걸린다. 그러므로 큰 범위에서 소수를 찾기 위해서는 효율적인 알고리즘을 사용할 필요가 있는데, 여기에서 알아볼 알고리즘이 '에라토스테네스의 체' 이다. 2. 에라토스테네스의 체 '에라토스테네스(Eratosthenes)의 체'란, 다음과 같이 반복적인 과정을 반복함으로서 주어진 범위에서의 소수를 찾는 것이다. (1) 2부터 시작해, 2를 제외하고 2의 배수들을 모두 제외시킨다. (2) 3부터 시작해, 3을 제외하고 3의 배수들을 모두 제외시킨다. (3) 4는 이미 제외되었으므로, 5부터 시작하고 5를 제..

1. 구분자(delimiter)를 이용한 파싱 처리란? 가장 대표적인 예는 엑셀의 .csv 파일이다. .csv 파일은 ',' 기호로 셀을 나누고 있는데, 다음과 같은 모양을 갖추고 있다. 서울특별시,인천광역시,부산광역시 위의 .csv 파일을 ',' 구분자로 구분하면 다음 3개의 항목을 얻을 수 있는 것이다. (1) 서울특별시 (2) 인천광역시 (3) 부산광역시 이와 같이 특정한 구분자를 사용해서 string을 파싱하는 경우가 종종 있는데, 이 때 사용하는 것이 stringstream 객체와 getline 함수이다. 2. 코드 (내용 추가 예정) #include #include #include int main(void) { string s = "seoul,busan,incheon"; stringstream..