HTTP란?

HTTP(Hyper Text Transfer Protocol) 텍스트 기반 통신 규약으로써,

인터넷에서 데이터를 주고받을 수 있는 프로토콜입니다.

HTTP는 신뢰성 있는 데이터 전송 프로토콜을 사용하는데

TCP 프로토콜에서는 데이터 송수신을 위해 클라이언트와 서버의 소켓이 연결되어 있어야 하며, 데이터가 유실되면 데이터

재전송을 요청함으로써 신뢰성을 보장합니다.

즉, 신뢰성 있는 데이터 전송이 가능하다는 장점으로 인해 HTTP, FTP, TELNET 등 대부분의 응용 계층 프로토콜의

전송 계층으로 사용 됩니다.

이렇기 때문에 인터넷의 결함이나 약점에 대한 걱정 없이 고유의 기능을 구현하는데에만 집중이 가능합니다.

웹 클라이언트와 서버

웹 콘텐츠들은 웹 서버에 존재합니다. 웹 서버는 HTTP로 통신을 한다고 했었기 때문에, HTTP서버 라고도 합니다.

이 웹 서버는 인터넷의 데이터를 저장하고, 클라이언트가 요청한 데이터를 제공해줍니다.

쉽게 설명하면 프론트단에서 Request(요청) 값을 보내면 서버쪽에서 Response(응답) 객체를 내려주는 원리라고

생각하면 되겠습니다.

이것이 바로 World Wide Web(통칭 WWW) 의 기본 요소입니다.

리소스

웹 서버는 웹 리소스들을 관리하고 제공합니다.

원초적인 이 웹 리소스는 웹 서버 파일 시스템의 정적 파일입니다.

이 정적 파일이라 함은, HTML파일부터 시작하여, 이미지파일 등등 모든 종류의 파일이 여기에 포함됩니다.

이런 정적파일이 주가 되기는 하지만, 무조건적으로 정적 파일일 필요는 없습니다.

이 동적 리소스인 경우에는 사용자마다, 시간, 정보 등등에 따라 각기 다른 콘텐츠들을 제공합니다.

미디어 타입

미디어 타입은 서버에서 메소드인자에 많이 들어간것을 생각해보면 됩니다.

대표적인 예가 바로

setContentType(MediaType.APPLICATION_JSON) 입니다.

인터넷은 수천가지 데이터 타입들을 다루기 때문에, HTTP에서는 웹에서 전송되는 객체 각각에 MIME이라는

데이터 포맷 타입을 붙이게 됩니다. 이 MIME은 전자메일 시스템에서 주로 사용을 했었는데,

각 문서와 함께 올바른 MIME 타입을 전송하도록, 서버가 정확히 설정하는 것이 중요합니다.

브라우저들은 리소스를 내려받았을 때 해야 할 기본 동작이 무엇인지를 결정하기 위해 MIME 타입을 사용합니다.

문법

MIME 타입의 구조는 주타입 / 부타입 으로 이루어져 있습니다.

이러한 예시들이 있습니다.

• application/json
• text/html
• image/jpeg

URI (Uniform Resource Identifier)

웹 리소스는 각기 고유한 이름을 가지고 있기 때문에, 클라이언트는 해당 리소스를 지목하여 호출할 수가 있습니다.

글에대한 리소스 URI라면 이렇게 표현이 가능합니다.

https://lsj8367.github.io/spring/Spring-Filter-Interceptor/

1. https 프로토콜을 사용해서
2. lsj8367.github.io 로 이동한 후
3. spring/Spring-Filter-Interceptor 에 해당하는 리소스를 가져와줘!

하면 이제 해당하는 글에 대한 포스팅을 보여주게 될 것입니다.

모든 코드는 여기

불 논리

NAND 게이트

Nand 게이트는 유니버셜 로직 게이트라고도 부르는데

이 게이트 하나만으로 모든 바이너리 동작을 제어할 수가 있다.

Nand게이트는 다음과 같은 불 함수를 계산한다.

기본 논리 게이트

Not

단일 입력 Not게이트 Converter라고 불리며 input값의

반대값으로 Output을 내준다.

And

And는 곱연산으로서, 입력 값이 둘다 1일 경우에만 1을 출력해준다.

Or

Or는 합연산으로, 입력값 2개중 1개가 1이라면 1을 출력해준다.

