Algorithm 개념 및 문제풀이/Knowledge2 동적 계획법 개념정리 개요 동적 계획법을 공부한 내용을 정리하기 위해 작성하였습니다. 공부하신 분들께 도움이 되면 좋겠습니다. 개념 정의 : 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법 큰 의미에서 보면 분할 정복과 같은 접근 방식을 의미합니다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해냅니다. 동적 계획법은 답을 여러 번 계산하지 않고 한 번만 계산하는데 이 계산 결과를 재활용함으로써 속도 향상을 꾀할 수 있습니다. 여기서 답을 메모리에 저장하는데 이 메모리의 장소를 캐시(cache)라고 부릅니다. 메모이제이션 앞서 캐시를 이용한 것처럼 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값.. 2020. 4. 6. 연결리스트(Linked-list) 개념 정리 및 문제 풀이 개요 연결리스트 문제를 풀면서 모르는 점들이 많다고 느껴 해당 개념을 정리하고 관련 문제를 푸는 방법에 대해서 글을 작성하였습니다. 개념 연결리스트란? 배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는 것은 시간이 오래 걸리는 작업입니다. 해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문입니다. 평균적인 경우 이 작업들에는 원소의 개수에 선형 비례하는 시간이 걸립니다. 이와 같은 문제를 해결하기 위해 고안된 자료 구조가 연결 리스트(linked list)로, 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해줍니다. 연결 리스트는 배열과 아주 다른 형태를 가지고 있습니다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되.. 2020. 2. 18. 이전 1 다음
