자료구조 (자료구조, 빅오표기법, ArrayList)

자료구조

자료구조란?

• 한정된 메모리 공간 안에서 데이터 관리, 데이터 저장, 데이터 활용에 대한 것들의 분류 해놓은 것
  ( 배열, 스택, 큐, 리스트, 트리, 그래프 등)

자료구조를 왜 알아야 할까

• 자료의 양은 시간이 지날 수록 기하급수적으로 늘어가고 있다.
  테이터들을 효율적으로 사용하기 위해 관리하는 법을 배워야 장기적으로 좋은 개발을 할 수 있다.
  (자료구조들의 장점과 단점을 알고 어디에 어떻게 쓸지 적용 할 수 있다.)

---

빅오표기법(big-O notation)

• 알고리즘의 효율성을 표기해주는 표기법
• 데이터 개수(N)가 있을 때 사칙연산과 같은 기본 연산의 횟수를 의미
• 빅오표기법은 알고리즘의 시간복잡도와 공간복잡도를 나타내는데 사용
• 다른 표기법 대신 빅오 표기법을 사용하는 이유는 빅오표기법이 상한선을 기준으로 효율성을 표시하기 떄문
  (알고리즘 효율성은 값이 클수록 그래프가 위로 향할 수록 비효율적)
• 상수항을 무시, 영향력 없는 항 무시
• 공간복잡도는 과거보다 용량이 많이 늘어서 신경쓰지않는 추세
• 시간복잡도는 더욱 더 신경을 써야한다

빅오 표기법 예시

• O(1) : Stack의 push, pop
• O(log N) : 이진트리
• O(N) : for문
• O(N log N) : 퀵정렬, 병합정렬, 힙 정렬
• O(N²) : 이중 for문, 삽입정렬, 버블정렬, 선택정렬
• O(2ⁿ) : 파보나치 수열

---

ArrayList

배열

• 데이터 나열, 데이터에 인덱스를 대응시켜 구성한 데이터 구조
• 주로 ArrayList, LinkedList (차후에 다룬다) 사용

ArrayList

• 기존 배열 선언은 길이를 정하고 나중에 추가될 사항이 있어 배열의 개수가 길어지면 재할당을 하고 복사를 했다.
• ArrayList는 길이를 정하지 않고 사용할 수 있는 장점이 있다.
• ArrayList는 Generic 타입을 선언하여 사용하는게 좋다.
  (선언하지 않으면 Object를 상속 받기 때문에 어느타입이든 받을 수 있다.)
• 대체로 for문을 이용하여 출력한다.

예제

• ArrayList를 이용하여 전기자동차 부품의 테스트 항목을 출력하는 문제를 만들어 보았다. (순수 창작)
• 출력문은 다음과 같다.

BigCompany T사와 MiddleCompanyN사의  
2곳의 전기자동차 회사가 있습니다.
T사는 Tire와 Motor 2부품 테스트를 했고,  
H사는 Tire와 Steering Wheel, Motor 3부품 테스트를 했습니다.  
T사는 2부품 모두 통과했고, N사는 Tire에서 불합격을 받았습니다.  
두 회사의 테스트 결과를 출력하세요.

• 먼저 CarCompany 클래스를 작성하여 필요한 매개변수, 생성자, 메서드를 만들어준다.

package ArrayListTest;

import java.util.ArrayList;

public class CarCompany {

    String companyName;
    String companyType;
    ArrayList<Part> partList;

    public CarCompany(String companyName, String companyType) {
        this.companyName = companyName;
        this.companyType = companyType;

        partList = new ArrayList<Part>();
    }

    public void addPart(String name, String pass) {
        Part part = new Part();

        part.setName(name);
        part.setPass(pass);
        partList.add(part);
    }

    public void showCompanyInfo() {

        for (Part p : partList) {
            System.out.println(companyType + "," + companyName + "사 의 부품 테스트 항목은 " + p.getName() + " 이며 결과는 "
                    + p.getPass() + " 입니다.");

        }
    }
}

• 다음으로 Part 클래스를 private로 만들어 get,set 함수를 설정한다.

package ArrayListTest;

public class Part {

    private String name;
    private String pass;

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getPass() {
        return pass;
    }
    public void setPass(String pass) {
        this.pass = pass;
    }

}

• 원하는 결과값을 얻는 결과 클래스를 만든다.

package ArrayListTest;

public class TestResult {

    public static void main(String[] args) {
        CarCompany t = new CarCompany("BigCompany", "T사");

        t.addPart("Tire", "Pass");
        t.addPart("Moter", "Pass");

        CarCompany n = new CarCompany("MiddleCompany", "N사" );

        n.addPart("Tire", "Fail");
        n.addPart("Steering Wheel", "Pass");
        n.addPart("Motor", "Pass");

        t.showCompanyInfo();
        System.out.println();
        n.showCompanyInfo();

    }

}

• 결과

T사,BigCompany사 의 부품 테스트 항목은 Tire 이며 결과는 Pass 입니다.
T사,BigCompany사 의 부품 테스트 항목은 Moter 이며 결과는 Pass 입니다.

N사,MiddleCompany사 의 부품 테스트 항목은 Tire 이며 결과는 Fail 입니다.
N사,MiddleCompany사 의 부품 테스트 항목은 Steering Wheel 이며 결과는 Pass 입니다.
N사,MiddleCompany사 의 부품 테스트 항목은 Motor 이며 결과는 Pass 입니다.