알고리즘 스터디 Week3

18. 선형 자료 구조

1) 동적 배열

- 원소들은 메모리의 연속된 위치에 저장함

- 주어진 위치의 원소를 반환하거나 변경할 때 $O(1)$의 상수시간이 필요

- 배열의 크기를 변경하는 $resize()$ 연산이 가능하며, 배열의 크기 N에 대해 $O(N)$의 시간이 필요

- 주어진 원소를 배열의 맨 끝에 추가할 수 있으며, 이 때 $O(1)$의 상수시간이 필요

 

어떻게 구현할 지를 정리해보자.

 

1, 2, 3번의 조건을 달성하기 위해선 밑 코드에서 첫번째 $append()$ 함수로 가능하지만, 상수시간으로 append를 처리할 수 없게 된다. 항상, 배열의 크기 $O(N)$의 시간이 필요하다.

 

매번 원소를 추가할 때마다 복사를 하지 않기 위해서 두번째 $append()$와 같이 $capacity$라는 변수를 추가하고 $size$가 그보다 작을 때 상수시간이 될 수 있을 걸로 생각이 된다. 하지만 size가 capacity에 도달했을 때는 어떻게 해야하는지 아직 고민이다.

 

M이라는 적당히 큰 상수값을 지정해서 $size$가 $capacity$에 도달하면 $capcity$ -> $capacity + M$으로 업데이트하고 복사를 하는게 어떨까 생각해본다. $N$번의 삽입했을 때, 시간복잡도의 평균을 계산해보면 다음과 같다.

$$ \begin{align*} complexity& = {{N * O(1) + \sum_{ i=1 }^{ [N/M] }(i * M)} \over N} \\ & = {{N * O(1) + {{[N/M] \cdot ([N/M] - 1)} \over 2}} \over N} \\ & = {{O(N) + O(N^2)} \over N} \\ & = O(N) \end{align*} $$

상수값으로 증가하는 경우에도, $1/M$의 이득을 볼 수 있지만 상수시간 $O(1)$으로 삽입이 불가능하다.

 

그러면 $capacity$ -> $capacity * 2$로 업데이트하는 경우는 어떨까. 다시 N번의 추가한다 해보자.

$$ \begin{align*} complexity& = {{N * O(1) + \sum_{ i=1 }^{ [log_2 N] }(2^i)} \over N} \\ & = {{N * O(1) + 2^{[log_2 N] + 1} - 1} \over N}\\ & \leq {{N * O(1) + 4 * N} \over N} \\ & = O(1) \end{align*} $$

이와 같이, 2배로 증가하는 경우에는 $O(1)$의 평균시간을 가지게 되며 모든 조건을 만족할 수 있다. 이는 4번째 $append()$ 함수와 같다.

int size; // 배열의 크기
ElementType* array // 실제 배열을 가르키는 포인터

// array 동적할당에 여유가 없다면
void append(ElementType element) {
  ElementType* new_array = new ElementType[size + 1];
  for (int i=0; i<size; i++) {
    new_array[i] = array[i];
  }
  delete[] array;
  array = new_array;
  array[size++] = element;
}

// array 동적할당에 여유가 있음
int capacity;
void append(ElementType element) {
  if (size < capacity) {
    new_array[size++] = element;
  } else {
    // how?
  }
}

// 상수 M만큼 추가 할당
void append(ElementType element) {
  if (size == capacity) {
    capacity = capacity + M;
    ElementType* new_array = new ElementType[capacity];
    for (int i=0; i<size; i++) {
      new_array[i] = array[i];
    }
    delete[] array;
    array = new_array;
  }
  array[size++] = element;
}

// capacity만큼 추가 할당
void append(ElementType element) {
  if (size == capacity) {
    capacity = capacity * 2;
    ElementType* new_array = new ElementType[capacity];
    for (int i=0; i<size; i++) {
      new_array[i] = array[i];
    }
    delete[] array;
    array = new_array;
  }
  array[size++] = element;
}​

그리고 C++에서 동적배열은 std::vector로 STL에 정의가 되어 있는데, 실제 사용해보면 재할당 때문에 정적배열에 비해 오랜시간이 걸리는 것을 알 수 있다. 이 때는 다음과 같은 구현을 추천한다. reserve()는 미리 동적배열의 capacity를 지정해는주는 함수이므로 미리 크기를 알고 있다면, 더 빠르게 std::vector의 원소를 구성시킬 수 있다.

#include <vector>

int input_num = 10000000;

{
  std::vector<int> dynamic_array;
  for (int i=0; i<input_num; i++) {
    dynamic_array.emplace_back(i);
  }
}

// Faster
{
  std::vector<int> dynamic_array;
  dynamic_array.reserve(input_num);
  for (int i=0; i<input_num; i++) {
    dynamic_array.emplace_back(i);
  }
}​

 

2) 연결리스트

- 특정 위치의 삽입, 삭제가 상수시간 $O(1)$에 이루어짐

- 특정 위치 접근은 선형시간 $O(N)$에 이루어짐

이러한 구조로 구현되고 이를 Doubly Linked List라고 부른다. 삽입, 삭제 시에는 prev와 next를 수정해줌으로써 상수시간에 처리한다.

