알고리즘

TIL] (자료구조)링크드 리스트

링크드 리스트 링크드 리스트는 연결 리스트라고도 합니다. 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조를 가지고 있고 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표(포인터)로 연결해서 관리합니다. 링크드 리스트는 미리 데이터 공간을 할당하지 않아도 되는 장점이 있지만 연결을 위한 별도 데이터 공간이 필요하여 저장공간 효율은 높지 않습니다. 또한 연결 정보를 찾는 시간이 필요하여 접근 속도가 느리다는 단점이 있습니다. 용어 노드 : 데이터 저장 단위입니다. (데이터 값, 포인터)로 구성되어 있습니다. 포인터 : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있습니다. head : 맨 앞을 가르킵니다. before : 현재 위치 전입니다. current : 현재 탐색 위..

TIL] 알고리즘 공부

최댓값 구하기 시간 복잡도 ↑ (N제곱) input = [3, 5, 6, 1, 2, 4] def find_max_num(array): # array의 길이만큼 아래 연산실행 for num in array: # array의 길이만큼 아래 연산실행 for compare_num in array: #비교연산 1번실행 if num < compare_num: break else: return num result = find_max_num(input) print(result) # 프로그램 동작 정리.. # num = 3 < compare_num = 5 break # num = 5 < compare_num = 6 break # num = 6 시간 복잡도 ↓ (1 + 2N) input = [3, 5, 6, 1, 2, 4..

TIL] 동적 프로그래밍

동적 프로그래밍 동적 프로그래밍은 이름부터 생소하다. 동적 프로그래밍은 다이내믹 프로그래밍이라고도 부르고 동적 계획법이라 부르기도한다. 동적 프로그래밍의 원리는 주어진 문제를 풀기 위해서 문제를 여러 개의 하위 문제로 나누어 푼 다음 그것을 결합하여 최종적인 답을 구하는 것이다. 동적 프로그래밍의 장점 동적 프로그래밍의 장점으로는 하위 문제의 해결을 계산한 뒤 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 저장된 해결책을 재활용하여 간단하게 해결하여 내려가므로 계산 횟수를 줄일 수 있다. 저장된 해결책을 재활용하는 것을 메모 이제이 션이라고 부른다. 또한 프로그램을 구현할 때에 필요한 모든 가능성을 고려해서 구현하게 되기 때문에 동적 계획법을 이용하여 항상 최적의 결과를 얻을 수 있다. 동적 ..