12/20 금요일

1. 알고리즘

   • 코드 플러스

     • 스택수열, VPS 괄호 문제 학습 및 포스팅

삽입정렬

삽입정렬

• 기준이 되는 원소보다 앞에 존재하는 원소들과 비교하여 정렬하는 알고리즘
• 최선의 경우 시간복잡도는 O(n) : 이미 정렬되어 있는 경우
• 최악의 경우 시간복잡도는 O(n^2) : 반대로 정렬되어 있는 경우
• 추가 공간이 필요하지 않다

//pseudocode
InsertionSort(A){
  for(i=2 to A.length){
    key = A[i];
    // A[i]를 정렬된 배열 A[1..j-1]에 삽입한다
    j=i-1;
    while(j>0 && A[j] > key){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=key;
  }
}

최악의 경우 시간복잡도가 O(n^2)인 이유는 while절 연산 횟수 때문이다.

Java로 삽입정렬 구현

• 테스트 코드

import org.junit.jupiter.api.Test;
import java.util.Arrays;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;

class InsertionSortTest {

    @Test
    public void testBestTimeComplexity(){

        int[] input = new int[]{1,2,3,4,5};
        int[] answer = Arrays.copyOf(input,input.length);
        Arrays.sort(answer);

        InsertionSort.insertionSort(input);
        assertArrayEquals(input,answer);
    }

    @Test
    public void testUnsortedArray(){

        int[] input = {64,34,25,12,22,11,90};
        int[] answer = Arrays.copyOf(input,input.length);
        Arrays.sort(answer);

        InsertionSort.insertionSort(input);
        assertArrayEquals(input,answer);
    }

    @Test
    public void testWorstTimeComplexity(){

        int[] input = {5,4,3,2,1};
        int[] answer = Arrays.copyOf(input,input.length);
        Arrays.sort(answer);

        InsertionSort.insertionSort(input);
        assertArrayEquals(input,answer);
    }
}

• 알고리즘

public class InsertionSort {

    public static void insertionSort(int[] src) {
        for (int i = 1; i < src.length; i++) {
            int key = src[i];
            int j = i - 1;
            while (j >= 0 && src[j] > key) {
                src[j + 1] = src[j];
                j--;
            }
            src[j + 1] = key;
        }
    }
}

버블정렬

버블정렬

• 두 인접한 원소를 비교하여 정렬하는 알고리즘
• 최선의 경우 시간복잡도는 O(n) : 이미 정렬되어 있는 경우
• 최악의 경우 시간복잡도는 O(n^2) : 반대로 정렬되어 있는 경우
• 추가 공간이 필요하지 않다

//pseudocode
BubbleSort(A){
  for(i=1 to A.length-1){
    for(j=A.length downto i+1){
      if(A[j]<A[j-1])
        swap(A[j],A[j-1]);
    }
  }
}

최악의 경우 시간복잡도가 O(n^2)인 이유는 내부 for문의 연산횟수 때문이다.

Java로 버블정렬 구현

• 테스트 코드

import org.junit.jupiter.api.Test;
import java.util.Arrays;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;

class BubbleSortTest {

    @Test
    public void testBestTimeComplexity(){

        int[] input = new int[]{1,2,3,4,5};
        int[] answer = Arrays.copyOf(input,input.length);
        Arrays.sort(answer);

        BubbleSort.bubbleSort(input);
        assertArrayEquals(input,answer);
    }

    @Test
    public void testUnSortedArray(){

        int[] input = {64,34,25,12,22,11,90};
        int[] answer = Arrays.copyOf(input,input.length);
        Arrays.sort(answer);

        BubbleSort.bubbleSort(input);
        assertArrayEquals(input,answer);
    }

    @Test
    public void testWorstTimeComplexity(){

        int[] input = {5,4,3,2,1};
        int[] answer = Arrays.copyOf(input,input.length);
        Arrays.sort(answer);

        BubbleSort.bubbleSort(input);
        assertArrayEquals(input,answer);
    }

}

• 알고리즘

public class BubbleSort {

    public static void bubbleSort(int[] src) {
        int size = src.length;
        boolean swapped;
        for (int i = 1; i < size; i++) {
            swapped = false;
            for (int j = size - 1; j >= i; j--) {
                if (compareTo(src[j], src[j - 1]) < 0) {
                    swap(src, j, j - 1);
                    swapped = true;
                }
            }

            // 이미 정렬된 배열인 경우 정렬을 종료한다(시간복잡도: O(n))
            if (swapped == false)
                break;
        }
    }

    private static void swap(int[] src, int i, int j) {
        int tmp = src[i];
        src[i] = src[j];
        src[j] = tmp;
    }

    private static int compareTo(int a, int b) {
        if (a > b)
            return 1;
        else if (a == b)
            return 0;
        else return -1;
    }
}

12/19 목요일

1. 알고리즘

   • Introduction to Algorithm

     • BubbleSort 학습 및 포스팅
     • InsertionSort 학습 및 포스팅
     • BucketSort 복습
     • CountingSort 복습
     • HeapSort 복습
2. 안드로이드
   • MVM,MVC,MVVC 샘플 코드 분석

##IP/이더넷 송수신 과정(2)

이더넷의 기본

• IP 담당 부분이 패킷을 완성했으면 LAN 어댑터가 나설 차례인데, 그 전에 이더넷의 기본에 대해 알아보자.
  

  이더넷은 다수의 컴퓨터가 여러 상대와 자유롭게 적은 비용으로 통신하기 위해 고안된 통신 기술이며, 그림의 (a)와 같다.

  네트워크의 실체는 케이블이다. 트랜시버라는 작은 기기도 있지만, 이것은 연결한 케이블 사이의 신호를 흘리는 역활만 하며, 케이블과 같은 것이다. 컴퓨터가 신호를 송신하면 케이블을 통해 네트워크 전체에 신호가 흐르고 전원에게 신호가 도착한다.

  신호의 맨 앞 부분에 수신처에 대한 정보(주소)를 명시해두고 해당하는 기기는 패킷을 수신하고 다른 기기들은 패킷을 패기한다. 그림의 (c)와 같은 스위칭 허브를 사용한 형태가 현재의 이더넷의 형태다. 수신처 MAC 주소를 가진 기기로만 신호가 흐르고, 다른 곳에는 신호가 흐르지 않는 방식이다. 그 외 송신처 MAC 주소를 명시하고, 이더 타입으로 패킷의 내용물을 나타내는 성질은 변하지 않았다. 이 세가지 성질을 가진 것이 이더넷이라고 생각하면 된다.

IP 패킷을 전기나 빛의 신호로 변환하여 송신한다

• IP가 만든 패킷은 메모리에 기억된 디지털 데이터 이므로 이것을 그대로 상대에게 보낼 수 없다. 그래서 디지털 데이터를 전기나 빛의 신호로 변환하여 네트워크의 케이블에 송출하는데, 이것이 송∙수신 동작의 본질이라 할 수 있다.
  

  이 동작은 실행하는 것이 LAN 어댑터인데, LAN 어댑터는 단독으로는 동작하지 않는다. LAN 어댑터를 제어하라면 LAN 드라이버 소프트웨어가 필요하기 때문이다.

• LAN 어댑터는 전원을 공급하면 즉시 사용할 수 있는 것이 아니라 초기화 작업이 필요하다. 전원을 공급하여 OS를 시동할 때 LAN 드라이버가 하드웨어의 초기화 작업을 수행해야 사용가능한 상태가 된다. 여기에서 실행하는 이더넷 특유의 작업은 이더넷의 송∙수신 동작을 제어하는 MAC이라는 회로에 MAC주소를 설정하는 것이다.
  

  LAN 어댑터의 ROM에는 전 세계적으로 중복되지 않도록 일원화해서 관리하는 MAC주소를 제조할 때 기록하므로 이것을 읽어와서 MAC 회로에 설정하는 것이다. 이렇게 해서 MAC 회로는 자체에 할당된 MAC주소가 무엇인지 알게된다. 특수한 사용법이지만 명령이나 설정파일에서 MAC주소를 받아 설정하는 경우도 있다. 이때 LAN 어댑터의 ROM에 기록한 것을 무시한다. 전원을 공급할때 ROM에 기록된 MAC주소가 자동적으로 유효한 것처럼 보이지만 LAN 드라이버가 초기화 작업의 일환으로 MAC 회로에 설정한 MAC주소가 유효하게 된다.

패킷에 3개의 제어용 데이터를 추가한다

• 이제 패킷을 전기 신호로 변환하여 실제로 케이블에 송출하는 장면으로 넘어간다. LAN 드라이버는 IP 담당 부분에서 패킷을 받으면 그것을 LAN 어댑터의 버퍼 메모리에 복사한다. 복사를 마친 후 패킷을 송신하도록 MAC 회로에 명령을 보내면 MAC 회로의 작업이 시작된다.

• MAC 회로는 먼저 송신 패킷을 버퍼 메모리에서 추출하고 맨 앞에는 프리앰블과 스타트 프레임 딜리미터라는 두 개의 데이터를, 맨 끝에는 프레임 체크 시퀀스라는 오류 검출용 데이터를 부가한다.
  

• 프리앰블은 송신하는 패킷을 읽은 때의 타이밍을 잡기 위한 것으로, ‘10101010…‘과 같이 1과 0이 번갈아 나타나는 비트열이 56비트 이어진 것이다. 디지털 데이터를 전기 신호로 나타낼 때는 0과 1의 비트 값을 전압이나 전류의 값에 대응시킨다. 그러나 0과 1이 이어지면 신호의 변화가 없어져서 비트 구분을 할 수 없게 된다는 문제가 생긴다. 이 문제를 해결하기 위한 방법은 데이터를 나타내는 신호와 비트 구분을 나타내는 클록이라는 신호를 보내는 방법이다. 거리가 멀어져서 케이블이 길어지면 데이터 신호와 클록 신호가 전달되는 시간에 차이가 생기기 때문에 클록이 틀어져 버릴 수 있다. 따라서 데이터 신호와 클록 신호를 합성하여 한 개의 신호를 만들어서 전달하면 이 문제를 해결할 수 있다.

  이때 클록 신호의 타이밍을 판단하는 것이 중요하다. 10메가비트/초나 100메가비트/초라는 식으로 클록의 변화주기는 결정되어 있으므로 에스컬레이터에 탔을 때와 같이 잠시 신호의 변화를 볼 수 있으면 타이밍을 파악할 수 있다. 갑자기 패킷의 신호를 흘리는 것이 아니라 클록 신호의 타이밍을 잡기 위한 특별한 신호를 패킷 앞에 부가하면 되는데, 이것이 프리앰블의 역활이다. 스타디 프레임 딜리미터는 패킷의 시작을 나타내는 표시가 되고 FCS 패킷을 운반하는. 도중에 잡음 등의 영햐응로 파형이 흐트러져 데이터가 변한 경웅이것을 검출하기 위해 사용한다.

허브를 향해 패킷을 송신한다

• 프리앰블, 스타트 프레임 딜리미터, FCS 세 가지를 부가하면 케이블에 송출하는 패킷이 완성된다. 신호를 송신하는 동작을 설명하는데, 이 동작에는 리피터 허브를 사용했을 때의 반이중 모드와 스위칭 허브를 사용한 전이중모드의 두 가지가 있다. 여기에서는 전자인 반이중 모드부터 설명한다.

• 반이중 모드의 동작은 신호의 충돌을 피하기 위해 먼저 케이블에 다른 기기가 송신한 신호가 흐르고 있는지 조사하고, 신호가 흐르고 있으면 그것이 끝날때까지 기다린다. 신호가 흐르고 있을 때 송신 동작을 하면 신호가 충돌하기 때문이다. 그리고 신호가 정지했거나 흐르고 있지 않으면 송신 동작을 시작한다. 이 송신. 동작은 먼저 MAC 회로가 프리앰블의 맨 앞부터 1비트씩 차례로 디지털 데이터를 전기 신호로 변환하고, 이것을 PHY 또는 MAU라는 송∙수신 신호부분에 보낸다. 이때 디지털 데이터를 신호로 변환하는 속도가 전송 속도다.
• PHY(MAU)회로는 이 신호를 케이블에 송출하는 형식으로 변환하여 송신한다. 이더넷은 케이블의 종류나 전송 속도에 따라 몇 가지 신호형식이 규정되어 있지만, MAC 회로는 이러한. 형식의 차이에 신경쓰지 않고 어느 형식으로도 변환할 수 있는 공통 형식의 신호를 PHY(MAU)회로에 보낸다. 그리고 PHY(MAU)회로에서 실제로 케이블에 송출하는 형식으로 변환하여 송신한다. PHY(MAU)회로는 MAC 회로가 송신한 신호의 형식을 변환하기 위한 변환회로라고 생각하면 된다.
• PHY(MAU)회로가 MAC 회로에서 받은 신호를 케이블에 송신할 때 단지 송신 동작만 실행하는 것이 아니라 수신 신호선에서 신호가 흘러들어오는지 감시한다. 그리고 신호 송신이 완료할 때까지 수신 신호선에 신호가 들어오지 않으면 송∙수신 동작이 끝난다. ‘이더넷’이라는 통신 방식은 송신한 신호가 상대에게 완전하게 도착했는지 확인하지 않는다. 만일 오류가 발생해도 프로토콜 스택의 TCP가 검출하므로 신호를 송신할 때 오류를 확인할 필요가 없다. 신호를 송신하고 있는 사이에 수신 신호가 흘러들어오면 리피터. 허브를 사용한 반이중 모드의 경우 서로의 신호가 뒤섞여서 분간할 수 없는 상태가 되는데, 이것이 바로 충돌이라는 현상이다. 이렇게 되면 송신을 해도 의미가 없으므로 송신 동작을 중지하고 충돌이 일어난 사실을 알리기 위해 재밍 신호를 흘린다. 그리고 송신 동작을 멈추고 잠시 기다렸다가 다시 한 번 송신 동작을 시도한다.
  이더넷이 혼잡해지면 충돌의 가능성이 높아지므로 다시 보낼때 다른 기기와 송신 동작이 겹쳐 다시 충돌이 발생할 수도 있다.이렇게 되면 대기 시간을 2배로 늘려 다시보낸다. 그리고 충돌이 일어날때 마다 2배씩 늘리며 송신하고 열 번째까지 보냈는데 해결되지 않으면 오류로 판단한다.

돌아온 패킷을 받는다

• LAN 어댑터에서 패킷을 전기 신호로 변환하여 송출하는 동작은 이것으로 끝이다. 이제 이더넷의 움직임을 알았으므로 패킷을 수신할 때의 동작을 알아보자.
  

  리피터. 허브를 이용한 반이중 동작의 이더넷에서는 1대가 송신한 신호가 리피터 허브에 접속된 케이블 전부에 흘러간다. 그러므로 수신동작은 이러한 신호를 전부 받아들이는 것부터 시작한다. 신호의 맨 앞에는 프리앰블이 있으므로 파형에서 타이밍을 계산하여 스타트 프레임 딜리미터가 나오면, 그 다음 비트부터 디지털 데이터로 변환하여 동작을 개시한다. 이 동작은 송신할 때와 반대로 PHY(MAU) 회로에서 MAC 회로쪽으로 진행한다. 먼저 PHY(MAU) 회로에서 신호를 맨 앞부터 차례대로 디지털 데이터로 변환하여 버퍼 메모리에 저장한다. 그리고 신호의 마지막에 이르면 FCS를 검사한다. FCS에 문제가 없으면 다음에는 MAC 헤더의 수신처 MAC 주소를 조사하여 LAN 어댑터를 초기화할 때 설정한 자체의 MAC 주소와 비교한 후 이것이 자신에게 오는 것인지 판단한다. 다른 곳에 갈 패킷은 수신할 필요가 없으므로 폐기하고, 수신처 MAC 주소가 자신에게 오는 경우에만 패킷을 받아 버퍼 메모리에 저장한다. 이렇게 해서 MAC 회로가 할 일이 끝나면 패킷을 수신한 사실을 컴퓨터 본체에 통지한다. 이 통지는 인터럽트라는 구조를 사용한다. LAN 어댑터가 패킷 송∙수신 동작을 실행하고. 있는 사이 컴퓨터 본체는 LAN 어댑터의 움직임을 감시하는 것이 아니라 다른 작업을 실행하고 있다. 이러한 상태일 때 컴퓨터 본체가 실행하고 있는 작업에 끼어들어 LAN 어댑터쪽에 주의시키는 것이 인터럽트다.

  
  

  
  

서버의 응답 패킷을 IP에서 TCP로 넘긴다

• 이제 웹 서버에서 패킷이 돌아온 것으로 간주하고 다음. 프로토콜 스택의 동작을 추적해보자. LAN 드라이버는 TCP/IP의 프로토콜 스택에 패킷을 건넬 것이다. IP 담당 부분은 IP 헤더 부분부터 조사하여 포맷에 문제가 없는지 확인하고, 수신처 IP 주소를 조사한다. 패킷을 수신한 기기의 IP 주소는 수신한 LAN 어댑터에 할당된 주소와 일치할 것이므로 이 것을 확인하고 패킷을 수신한다. 만약 수신처 IP 주소가 자신의 주소와 다르면 오류가 있는 것이다. 이와 같이 오류가 발생했을 때는 IP 담당 부분이 ICMP라는 메시지를 사용하여 통신상대에게 오류를 통지하게 되어 있다.

• 패킷을 운반하는 도중 통신 회선이나 LAN 중에 짧은 패킷만 다룰 수 있는 것이 있다. 이를 위해 패킷을 여러 개로 분할하는 것은 IP 프로토콜이 담당한다. 분할된 패킷은 IP 헤더에 있는 플래그라는 항목을 보면 알 수 있으므로 수신 패킷이 분할된 것이면 IP 담당 부분 내부의 메모리에 일시적으로 보관한다. 그리고 IP 헤더에 있는 ID 정보에 같은 값을 가진 패킷이 도착하기를 기다리고, 분할된 패킷은 ID 정보의 값이 모두 같은 값인 패킷이므로 이것을 참조한다. 또한 프래그먼트 오프셋이라는 항목에는. 패킷이 원래 패킷의 어느 위치에 있었는지를 나타내는 정보가 들어있다. 이러한 정보를 바탕으로 분할된 패킷이 전부 도착하기를 기다렸다가 패킷의 원래모습으로 되돌리는 동작을 리어셈블링이라고 한다. 리어셈블링이 끝나면 IP 담당 부분의 역활은 끝나므로 TCP 담당 부분에 건네준다. 그러면 TCP 담당 부분은 IP 헤더에 기록된 수신처 IP주소와 송신처 IP주소, TCP 헤더에 기록된 수신처 포트번호 및 송신처 포트 번호의 네가지 항목을 조사하여 해당하는 소켓을 찾는다. 해당하는 소켓을 찾아내면 통신 진행 상태가 기록되어 있으므로 상황에 따라 적절한 동작을 실행한다. 예를 들어 애플리케이션의 데이터를 넣은 패킷이 있다면 수신 확인 패킷을 반송한 후 데이터를 수신 버퍼에 저장하고 애플리케이션이 가지러 오기를 기다릴 것이다.

ref 성공과 실패를 결정하는 1% 네트워크 원리