02 기본 자료구조

Do it 자료구조와 함께 배우는 알고리즘 입문 자바편을 읽고 정리한 내용입니다.

배열

자료구조

데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계

데이터 단위 : 데이터를 구성하는 한 덩어리

배열

같은 자료형의 변수로 이루어진 구성요소가 모인 자료구조

// 배열 선언
int[] a;
int a[];

// 길이가 5인 배열을 참조 - a의 자료형은 int[5]형
int a = new int[5];

// 초기화하며 배열 선언
int[] a = {1, 2, 3, 4};
int[] b = new int[] {1, 2, 3, 4}';

// 배열 복제
// - 복제한 배열에 대한 참조를 생성
int[] c = a.clone();

배열 요소의 최댓값 구하기

public class MaxOfArray {
  // 배열 요소의 최댓값을 구하는 메서드
  public static int maxOf(int[] a){
    int max = a[0];
    for(int i=1; i<a.length; i++){
      if(max < a[i])
        max = a[i];
    }
    return max;
  }

  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);

    System.out.println("키의 최댓값을 구합니다.");
    System.out.print("사람 수 : ");
    int num = scan.nextInt();

    int[] height = new int[num] // 요솟수가 num인 배열 생성

    for(int i=0; i<num; i++){
      System.out.print("height[" + i + "]: ");
      heught[i] = scan.nextInt();
    }
    System.out.println("최댓값은 " + maxOf(height) + "입니다.");
  }
}

주사(traverse) : 데이터를 하나씩 지나면서 조사하는 것, 베열의 요소를 하나씩 살펴보는 과정을 알고리즘 용어로 주사라고 한다.

배열 요소 역순으로 정렬하기

class ReversArray {
  // 두 배열 요소 교환
  static void swap(int[] a, int index1, int index2) {
    int t = a[index1];
    a[index1] = a[index2];
    a[index2] = t;
  }

  // 배열 요소 역순으로 정렬
  static void reverse(int[] a) {
    for(int i=0; i<a.length/2; i++){
      swap(a, i, a.length-i-1);
    }
  }

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    System.out.print("요솟수 : ");
    int num = scan.nextInt();

    int[] arr = new int[num];

    for(int i=0; i<num; i++){
      System.out.print("arr["+ i +"] : ");
      arr[i] = scan.nextInt();
    }

    reverse(arr);

    System.out.println("요소를 역순으로 정렬했습니다.");
    for(int i=0; i<arr.length; i++){
      System.out.print("arr["+ i +"] : " + arr[i]);
    }
  }
}

기수 변환

기수
: 기초가 되는 수
10진법에서는 0~9까지 정수
기수가 10 단위를 넘어가면 0~9까지의 정수와 알파벳 A, B, ...를 사용

기수로 변환하는 방법

• 임의의 정수를 n진수로 변환
  정수를 n으로 나눈 몫이 0이 될때까지 나머지를 구하고 그 나머지를 역순으로 늘어 놓은 숫자가 기수로 변환한 숫자이다.

class CardConvRev {
  // 정수 x를 r진수로 변환하는 메서드
  static int cardConvR(int x, int r, char[] d) {
    int digits = 0; // 변환한 수의 자릿수
    String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    do {
      d[digits++] = dchar.charAt(x % r); // x를 r로 나눈 나머지를 배열 d에 저장
      x /= r;
    }while (x!=0);
    return digits;
  }
}

• 위 코드에서 배열 d에는 나머지를 연산 순대로 저장했기 때문에 기수로 변환하기 위해서는 main에서 다시 역순으로 출력해야 한다.
  
  

소수의 나열

소수 : 자신과 1 이외의 정수로 나누어 떨어지지 않는 정수

// 1,000 이하의 소수 찾기
class PrimeNumber1 {
  public static void main(String[] args) {
    int counter = 0;

    for (int n = 2; n<= 1000; n++) {
      int i;
      for (i = 2; i < n; i++) {
        counter++;
        if (n % i == 0) // 나누어 떨어지면 소수가 아님
          break;
      }
      if (n == i)
        System.out.println(n);
    }
  }
}

