코딩 테스트

다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 하며, 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 줄일 수 있는 방법이다.  다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다. 결과적으로 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있다.이를 해석하면 다음과 같다. n번째 피보나치 수=(n-1)번째 피보나치 수  + (n-2)번쨰 피보나치 수단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1프로그래밍에서는 이러한 수..

순차 탐색(Sequential Search) 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다.  순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용..