[프로세싱(Processing) : 고급] 알고리즘과 최적화

1. 알고리즘과 최적화

 

1.1 복잡도 이론

복잡도 이론은 알고리즘의 효율성을 분석하는 이론입니다. 알고리즘의 시간 복잡도는 입력 크기에 대한 알고리즘의 실행 시간을, 공간 복잡도는 메모리 사용량을 의미합니다. 대표적으로 빅오(O) 표기법을 사용해 복잡도를 표현합니다.

 

1.2 정렬 및 검색 알고리즘

정렬 알고리즘은 데이터를 특정 순서로 정렬하는 알고리즘입니다. 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있습니다. 검색 알고리즘은 원하는 데이터를 찾는 알고리즘으로 선형 검색, 이진 검색 등이 있습니다.

 

1.3 그래프 이론과 경로 찾기

그래프 이론은 정점(Vertex)과 간선(Edge)으로 이루어진 그래프를 다루는 이론입니다. 경로 찾기 알고리즘은 그래프에서 한 정점에서 다른 정점으로 가는 최단 경로를 찾는 알고리즘입니다. 대표적으로 다익스트라(Dijkstra) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘, 플로이드-워셜(Floyd-Warshall) 알고리즘이 있습니다.

 

1.4 프로세싱에서의 성능 최적화

프로세싱에서의 성능 최적화는 코드 실행 시간을 줄이고, 메모리 사용량을 최소화하는 것을 목표로 합니다. 불필요한 연산을 줄이거나, 이미 계산된 결과를 재사용하거나, 병렬 처리를 사용하는 등의 기법을 활용할 수 있습니다.

---

예제: 버블 정렬 알고리즘을 사용한 정렬

// 버블 정렬 함수
void bubbleSort(int[] arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 원소를 서로 바꿈(swap)
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

void setup() {
  int[] arr = {64, 34, 25, 12, 22, 11, 90};
  bubbleSort(arr);
  println("정렬된 배열: " + Arrays .toString(arr));
}

// 출력: 정렬된 배열: [11, 12, 22, 25, 34, 64, 90]

 

예제: 다익스트라 알고리즘을 사용한 최단 경로 찾기

final int INF = 1000000;
int[][] graph = { 
  {0, 10, INF, INF, INF, 5},
  {INF, 0, 1, INF, 2, INF},
  {INF, INF, 0, 20, INF, INF},
  {50, INF, INF, 0, INF, INF},
  {INF, INF, 10, INF, 0, 20},
  {INF, 3, INF, 2, INF, 0}
};

void dijkstra(int start) {
  int n = graph.length;
  boolean[] visited = new boolean[n];
  int[] dist = new int[n];

  Arrays.fill(dist, INF);
  dist[start] = 0;

  for (int i = 0; i < n - 1; i++) {
    int minDist = INF;
    int minIndex = -1;

    // 최소 거리를 가진 정점 찾기
    for (int j = 0; j < n; j++) {
      if (!visited[j] && dist[j] < minDist) {
        minDist = dist[j];
        minIndex = j;
      }
    }

    visited[minIndex] = true;

    // 선택한 정점을 통해 다른 정점까지의 거리 업데이트
    for (int j = 0; j < n; j++) {
      if (!visited[j] && graph[minIndex][j] != INF && dist[minIndex] + graph[minIndex][j] < dist[j]) {
        dist[j] = dist[minIndex] + graph[minIndex][j];
      }
    }
  }

  println("정점 " + start + "에서 다른 정점까지의 최단 거리: " + Arrays.toString(dist));
}

void setup() {
  dijkstra(0);
}

// 출력: 정점 0에서 다른 정점까지의 최단 거리: [0, 8, 9, 7, 10, 5]

 

이 두 예제는 각각 버블 정렬 알고리즘을 사용한 정렬과 다익스트라 알고리즘을 사용한 최단 경로 찾기를 보여줍니다. 이러한 알고리즘들을 프로세싱에서 사용하면 더 효율적인 코드를 작성하고, 성능 최적화를 도모할 수 있습니다. 또한, 알고리즘을 이해하고 다양한 문제에 적용함으로써 고급 프로세싱 기술을 습득할 수 있습니다.