게선 사항 1

정수 n이 소수인지 아닌지의 여부는 아래 조건을 만족하면 된다.

2 ~ n-1까지의 어떤 소수로도 나누어 떨어지지 않는다.

class PrimeNumber2 {
  public static void main(String[] args) {
    int ptr = 0;      // 찾은 소수의 개수
    int[] prime = new int[500];  // 찾은 소수를 저장하는 배열

    prime[ptr++] = 2; // 2는 소수이므로 prime[0]에 저장

    for(int n=3; n<=1000; n +=2) { // 홀수만
      int i;
      for(i=1; i<ptr; i++){   // 찾은 소수로 나눠서
        if(n % prime[i] == 0)   // 나누어 떨어지면 소수가 아님
          break;
      }

      if(ptr == i)  // 마지막 까지 나누어 떨어지지 않으면
        prime[ptr++] = n;  // 소수이므로 배열에 저장
    }

    // 찾은 소수 출력
    for(int i=0; i<ptr; i++){
      System.out.println(prime[i]);
    }
  }
}

개선 사항 2

100의 약수를 그림으로 나타내면 다음과 같다.

• 5 x 20이나 20 x 5나 가로, 세로를 다르지만 같은 직사각형이고, 10 x 10을 기준으로 대칭을 이루고 있다.
• 이를 소수를 구하는 알고리즘에 대입하면,
  정수 n의 소수를 구할 때 n의 제곱근을 한 변으로 하는 사각형 이후의 직사각형에 대한 계산량을 줄일 수 있다.
• 즉, 어떤 정수 n은 다음 조건을 만족하면 소수이다.

  n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

이때, n의 제곱근을 구하는 것보다 제곱을 구하는 것이 곱하기 연산을 사용하기 때문에 훨씬 간단하고 빠르다.

prime[i]의 제곱이 n 이하인가?

class PrimeNumber3 {
  public static void main(String[] args) {
    int ptr = 0;      // 찾은 소수의 개수
    int[] prime = new int[500];  // 찾은 소수를 저장하는 배열

    prime[ptr++] = 2; // 2는 소수이므로 prime[0]에 저장
    prime[ptr++] = 3; // 3은 소수이므로 prime[1]에 저장

    for(int n=5; n<=1000; n +=2) { // 홀수만
      boolean flag = false;
      for(int i=1; prime[i] * prime[i] <= n; i++){   // 소수의 제곱근이 n 이하 일때
        if(n % prime[i] == 0) { // 나누어 떨어지면 소수가 아님
          flag = true;
          break;
        }
      }

      if(!flag)  // 마지막 까지 나누어 떨어지지 않으면
        prime[ptr++] = n;  // 소수이므로 배열에 저장
    }

    // 찾은 소수 출력
    for(int i=0; i<ptr; i++){
      System.out.println(prime[i]);
    }
  }
}

다차원 배열

2차원 배열 = 배열의 배열
3차원 배열 = (배열의 배열)의 배열

// 2차원 배열의 선언
int[][] x = new int[2][4];

// 3차원 배열의 선언
long[][][] y = new long[2][3][4];

클래스

임의의 데이터형을 자유로이 조합하여 만들 수 있는 자료구조

class XYZ {
  int x;
  long y;
  double z;
}

클래스형 변수를 사용할 때는 먼저 클래스형 변수를 만들고 실체인 클래스 인스턴스 생성해야 한다.

XYZ a = new XYZ();

클래스 본체와 멤버

1. 클래스 본체에서는 다음과 같은 내용을 선언할 수 있다.

• 멤버(필드/메서드/중첩(nested)클래스/중첩(nested) 인터페이스)
• 클래스 초기화 / 인스턴스 초기화
• 생성자

2. 필드/메서드/생성자를 선언할 때 public/protected/private 등 접근 제한자를 지정할 수 있다.
3. 메서드/생성자는 다중으로 정의할 수 있다.(오버라이드)
4. final로 선언한 필드는 한 번만 값을 대입할 수 있다.
5. 생성자는 새로 생성한 인스턴스의 초기화를 위해 사용한다.