Dev-/자료구조, 알고리즘 썸네일형 리스트형 동적 계획법, 동적 프로그래밍 재귀와 같이,, 자기 자신을 계속 호출하는 형태의 함수에서 각 함수의 결과를 미리 저장해 놓고, 호출시 저장된 값을 활용해 시간을 단축하는 방법 가령 피보나치 수열을 예로 위 그림과 같이 계속 반복되는 부분이 있을 때,, 초기 매개변수가 작다면 실행 시간에 큰 차이가 없지만,,매개변수가 커졌을 때, 매번 그 부분을 계산하는 것은 매우 비효율적이다. 따라서 그 값을 저장해둔다. 아래는 비교 - 동적 계획법 X/** * 일반 재귀 * @param n * @return */ public static int fibo(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fibo(n - 2) + fibo(n -1); } } .. 2581번) 소수 boolean 타입의 소수여부를 판단하는 메서드 isSosu를 만든 후, 해당 메서드를 사용해 ArrayList에 넣어주었습니다. 재귀함수의 쓰임은 무한루프만?? 참조: 재귀함수가 무한루프에 빠지지 않기 위한 조건 2가지 재귀함수가 성립되기 위한 조건들을 보시면,수학에서의 귀납법과 굉장히 닮아있다는 것을 알 수 있습니다. 귀납법은 어떤 명제를 증명하기 위한 하나의 방법론으로 1. n = 1-> 명제가 성립함을 확인2. n = k - 1 명제가 성립함을 가정 -> n = k 명제가 성립함을 확인---> 위 1, 2가 성립하면 해당 명제는 참! 뭐 대강 이런식인데,재귀함수의 성립 조건과 상당히 닮아 있습니다. 고로, 대부분의 문제를 해결할수 있습니다.여기엔 반복문도 포함해, 정말 대부분의 문제가 해결 가능합니다. 굳이 이렇게 언급하는 이유는,,, 재귀함수라 하면대부분 무한루프와 관련된, 혹은 비슷한 문제만 해결가능할 것이라고 생각하기 때문입니다. 어떠한 문제가 주어졌.. 재귀함수가 무한루프에 빠지지 않기 위한 조건 2가지 재귀함수는 공부할 때도 많이다뤄보지 못했지만,실무에서 꽤나 중요한 것 같습니다. 뭐.. 검색해보니 의견이 반반인 것 같지만.. 현재 다니는 회사의 면접을 볼때에도팀장님이 따로 중요하다고 말씀하기도 하셨구요. 여튼 간단히 기억해두면 좋을 것 같아 정리해둡니다. 재귀함수가 무한루프에 빠지지 않기 위해서는 1. 무한루프에 빠지지 않을 적어도 하나의 경우가 존재해야 한다.2. 재귀를 반복하면 결국 위 경우에 수렴해야 한다. 여기서 '수렴'은 재귀함수에 들어가는 매개변수의 형태로 표현하시면 됩니다. 시간복잡도란? 대강 뜻만 알면 되겠지 하고 자세히 알아본 적이 없었네요.자세히 살펴보겠습니다. 어떠한 알고리즘의 자원의 사용량을 분석하는 것은 중요한 이슈입니다.얼마나 잘 짜여져 있는지 확인할 수 있는 지표이기 때문이죠. 여기서 자원이란실행 시간, 메모리, 저장장치, 통신 등 말 그대로해당 알고리즘을 돌리는데 사용되는 모든 재료를 말합니다. 이러한 여러가지 자원 중 표현하기 가장 좋은 것이 실행시간이겠죠. 하지만 실행시간으로 자원의 사용량을 나타내기에는 문제점이 있습니다.실행시간은 하드웨어, 운영체제, 언어, 컴파일러 등 실행 환경에 따라서 달라지기 때문입니다. 따라서 환경에 구애받지 않는 관측도구를 사용한 점근적인 접근이 필요한데,이것이 바로 시간복잡도입니다. 다시말해 시간복잡도는,실행시간 대신 연산의 실행횟수를 카.. 정규화란? 정규화를 이해하려면, 우선 이상(Anomaly)에 대해 알 필요가 있습니다. 이상: 한 릴레이션에서 일부 속성들의 함수적 종속으로 인해 데이터의 중복이 발생하는 것- 삽입, 삭제, 갱신 이상이 존재 다시말해, 자료가 (객체지향 프로그래밍이 피해야할) 종속성을 가지고 있어데이터 처리시 모순이 발생하는 것을 이상이라고 합니다. 여기서 함수적 종속이란, 한 속성이 다른 속성의 값을 유일하게 결정하는 것을 말합니다.(X -> Y: Y는 X에 종속) 정규화는 바로 이러한 자료의 이상을 해결하기 위해 고안된 방법입니다.각각의 정규형에 대해 알아보겠습니다. - 제 1 정규형(1NF): 모든 속성의 도메인이 원자값으로 구성(원자값은 단일값을 말하며, 즉, 복합값, 다중값이 아닌 값을 말합니다.) (출처: http://.. 스택(Stack), 큐(Queue), 그리고 덱(Deque) 자료구조 중에는 LIFO(Last In First Out: 후입선출)과 FIFO(First In First Out: 선입선출)가 있습니다. 스택(Stack)과 큐(Queue)가 바로 그러한 형태를 띄고 있습니다. (출처: https://blog.naver.com/coolten/140057846054) stack: '~을 쌓다.' -> '가장 마지막에 쌓은 것을 뺀다.'뭐 이렇게 생각하시면 잘 기억나겠죠?두 가지 자료구조를 사용하는 예는 아래와 같습니다. Stack: JVM 스택 메모리-> JVM 스택 메모리에 저장된 변수는 나중에 저장된 변수부터 제거Queue: 스레드풀-> 작업 큐가 먼저 들어온 작업부터 처리 그리고 스택과 큐의 장점을 모두 합친 것이 바로 덱(Deque)입니다.Double Enable.. 이전 1 다음