Xor

배타적 논리합 이라고 불리며, 두 입력값이 서로 다를 경우 1

그렇지 않으면 0을 출력한다.

멀티플렉서(Multiplexer)

멀티플렉서는 3입력 게이트로 selector 비트를 이용하여

나머지 두개 데이터 비트 입력중 하나를 선택.

디멀티플렉서

이름만봐도 멀티플렉서의 정반대 기능을 수행한다고 알 수 있다.

디멀티플렉서는 선택한 비트에 따라 출력선 중 하나를 선택해 입력 신호를 보낸다.

멀티비트

멀티비트는 버스라는 멀티배열에 대한 연산을 수행하게 되어있다.

이 연산들은 쭉 같은 논리연산을 나열하여 비트의 쌍마다 연산을 수행해주는 것이다.

여기서는 16비트에 대한 연산을 진행했다.

AND 연산으로 예를 들어보겠다.

원래 하나의 비트 XY에 대하여 결과값을 AND(X,Y) 했던것을 16개를 동시에 진행한다고

생각하면 된다.

아래의 모든 예시는 전부 16비트 연산으로 이루어져있다.

AND16

기본 게이트의 연산과 같은데 갯수만 늘어난 것이므로 설명은 생략하도록 하겠다.

OR16

NOT16

MUX16 멀티플렉서

다입력

입력이 여러개인 다입력 게이트이다.

다입력에는 다입력/멀티비트 도 같이 묶어서 정리하겠다.

Or8Way

Or8Way의 논리게이트 인터페이스는 다음과 같다.

Mux4Way

이것의 멀티비트라고 한다면

이 같은 그림이 16개가 같이 수행된다고 생각하면 된다.

셀렉터가 2개이기 때문에

sel 0번째로 a,b 그리고 c,d 를 연산 한후에
나온 결과값 o1, o2를 sel 1번째로 연산하여 결과값을 출력해주는 구조이다.

Mux8Way

4Way의 구조를 2개로 만들어서 결과값을 도출해주는 8입력 멀티플렉서이다.

DMux4Way

반대인 디 멀티플렉서이다.

여기부터는 실습에서도 멀티비트는 하지 않았기에 하나만 쓰도록 하겠다.

이건 입력을 1개를 받아서 4개의 결과값을 도출해주는 정반대 플렉서이다.

DMux8Way

이것도 Mux8Way와 반대의 특성을 가지고 있으며 4Way 2개가 붙어진 것이다.

정리

이렇게 1장 불 논리가 끝이났다.

처음 구현을 시작했을 때에는 NAND 게이트로 쭉쭉 구현을 진행했는데

특징이라고 한다면 컴파일 자체가 가령 Or를 구현해야 한다고 치면

Or만 써서 바로 구현할 수가 없게 해놨다.

이런 함수를 하나씩 쓰려면 그 전의 동작을 알게끔 한것인가?

하는 생각이 들었다.

그리고 마지막으로는 결국 구현이 다 되어서 BUILTIN이라는 기능으로

tools - builtInChips 안의 자바 클래스파일들 이 있으면

해당 기능을 사용할 수 있었다.

마지막으로는 그것으로 구현해두고 나머지는 주석처리를 진행했다.

이진수를 다루면서 완전 밑바닥을 체험하니 재밌기도 하고 어렵기도 했다.

재귀 알고리즘

개념을 먼저 익힌 후에 백준 알고리즘을 푸는식으로 해야겠다. 맨땅에 헤딩식으로 하면 나는 잘 이해가 안되는 것 같다. 천천히 하더라도 깊이있게 해보자❗

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.

바로 예제로 가보도록 하자

팩토리얼 구하기

재귀의 예시로 팩토리얼이 있다.
n!(팩토리얼) 은 n * n-1 * n-2 * ... 이다.
이것을 그대로 코드로 표현하면 다음과 같다.

import java.util.Scanner;

public class Factorial {
    static int factorial(int n) {
        if(n > 0)
            return n * factorial(n - 1);
        else
            return 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n + "! = " + factorial(n));
    }
}

동작형식을 자세하게 보면 factorial(int n)은 n이 0보다 크면 n * factorial(n - 1) 를 호출하고 아니면 1을 반환한다.

풀어서 써보자.

예를 들어 n값에 3을 넣었다고 가정한다.

