양방향 연결리스트 구현하기

양방향 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고 있는 연결 리스트의 한 종류입니다. 각 노드는 데이터와 두 개의 포인터(다음 노드를 가리키는 next 포인터와 이전 노드를 가리키는 prev 포인터)로 구성되어 있습니다. 이러한 구조로 인해 양방향 연결 리스트는 단방향 연결 리스트와 달리 노드의 이전 노드를 쉽게 접근할 수 있습니다. 양방향 연결 리스트의 특징: 노드 구성: 각 노드는 데이터 필드와 두 개의 포인터(다음 노드를 가리키는 next 포인터와 이전 노드를 가리키는 prev 포인터)로 이루어져 있습니다. 양방향 이동: 단방향 연결 리스트와 달리, 양방향 연결 리스트는 노드의 이전 노드를 가리키는 prev 포인터를 통해 역방향으로 이동할 수 있습니다. 이..

• format_list_bulleted Algo 개념
• · 2023. 8. 5.
• textsms

DP - LIS(최장 증가 수열) 및 0-1 Knapsack 개념 (JAVA)

최장 증가 부분 수열(LIS) 최장 증가 부분 수열이란? 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로, 순서를 유지한 채 몇 개의 숫자들을 뽑아서 부분 수열을 만들 수 있다. 이렇게 만들 수 있는 부분 수열 중 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어, [6, 2, 1, 4, 3, 5]라는 수열이 있다면마지막 원소 5를 붙일 거라면, 5보다 앞에 있고, 5보다 작은 수로 끝나는 가장 긴 부분 수열에 붙이는 것이 좋다. [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이다. (여러 개 일 수 있다. ) DP를 활용하여 O(N²)으로 구해보기 배열의 숫자를 하나씩 살펴..

• format_list_bulleted Algo 개념
• · 2023. 7. 16.
• textsms