• 목차

배열

회전 배열

point!

• 돌리는 각도에 따라 배열 크기를 바꿔줘야 한다.

  • mxn 배열을 90도 돌리는 경우 → nxm 사이즈의 배열이 필요하다.

    int[][] rotateArray(int[][] arr) {
    	int n = arr.length;
      int m = arr[0].length;
      int[][] rotated = new int[m][n];
    
    	for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
            rotated[j][n-i-1] = arr[i][j];
          }
      }
    	return rateted
    }
    

  • 시계방향으로 90도 회전하는 경우 (i, j) 좌표는 (j, n-1-i) 좌표로 변환

  • 반시계방향으로 90도 회전하는 경우 (i, j) 좌표는 (n-1-j, i) 좌표로 변환

    (0,0) (0,1) (0,2) (0,3)		      (0,3) (1,3) (2,3) (3,3)
    (1,0) (1,1) (1,2) (1,3)				  (0,2) (1,2) (2,2) (3,2)
    (2,0) (2,1) (2,2) (2,3)		->		(0,1) (1,1) (2,1) (3,1)
    (3,0) (3,1) (3,2) (3,3)				  (0,0) (1,0) (2,0) (3,0)
    

정렬

선택 정렬(Selection Sort)

• 처음 인덱스 0부터 시작하여 나머지 원소들 중 최소값을 찾아서 위치를 교환하는 방식

  

• 정렬이 되지 않은 부분 중 가장 작은 값의 인덱스를 저장하는 변수(min_index)를 사용함.

• 시간 복잡도 : 최선, 최악, 평균 O(n^2)

• 예제

삽입 정렬(Insertion Sort)

• 정렬되지 않은 원소를 정렬된 부분에 삽입하는 방식

  

• 정렬된 부분은 첫번째 원소만이 들어있는 상태에서 시작하여, 한번에 하나씩 정렬되지 않은 부분에서 원소를 가져와 적절한 위치에 삽입함.

• 시간 복잡도 : 최선 O(n), 최악 O(n^2)

• 예제