• n = 3
  • 3 * factorial(2);
  • 2 * factorial(1);
  • 1 * factorial(0);
  • return 1

이 순서로 들어가게 될텐데,

맨 마지막의 1부터 1 * 2 * 3 이 되는 것이다.
호출은 n = 3부터 시작했으니 정렬이 되면 3 * 2 * 1이 되게 된다.

이렇게 해서 3! 의 답인 6을 얻게된다.

내가 재귀를 볼때 막힘없이 봐야 이해가 쏙 되는것 같은 느낌 😂

한번에 안읽히면 머릿속에서 무한루프를 도는느낌이다.

항상 끝부터 쭉 나간다음 생각해 보는것이 이해가 잘된다❗

재귀 안썼을 때

static int factorial(int n) {
        int count = 1;

        for(int i = n; i > 0; i--) {
            count *= i;
        }

        return count;
    }

유클리드 호제법

최대공약수를 재귀로 구할 수 있다.

두 정수를 직사각형 두 변의 길이라고 가정하면 최대 공약수를 구하는 문제는 다음과 같아질 수 있다.

직사각형을 정사각형으로 완전히 채우고, 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하자

4와 22 의 최대 공약수를 구해보자고 가정하면

1. 22 x 4에서 4를 한변으로 하는 정사각형으로 분할한다.
2. 5개의 4 x 4 정사각형이 생기고 2 x 2 두개가 남는다.
3. 이렇게 더이상 나눌 수 없는 2 x 2 정사각형이 생겼으므로 2가 최대 공약수이다.

public class Euclid {
    static int solution(int x, int y) {
        if(y == 0) {
            return x;
        }

        return solution(y, x % y);
    }

    public static void main(String[] args) {
        int x = 22;
        int y = 4;
        System.out.println(solution(x, y));
    }
}

단순하게 해석하면 0일때까지 계속 solution 자기 자신을 호출하면서 맨 마지막에 남은 x를 돌려주는 것이다.

재귀 안썼을 때

static int gcd2(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

배열 모든 요소의 최대 공약수

public class EucArray {

    static int euc(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    static int eucArray(int[] arr, int index, int length) {
        if(length == 1) {
            return arr[index];
        }

        if(length == 2) {
            return euc(arr[index], arr[index + 1]);
        }

        return euc(arr[index], eucArray(arr, index + 1, length - 1));
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 12, 15};
        System.out.println(eucArray(arr, 0, arr.length));
    }
}

막상 풀어보니까 이렇게 복잡한거는 재귀보다는 다른 방법이 나아보이는....

그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
단어 그대로 번역하자면 탐욕법이다.
이 부분에서 탐욕적이라 함은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이다.
이 알고리즘은 매 순간 가장 좋아 보이는 것만 선택하고, 그 선택이 나중에 어떤 영향을 미치는지에 대해서는 고려하지 않는다.

거스름돈을 예시로 살펴보자
당신은 음식점의 계산을 도와주는 점원이 되었다고 가정하자.
500원, 100원, 50원, 10원짜리 동전은 무한히 존재한다. 손님에게 거슬러줘야 하는 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구해라
(단, 거슬러줘야 할 돈 N은 항상 10의 배수이다.)

이럴때는 단순하게 가장 가격이 큰 동전 부터 돈을 거슬러 주는 것이다.
이렇게 되면 N원으로 설정된 가격을 금방 차감시켜 0원으로 만들기 적합하다.

coin.py

n = 1260 # 거슬러줘야할 가격
count = 0 # 코인의 개수

# 화폐 단위가 큰 것부터 차례로 거슬러준다.
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 원래 가격을 코인값으로 나눈 몫만큼 동전으로 추가해줌
    n %= coin

print(count)

화폐의 종류가 K개 라고 할때, 위 소스의 시간복잡도는 BigO 표기법으로 O(K)이다. 시간복잡도에서는 총 화폐인 N을 찾을 수 없다.
그래서 이 알고리즘은 동전의 종류에만 영향을 받지 거슬러 줘야하는 금액에는 초점이 맞춰지지 않는다.

알고리즘 문제 유형을 바로 파악하기 어렵다면, 그리디 알고리즘을 의심해 볼 수 있다.

그리디 알고리즘의 예제를 많이 풀어봐야겠다.