struct ListNode {
  ElementType element;
  ListNode* prev, next;
};

ListNode* head, tail

연결리스트의 경우, 통째로 잘라서 옮기는 splicing 연산이 가능하다. i-1번째 <-> i번째, j번째 <-> j+1번째 노드의 연결들을 끊고 i-1번째와 j+1번째를 연결하고 i번째와 j번째는 옮기려는 곳에 연결하면 된다.

 

19. 큐, 스택, 데크(deque)

동적배열을 circular buffer((start + index)%capacity을 index로써 접근)에 넣고, 원하는 구조의 포인터(실제 포인터는 아니고 인덱스)들을 구현하면 됨. 큐의 경우 front와 rear를 구현하고, deque의 경우 head와 tail 그리고 stack의 경우 top을 구현하면 된다. 활용한 간단한 문제에 집중하여 활용에 집중하는게 좋아 보임.

 

https://algospot.com/judge/problem/read/BRACKETS2

https://algospot.com/judge/problem/read/ITES

 

문제풀이

https://algospot.com/judge/problem/read/CHRISTMAS

#include <cstdio>
#include <vector>
#include <algorithm>

#define ZERO_INCLUDE_MAX_SIZE 100001
#define MAX_SIZE 100000

int n, m[ZERO_INCLUDE_MAX_SIZE], k;
int psum[ZERO_INCLUDE_MAX_SIZE];
int sub_max[ZERO_INCLUDE_MAX_SIZE];

// k related
int prev[MAX_SIZE];
int64_t count[MAX_SIZE];

void GetInput() {
    scanf("%d %d", &n, &k);
    for (int i=1; i<=n; i++) {
        scanf("%d", &(m[i]));
    }
}

void BuildPartSum() {
    psum[0] = 0;
    for (int i=1; i<=n; i++) {
        psum[i] = (psum[i-1] + m[i]) % k;
    }
}

int SolveOneOrder() {
    for (int i=0; i<k; i++) {
        count[i] = 0;
    }

    for (int i=0; i<=n; i++) {
        count[psum[i]]++;
    }

    int64_t result = 0;
    for (int i=0; i<k; i++) {
        result += (count[i] * (count[i] - 1)) / 2;
    }
    return result % 20091101;
}

int SolveMultipleOrder() {
    // -1 is not visited
    for(int i=0; i<k; i++) {
        prev[i] = -1;
    }
    prev[psum[0] % k] = 0;

    sub_max[0] = 0;
    for (int i=1; i<=n; i++) {
        if (prev[psum[i]] < 0) {
            sub_max[i] = sub_max[i-1];
        } else {
            sub_max[i] = std::max(sub_max[i-1], sub_max[prev[psum[i]]] + 1);
        }
        prev[psum[i]] = i;
    }
    return sub_max[n];
}

int main(void) {
    int c;
    scanf("%d", &c);
    for (int i=0; i<c; i++) {
        GetInput();
        BuildPartSum();
        printf("%d %d\n", SolveOneOrder(), SolveMultipleOrder());
    }
    return 0;
}

문제풀이

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

#include <cstdio>
#include <algorithm>

int CountTrueBits(int64_t num) {
  int count = 0;
  while (num > 0) {
    count += num % 2;
    num = num >> 1;
  }
  return count;
}

int main() {
  int m, n;
  scanf("%d %d", &m, &n);

  int64_t board[m];
  for(int i=0; i<m; i++) {
    char c = getchar();
    int64_t line = 0;
    for (int j=0; j<n; j++) {
      c = getchar();
      line = line << 1;
      if (c == 'B') {
        line += 1;
      }
    }
    board[i] = line;
  }

  int min_paint = 987654321;

  int64_t checker_row[2];
  checker_row[0] = (1 << 6) + (1 << 4) + (1 << 2) + 1;
  checker_row[1] = checker_row[0] << 1;
  int64_t mask = (1 << 8) - 1;
  // i: col pos, j: row pos
  for (int i=7; i<n; i++) {
    // paint_row[0]: B is top-left, paint_row[1]: W is top-left
    int paint_row[2][m];
    for (int j=0; j<m; j++) {
      for (int k=0; k<2; k++) {
        paint_row[k][j] = CountTrueBits((board[j] & (mask << (n - i - 1))) ^ (checker_row[(j + k) % 2] << (n - i - 1)));
      }
    }

    int paint_sum[2] = {0};
    for (int j=0; j<8; j++) {
      for (int k=0; k<2; k++) {
        paint_sum[k] += paint_row[k][j];
      }
    }
    for (int k=0; k<2; k++) {
      min_paint = std::min(min_paint, paint_sum[k]);
    }

    for (int j=8; j<m; j++) {
      for (int k=0; k<2; k++) {
        paint_sum[k] -= paint_row[k][j - 8];
        paint_sum[k] += paint_row[k][j];
        min_paint = std::min(min_paint, paint_sum[k]);
      }
    }
  }
  printf("%d", min_paint);
  return 0;
}

 

참조 및 출처: 알고리즘 문제해결전략 2 (구종만)