최솟값을 찾아서 첫번 째 인덱스에 넣고, 그 이후 남은 값 중 최솟값을 찾아서 다시 다음 인덱스에 넣어 하나씩 정렬하는 방식

![] (https://blog.kakaocdn.net/dn/bekAxf/btqBWrh1Sjl/AAVyKUtExiy6pdwfbhgR3k/img.gif)

int main(void)
{
    int nums[10] = {50, 30, 90, 100, 20, 10, 40, 80, 60, 70};

    for (int i = 0; i < 10-1; ++i) {
        for (int j = i + 1; j < 10; ++j) {
            if (nums[i] > nums[j]) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
    }
    return 0;
}

시간복잡도 : O(n^2)

버블 정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

두 원소를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환

void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

시간 복잡도 : O(n^2)

삽입 정렬

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교, 제 위치를 찾아 삽입

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

시간 복잡도 : O(n^2)

출처 : https://devuna.tistory.com/28 https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

자료의 삽입,삭제에 중점인 선형구조와 다르게, 자료의 표현에 중점을 맞춘 것 하나의 자료 뒤에 여러개의 자료가 존재하는 형태

트리

Node와 Branch를 이용해 사이클로 이루어지지 않도록 구성된 그래프

Node(노드) : 트리의 기본 요소, data와 다른 Branch 정보를 합친 것 Branch(가지) : 노드와 노드를 연결하는 간선 Degree(차수) : 각 노드에서 뻗어나온 가지의 수 Level(레벨) : Root Node의 레벨이 1로 가정하면 자식 Node로 갈 수록 +1이 된다.

트리의 특징

• 방향성 존재
• Node는 어떤 자료형으로도 표현 가능
• 사이클 존재 불가
• Node가 N개인 트리는 항상 N-1개의 Branch를 가짐

이진 트리

각 Node가 최대 두 개의 자식 Node를 갖는 트리 모든 Node가 왼쪽 자식 Node <= n <= 오른쪽 자식 Node 라는 특정 순서를 모두 따르는 이진 트리

완전 이진트리

마지막 Level을 제외하고 모든 Level이 완전히 채워져 있는 트리

균형 이진트리

모든 Node가 0개 또는 2개 자식 Node 갖는 트리

포화 이진트리

균형이진 트리이면서 완전 이진트리 모든 단말 Node는 같은 Level, 모든 내부 Node는 두 개의 자식 Node

균형 트리 (B-Tree)

레드블랙트리, AVL트리가 일종, 시간복잡도 O(logN)에 삽입, 찾기 등이 가능한 균형 잡힌 트리

그래프

Node와 Node를 연결하는 Edge(간선)를 하나로 모아 놓은 자료구조 연결되어 있는 객체 간의 관계를 표현할 수 있음

Node(정점) : 데이터의 위치를 나타내는 개념 Edge(간선) : Node를 연결하는 선 인접 정점 : Edge에 의해 직접 연결된 정점 Degree(차수) : 무방향 그래프에서 하나의 Node에 인접한 Node의 수 - in-Degree(진입 차수) : 방향 그래프에서 외부에서 오는 Edge 수 - out-Degree(진출 차수) : 방향 그래프에서 외부로 향하는 Edge 수

그래프의 특징

• 네트워크 모델
• 2개 이상의 경로가 가능
• 부모 - 자식 관계 개념이 없음
• 방향 그래프 / 무방향 그래프 구분 됨

가중치 그래프

Edge에 비용이나 가중치가 할당된 그래프

무방향 그래프

Edge를 통해 양방향으로 갈 수 있음 Node A와 Node B를 연결하는 Edge는 (A,B) 또는 (B,A) 와 같이 Node의 쌍으로 표현

방향 그래프

Edge에 방향성이 존재하는 그래프

비연결 그래프

무방향 그래프에서 특정 Node 쌍 사이에 경로가 존재하지 않는 그래프

연결 그래프

무방향 그래프에 있는 모든 Node쌍에 대해서 항상 경로가 존재하는 경우

트리가 해당 됨

비순환 그래프

사이클이 없는 그래프

순환 그래프

단순 경로의 시작 Node와 종료 Node가 동일한 그래프

완전 그래프

그래프에 속해 있는 모든 Node가 서로 연결 되어 있는 그래프

무방향 완전 그래프의 Node 수 n일 때 Edge 수 n*(n-1)/2

자바 엔터프라이즈 개발을 편리하게 해주는 *오픈소스 경량급 어플리케이션 프레임워크 *

어플리케이션 프레임워크

특정 계층이나 기술, 업무 분야에 국한되지 않고 전 영역을 포괄하는 범용적인 프레임워크 개발의 전 과정을 빠르고 편리하며 효율적으로 진행하는데 일차적인 목표를 둡니다.

일반적으로 라이브러리나 프레임워크는 특정 업무 분야나 한 가지 특화된 목표를 가지고 만들어졌습니다.

전 영역에 일관된 프로그래밍 모델을 제공해, 개발을 편리하게 해주는 프레임워크

경량급

코드에 불필요하게 등장하던 프레임워크와 서버환경에 의존적인 부분을 제거해주기 때문에 경량급이라고 칭합니다.

Spring 은 EJB의 단점을 보안해서 나온 프레임워크 이전, EJB(Enterprise JavaBeans)의 경우, spring과 같이 분산 처리, 트랜잭션, ORM인 Entity Bean까지 다양한 기능을 제공

하지만, 하나의 기능을 구현하기 위해 클래스간 상속, 인터페이스의 구현 등 클래스 간 의존도가 커지는 상황이 생김

EJB 의 단점

• 설정의 어려움
• 비즈니스 로직에 특정 기술이 종속 됨
• EJB의 동작을 위해서, 무거운 자바 서버(WAS) 가 필요
• 고가의 제품으로 구성된 개발환경에서만 개발 가능

그로인해, POJO (Plain Old Java Object) 인, 일반 자바 클래스를 활용해 단순하지만 EJB에서 제공했던 기술들을 제공하는 Spring을 창시합니다.

스프링 주요 특징

컨테이너 역할을 수행

스프링 컨테이너는 객체의 사이클을 관리하고, 컨테이너로부터 필요한 객체를 가져와 사용 가능

의존성 주입 ( DI : Dependency Injection )

객체가 의존하는 또 다른 객체를 외부에서 선언하고 이를 주입받아 사용하는 것

public class PetOwner{
    private AnimalType animal;

    public PetOwner(){
        this.animal = new Dog();
    }
}

PetOwner는 AnimalType에 의존성을 가짐 생성자를 통해 Dog 객체를 생성했기 때문이다.

이 경우, 의존성의 위험함이 따라온다.

• Tight Coupling이 생기며, AnimalType 객체 변경 시, PetOwner 객체도 변경된다.
• 하나의 모듈이 변경되면 의존한 다른 모듈까지 변경되어야 한다.
• Unit Test 작성에 어려움이 생긴다.

의존성을 줄이기 위한 방법

• setter Injection

  • setter 메소드를 통해 의존관계에 있는 객체 주입
  • property 태그를 통해 의존관계에 있는 bean을 주입

• Construction Injection

  • 생성자를 통해 의존관계에 있는 객체 주입
  • constructor arg 태그를 통해 의존관계에 있는 객체를 생성자를 통해 주입

예시

package Coffe;

public class Employee {

    public Coffee coffee;
    public Employee(Coffee coffee) {
        this.coffee = coffee;

    }
    public void takeout() {
        coffee.howmuch();

    }
}

현재 Employee는 Coffee와 의존성이 존재하며, 생성자를 통해 의존관계를 주입받고 있다.

package Coffe;

public interface Coffee {
    public void howmuch();

}

package Coffe;

public class Americano implements Coffee{
    String price;

    public void setPrice(String money) {
        this.price = money;

    }

    public void howmuch() {

        System.out.println("아메리카노의 가격은 " + price);

    }

}

package Coffe;

public class latte implements Coffee{
    String price;

    public void setPrice(String money) {
        this.price = money;

    }

    public void howmuch() {

        System.out.println("라떼의 가격은 " + price);
    }
}

다음과 같이 Coffee를 상속 받는 Latte, Americano 클래스가 생성되었다.

applicationCtx.xml

<?xml version="1.0" encoding="UTF-8"?>

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd">

    <bean id="americano" class="Coffe.Americano">
        <property name = "price"  value = "1000"> </property>
    </bean>

    <bean id="latte" class="Coffe.latte">
        <property name = "price"  value = "3000"></property>
    </bean>

    <bean id = "employee" class = "Coffe.Employee">
        <!-- 내가 먹고 싶은 커피 객체를 지정한다. -->
        <constructor-arg ref = "americano"></constructor-arg>

    </bean>
</beans>  

위와 같이 xml을 통해서 americano, latte 객체를 생성하며 employee객체에 constructor-arg 태그를 통해서 americano 객체를 생성자를 통해 의존성 주입을 해준다.

@Autowired 스프링에서 DI를 위해 사용되는 어노테이션이다. Bean 인스턴스가 생성된 후, @Autowired를 설정한 메서드가 자동으로 호출되고, 인스턴스가 자동으로 주입된다. @Autowired는 변수, Setter, 생성자, 일반 메서드에 적용 가능하며, property, constructor-arg 태그와 동일 역할을 한다.

관점 지향 프로그래밍 ( AOP : Asepct-Oriented Programming )

트랜잭션이나 로깅, 보안과 같이 여러 모듈에서 공통적으로 사용하는 기능의 경우 해당 기능을 분리하여 관리한다.

개발자가 비즈니스 로직에만 집중 가능하게 해준다.

POJO 지원 ( POJO : Plain Old Java Object )

객체간의 관계를 구성할 때, 일반적인 Java 코드를 이용해 객체를 구성할 수 있음 객체 구성시, 특정 인터페이스를 구현하거나, 특정 클래스 상속 미필요

스프링 프레임워크 구조

• 논리적 순서 === 물리적 순서

• Index 통한 원소접근 용이

• 구현 쉬움

• 리스트 크기 제한

• 삽입, 삭제 등 연산에 대한 Cost가 높음

  삽입, 삭제의 경우 순서를 맞추기 위해서 Shift 연산이 필연적이기 때문이다.

연결리스트 (LinkedList)

• 배열의 Cost 높은 비효율성을 극복하고자 등장

• 논리적 순서 !== 물리적 순서

  LinkedList는 각 원소가 다음 논리적 Index위치에 해당하는 물리적 주소를 가지고 있다. 따라서, 삽입, 삭제 시, 물리적 주소에 대해 변경만 해주면 된다.

• 리스트 크기에 영향 없이 데이터 삽입,삭제 가능

• 원하는 Index를 참조하려면, 1번 Index부터 차례대로 접근해야 해당 Index를 찾을 수 있음.

단일 연결리스트

data와 next(포인터)로 구성된 한방향 연결 리스트 첫 번째 원소에서 시작해야 리스트를 종주 가능

이중 연결리스트

단일 연결리스트의 단점을 극복하고자 등장 next(포인터)외에도 prev(포인터)의 존재 등장

더 많은 메모리 사용 어느 원소에서 시작해도 리스트를 종주 가능

원형 연결리스트

머리나, 꼬리가 존재하지 않음 다음 원소를 가리키는 포인터 레퍼런스에는 반드시 null이 아닌 어떤 원소가 들어감

시작점을 제대로 추적하지 않으면 무한루프 가능성 존재

스택 (Stack)

LIFO (Last In First Out), 마지막에 들어간 것이 가장 먼저 나오는 자료구조 Push, Pop 을 통해 데이터를 삽입,삭제 여러개의 하위 작업으로 나눌 수 있는 작업을 관리할때 유용하게 쓰임

서브루틴에서 사용할 반환 주소, 매개변수, 지역변수 등을 추적

List로 구현하면 객체를 제거해야하는 작업이 필요 Array로 구현하면 삭제할 필요없이 Index를 줄이고 초기화만 하면됨

Array로 구현하는 것이 더 좋음

큐 (Queue)

FIFO (First In First Out), 먼저 들어간 것이 가장 먼저 나오는 자료구조

Array로 구현하면 poll 연산 이후, 객체를 앞당기는 작업 필요 List로 구현하면 객체 1개만 제거 하면 됨

삽입, 삭제 용이한 LinkedList로 구현하는 것이 더 좋음

데이터를 구조적으로 표현하는 방식과 구현하기 위해 필요한 알고리즘에 대해 논하는 기초이론

큰 데이터를 어떤 구조로 저장, 탐색, 삭제해야 가장 효율적인가? 어떻게 메모리를 가장 효율적으로 사용할 수 있을까?

자료구조와 알고리즘의 관계

자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조 알고리즘은 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임

자료구조의 특징

• 효율성 : 데이터를 목적에 맞게 효율적으로 관리 및 사용
• 추상화 : 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추림
• 재사용성 : 다양한 프로그램에서 동작할 수 있도록 범용성있게 설계

자료구조의 분류

• 단순 구조

  정수, 실수, 문자, 문자열

• 선형 구조

  순차리스트, 연결리스트(단순 / 이중 / 원형), 스택, 큐, 덱

• 비선형 구조

  트리(일반, 이진), 그래프(방향, 무방향)

• 파일 구조

  순차, 색인, 직접 파일