최소 회전수 구하는 알고리즘 | Algorithm for minimum rotation

최소 회전수 구하는 알고리즘 ❘ Algorithm for minimum rotation

get_min_rotate 함수는 두 개의 스택을 조작하는 알고리즘에서 스택 B의 원소를 스택 A로 옮기기 위해 필요한 최소 회전 수를 계산하는 역할을 합니다. 이 함수는 스택 B의 각 원소에 대해 스택 A에서의 위치와 스택 B에서의 위치를 비교하여, 최적의 회전 수를 찾습니다.

매개변수 설명

• t_var *stacks: 스택 A와 B의 정보를 포함하는 구조체 포인터입니다. 이 구조체는 스택의 크기와 각 스택의 노드에 대한 포인터를 포함합니다.
• int *a: 스택 A에서의 위치를 저장할 포인터입니다. 이 값은 스택 B의 원소를 스택 A로 옮기기 위해 필요한 회전 수를 결정하는 데 사용됩니다.
• int *b: 스택 B에서의 위치를 저장할 포인터입니다. 이 값은 스택 B의 원소를 스택 A로 옮기기 위해 필요한 회전 수를 결정하는 데 사용됩니다.

함수 동작 과정

1. 변수 초기화:
   • a_location, b_location: 각각 스택 A와 B에서의 위치를 저장하는 변수입니다.
   • idx: 스택 B의 원소를 순회하기 위한 인덱스입니다.
   • b_node: 스택 B의 첫 번째 원소를 가리키는 포인터입니다.
   • num: 현재 스택 B의 원소 값을 저장하는 변수입니다.
2. 스택 B 순회:
   • while (idx < stacks->b_size): 스택 B의 모든 원소를 순회합니다.
   • num = b_node->val: 현재 노드의 값을 가져옵니다.
   • a_location = find_a_location(num, stacks): 현재 스택 B의 원소가 스택 A에서 위치해야 할 곳을 찾습니다.
3. 위치 계산:
   • if (idx >= (stacks->b_size + 1) / 2): 현재 인덱스가 스택 B의 중간 이상인지 확인합니다.
     • 중간 이상일 경우, b_location은 스택 B의 끝에서부터의 위치를 나타내기 위해 음수로 설정됩니다.
   • 그렇지 않으면, b_location은 현재 인덱스와 같습니다.
4. 최소 회전 수 결정:
   • if (idx == 0 || get_bigger(*a, *b, a_location, b_location)): 첫 번째 원소이거나, 현재 계산된 위치가 이전에 저장된 위치보다 더 큰 경우에만 업데이트합니다.
     • *a와 *b에 각각 스택 A와 B에서의 최적 위치를 저장합니다.
5. 다음 노드로 이동:
   • b_node = b_node->right: 스택 B의 다음 노드로 이동합니다.
   • idx++: 인덱스를 증가시켜 다음 원소로 넘어갑니다.

결론

get_min_rotate 함수는 스택 B의 각 원소에 대해 스택 A에서의 최적 위치를 찾고, 이를 통해 최소 회전 수를 계산하여 스택 A로의 효율적인 이동을 가능하게 합니다. 이 과정은 스택 정렬 알고리즘에서 중요한 역할을 하며, 최적화된 회전 수를 통해 전체 알고리즘의 성능을 향상시킵니다.

 

 

Function Purpose
The get_min_rotate function calculates the minimum number of rotations needed to move elements from stack B to stack A in a stack manipulation algorithm. It compares the positions of each element in stack B with their corresponding positions in stack A to find the optimal rotation count.

Parameter Explanation

• t_var *stacks: A pointer to a structure that contains information about stacks A and B. This structure includes the sizes of the stacks and pointers to the nodes of each stack.
• int *a: A pointer to store the position in stack A. This value is used to determine the number of rotations needed to move an element from stack B to stack A.
• int *b: A pointer to store the position in stack B. This value is used to determine the number of rotations needed to move an element from stack B to stack A.

Function Operation Process

1. Variable Initialization:
   • a_location, b_location: Variables to store the positions in stacks A and B, respectively.
   • idx: An index used to iterate through the elements of stack B.
   • b_node: A pointer that points to the first element of stack B.
   • num: A variable to store the value of the current element in stack B.
2. Iterating Through Stack B:
   • while (idx < stacks->b_size): Iterates through all elements in stack B.
   • num = b_node->val: Retrieves the value of the current node.
   • a_location = find_a_location(num, stacks): Finds the position where the current element from stack B should be in stack A.
3. Position Calculation:
   • if (idx >= (stacks->b_size + 1) / 2): Checks if the current index is greater than or equal to the middle of stack B.
     • If it is, b_location is set to a negative value to represent the position from the end of stack B.
   • Otherwise, b_location is set to the current index.
4. Determining Minimum Rotation Count:
   • if (idx == 0 || get_bigger(*a, *b, a_location, b_location)): Updates the positions only if it is the first element or if the currently calculated position is greater than the previously stored position.
     • Updates *a and *b with the optimal positions in stacks A and B, respectively.
5. Moving to the Next Node:
   • b_node = b_node->right: Moves to the next node in stack B.
   • idx++: Increments the index to proceed to the next element.

Conclusion

The get_min_rotate function finds the optimal position for each element in stack B in stack A and calculates the minimum rotation count, enabling efficient movement to stack A. This process plays a crucial role in stack sorting algorithms, enhancing the overall performance through optimized rotation counts.