[3주차] Data Structure 1/4 (배열, 연결 리스트)

배열

※ C++ 에서 배열 사이즈 구하기

int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
// 전체 배열 사이즈 / 원소 하나의 사이즈

1. 배열 회전 프로그램

A. 기본적인 회전 알고리즘 

void leftRotatebyOne(int arr[], int n) {
	int temp = arr[0], i;
    for (i = 0; i < n - 1; i++) {
    	arr[i] = arr[i + 1];
    }
    arr[i] = temp;
}

첫 번째 인덱스 값 temp에 저장
i가 0부터 n - 1까지 돌면서 arr[i]에 arr[i + 1] 값 저장
루프 다 돌고 나오면 temp에 저장되어 있던 arr[0] 값 arr[n] 에 저장

이 함수로 한 칸 씩 이동 가능
원하는 만큼 함수 호출해서 회전하기

 

B. 저글링 알고리즘

최대공약수(gcd)를 이용해 집합을 나누어서 여러 요소를 한꺼번에 이동시키는 것

void leftRotate(int arr[], int d, int n) // arr, 회전 개수, arr의 원소 개수
{ 
    for (int i = 0; i < gcd(d, n); i++) { 
       
        int temp = arr[i]; 
        int j = i; 
  
        while (1) { 
            int k = j + d; 
            if (k >= n) 
                k = k - n; 
  
            if (k == i) 
                break; 
  
            arr[j] = arr[k]; 
            j = k; 
        } 
        arr[j] = temp; 
    } 
}

// 좀 더 생각해보기

a) arr [] -> { 4 2 3 7 5 6 10 8 9 1 11 12}

b) arr [] -> {4 5 3 7 8 6 10 11 9 1 2 12}

c) arr [] -> {4 5 6 7 8 9 10 11 12 1 2 3 }

 

C. 역전 알고리즘

회전시키는 수에 대해 구간을 나누어 reverse로 구현하는 방법

 

d = 2이면

1,2 / 3,4,5,6,7로 구간을 나눈다.

 

첫번째 구간 reverse -> 2,1

두번째 구간 reverse -> 7,6,5,4,3

합치기 -> 2,1,7,6,5,4,3

 

합친 배열을 reverse -> 3,4,5,6,7,1,2

// swap을 통한 reverse
void reverseArr(int arr[], int start, int end){
    while (start < end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        start++;
        end--;
    }
}

// 구간을 d로 나누었을 때 역전 알고리즘 구현
void rotateLeft(int arr[], int d, int n){
	reverseArr(arr, 0, d-1);
	reverseArr(arr, d, n-1);
	reverseArr(arr, 0, n-1);
}

 

 

2. 배열의 특정 최대 합 구하기

예) arr[i] 가 있을 때, i * arr[i] 의 sum이 가장 클 떄 그 값을 출력하기 (회전하면서 최댓값을 찾아야 한다. )

int maxVal(int arr[], int n){
    
    int arrSum = 0; // arr[i]의 전체 합
    int curSum = 0; // i*arr[i]의 전체 합
    
    for(int i = 0; i < n; i++){
        arrSum = arrSum + arr[i];
        curSum = curSum + (i*arr[i]);
    }
    
    int maxSum = curSum;
    
    for (int j = 1; j < n; j++){
        curSum = curSum + arrSum - n*arr[n-j];
        // curSum 에 전체 합을 더하고 제일 많이 더해진 값 빼기
        // (0 * arr[0] + 1 * arr[1] + 2 * arr[2]) + (arr[0] + arr[1] + arr[2]) - 3 * arr[3 - 1]
        // = 0 * arr[2] + 1 * arr[0] + 2 * arr[1] 
        
        if ( curSum > maxSum )
            maxSum = curSum;
    }
    
    return maxSum;
    
}

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/code/maxvalue_array.cpp

 

3. 특정 배열을 arr[i] = i 로 재배열 하기

int fix(int A[], int len){
    
    for(int i = 0; i < len; i++) {
        
        
        if (A[i] != -1 && A[i] != i){ // A[i]가 -1이 아니고, i도 아닐 때
            
            int x = A[i]; // 해당 값을 x에 저장
            
            while(A[x] != -1 && A[x] != x){ // while 인게 중요함(한 루프가 끝날 때까지 반복됨)
            	// A[x]가 -1이 아니고, x도 아닐 때
                
                int y = A[x]; // 해당 값을 y에 저장
                A[x] = x; 
                
                x = y;
            }
            
            A[x] = x;
            
            if (A[i] != i){
                A[i] = -1; // 일단 A[i]를 -1로 지정(이후에 i에 해당하는 원소값이 나오면 수정될 것)
            }
        }
    }
    
}

 

---

 

Linked List

연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조 (배열은 연속적인 메모리 위치에 저장됨)

포인터를 사용해서 연결됨

각 노드는 데이터 필드와 다음 노드에 대한 참조(주소)를 포함하는 노드로 구성

 

왜 Linked List를 사용하는가?

배열의 단점

1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대한 할당을 받아야 함. 

2. 새로운 요소를 삽입하는 비용이 많이 듦(공간 만들고, 기존 요소를 전부 이동시켜야)

 

Linked List

장점

1. 동적으로 크기를 늘리거나 줄일 수 있다. 

2. 삽입과 삭제가 용이하다.

 

단점

1. 임의로 특정 요소에 엑세스할 수 없다. (첫 번째 노드부터 순차적으로 엑세스 해야 함 → 이진 검색 수행 불가능)

※ 이진 탐색: 정렬된 배열에서 중간 값과 찾고자 하는 값을 비교
                    같으면 종료, 크다면 오른쪽 구간을 대상으로 탐색, 작으면 왼쪽 구간을 대상으로 탐색

2. 포인터를 저장할 여분의 메모리 공간이 각 노드에 필요하다. 

 

노드의 구현

// A linked list node 
struct Node 
{ 
  int data; 
  struct Node *next; // 포인터
};

 

Single Linked List

class LinkedList{
    
    Node head;

    static class Node {
        int data;
        Node next;
        Node(int d) { // 생성자
            data = d; next = null;
        }
    }

    public void printList() 
    { 
        Node n = head; 
        while (n != null) 
        { 
            System.out.print(n.data+" "); 
            n = n.next; 
        } 
    }

    public static void main(String[] args){

        LinkedList llist = new LinkedList();

        llist.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
    
        llist.head.next = second; // 첫번째 노드에 두번째 노드 연결
        second.next = third; // 두번째 노드에 세번째 노드 연결        
        
        llist.printList(); 
    }
}

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/code/linked_list.java

 

노드 추가

// 앞쪽에 노드 추가

void push(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

 

// 특정 노드 다음에 추가

void insertAfter(struct Node* prev_node, int new_data){
    if (prev_node == NULL){
        printf("이전 노드가 NULL이 아니어야 합니다.");
        return;
    }

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;
    new_node->next = prev_node->next;

    prev_node->next = new_node;
    
}

 

// 끝 쪽에 노드 추가

void append(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    struct Node *last = *head_ref;

    new_node->data = new_data;

    new_node->next = NULL;

    if (*head_ref == NULL){
        *head_ref = new_node;
        return;
    }
   	// 빈 linked list일 경우

    while(last->next != NULL){
        last = last->next;
    }

    last->next = new_node;
    return;

}

 

---

 

Array  vs  ArrayList  vs  LinkedList

• Array는 index로 빠르게 값을 찾는 것이 가능하다. 
• LinkedList는 데이터의 삽입 및 삭제가 빠르다. 
• ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느리다. 

 

배열

선언할 때 크기와 데이터 타입을 지정해야 한다. 

메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조이므로

데이터가 계속 늘어날 때, 최대 사이즈를 알 수 없는 경우에는 사용하기 부적합하다. 

 

중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적이다. 

ex) 4번째 index 값에 새로운 데이터를 넣어야 할 경우

원래 값들을 뒤로 한 칸씩 밀고 해당 index에 값을 덮어씌워야 한다. 

 

단, index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 용이하다. 

 

ArrayList

크기가 정해져있지 않기 때문에, 데이터가 계속 늘어날 때도 사용 가능하다. 

index를 가지고 있어 검색도 빠르다. 

하지만, 중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재한다. 

 

LinkedList

한 노드에 연결된 노드의 포인터 위치를 가리키는 방식으로 되어있다. 

데이터의 중간에 삽입 및 삭제를 할 때 전체를 돌지 않아도

이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행 가능하다. 

 

하지만, index가 없어 검색에는 시간이 더 걸린다는 단점이 존재한다. 

 

따라서, 상황에 맞게 자료구ㅗ를 잘 선택해서 사용하는 것이 중요하다.