• IP주소는 인터넷 프로토콜을 쓰는 인터넷망에서 인터넷에 연결된 컴퓨터 한 대를 식별하기 위해서 부여하는 고유번호이다.

IPv4주소의 구조

• IP는 32bit 주소 체계를 사용한다.
  • 32bit는 8bit가 4개 있는 것.
  • 전부 1이면 브로드캐스팅인지 고민해라.
• ipconfig 로 IP주소를 확인할 수 있다.
  • 192.168로 시작하면 사설 주소인가?
• 8bit 씩 쪼개서 가운데에 점(.)을 찍는다.
  • 점을 구분으로 해서 8bit씩이므로, 각 숫자는 0~255까지 될 수 있다.
• IP주소는 Network ID와 Host ID로 구분한다.
  • 우리나라 주소체계로 생각하자면 ‘서울시 강남구 역삼동 00번지’이다.
  • ‘서울시 강남구 역삼동’가 Network ID, ‘번지’가 Host ID라는 느낌으로 기억하자.
• 인터넷망이 고속도로, 패킷을 택배라고 하자.
  • 이때, 물류센터에 택배가 도착하면 어느 동네로 갈 것인지에 따라 분배한다.
• 즉, 각 ID는 다음과 같이 생각하자.
  • Network ID로 우리 동네까지 올 건지 아닌지를 판별한다.
  • Host ID로 동네에 도착한 후에 어느 집으로 갈 것인가를 본다.

L3 IP Packet

L3 Packet

• Packet은 개념적으로 단위 데이터이다.
• Packet이라는 말은 L3 IP Packet으로 외워라.
  • 보통 L3라는 말은 안 붙인다.
  • Packet을 언급하면 “IP 프로토콜이고 레이어 3이다”
• (L2 프레임에서와 마찬가지로) Header와 Payload로 나뉘며 이는 상대적인 분류이다.
  • 논리적 구조
  • Header가 송장이라면 Payload는 전달되는 대상
  • Header에는 Source가 어디인데, Destination으로 간다는 정보가 포함되어 있다. → 출발지/목적지 주소
• 최대 크기는 MTU (Maximum transmission unit)
  • Header와 Payload를 포함하여 전체 크기를 MTU이다.
  • 특별한 이유가 없다면 1500 byte(1.4KB 정도)이다.

정리하자면, 인터넷이라는 거대한 논리 네트워크에서 정보의 유통체계이며 최소 단위 최대 크기가 1500byte밖에 안된다.

Encapsulation과 Decapsulation

Encapsulation

• 이해를 돕기 위한 비유
  • 물건을 포장해서 택배로 쏙 넣었다.
• 쏙 넣었다는 의미에서 몇 가지 특징이 있다.
  • 어떤 단위로 바꿨다. → 단위화했다.
    • 택배를 보낼 때 박스 단위로 만든다.
  • 안에 어떤 것이 들어있는지는 모른다.
    • 택배 안에 들어있는 것이 책인지 음식인지 알 수 없다.
    • 보안적으로 봤을 때 보이지 않는다.
    • 정확히는 보이지 않는 건 사실은 아니지만, 단위 안에 넣어서 못 보게 하겠다는 의도가 포함되어있다는 점을 기억하자.

En/Decapsulation

• L2 Frame 내부에 L3 IP Packet이 있다. → IP Packet 통째로 L2 Frame의 Payload가 된다.
• L3 IP Packet 내부에는 L4 계층의 데이터(Segment)가 된다.
• L4 → L3 → L2 씩으로 하나씩 포장하는 것이 Encapsulation이다.
• L2 → L3 → L4 씩으로 하나씩 꺼내는 것이 Decapsulation이다.

패킷의 생성과 전달

두 가지 관점에서 다뤄본다.

패킷의 생성, 전달, 소멸

비유를 하자면, 다음 순서대로 진행된다.

• 철수가 영희에게 택배를 보낼 것이다.
  1. 보낼 물건(책)을 준비한다.
  2. 박스를 구해서 그 안에 물건을 넣고 포장한다.
  3. 택배에 송장을 붙여 기사님께 드린다.
  4. 기사님은 택배들을 모아 하나의 트럭에 넣고 이동한다.
  5. 물류체계를 타고 영희에게 전달된다.
• 전달의 모든 과정은 기사님 이하, 그 이후에 일어나는 일이고 철수는 아무런 개입을 하지 않는다.
• 택배는 물류체계에 의해 전달을 하며 송장의 목적지 주소를 보고 영희의 집까지 간다.
• 송장에는 주소(Src/Dst, 출발지/목적지)와 이름(보내는/받는 사람)이 적혀 있다.
  • 만약, 영희의 집에 다른 가족들도 있다고 한다면, 받는 이를 보고 영희에게 전달될 것이다.

위 상황에서 용어를 정의하자면 다음과 같다.

• 용어 정리
  • 영희와 철수는 Process
  • 책은 Data, 택배는 Packet
  • 택배 기사는 Gateway
  • 집은 Host, 택배를 기사에게 전달하는 현관은 인터페이스
  • 송장의 주소는 Host까지 찾아가는데 쓰이고, 받는 이는 도착한 후 Process를 찾는데 쓰인다.

구체적인 과정

어떤 프로세스가 인터넷을 통해 정보(Data)를 전달하려고 한다.

먼저, User mode application process가 접근할 수 있도록 Kernel mode Protocal(TCP/IP)을 추상화시켜준 인터페이스가 있다. 이 인터페이스는 파일의 일종이며, 소켓이라고 부른다.

1. Data를 File에 Write한다.
   • TCP 소켓(네트워크)에서는 Write라고 하지 않고, Send라고 한다.
2. Data가 소켓을 타고 내려가서 TCP를 만나면 TCP Header를 붙여서 Segment라고 부른다.
   • Segment화
3. 한 층 더 내려가서 IP를 만나면 IP Header를 붙인다.
4. 한 층 더 내려가면 Frame Header(이더넷 헤더)가 붙는다.
5. 이렇게 포장된 것이 타고 나가서 L2 Access 스위치를 만나게 된다.
   • Process가 Data를 Packet으로 만든 후 Gateway에게 준다.
6. Access 스위치를 타고 올라가 라우터 게이트웨이를 타고 인터넷으로 나간다.
   • Host와 만나는 접점, 즉 인터페이스를 타고 Packet이 나간다.
   • Gateway는 물류체계에 의해 데이터를 라우팅한다.
7. IPv4를 보고 목적지 Host에게 이동하고, 도착한 후에는 Port 번호를 보고 Data를 전달한다.

계층별 데이터 단위

• 운영체제 수준
  • L1~L2 수준에서 논하는 데이터의 단위는 Frame이다.
  • IP 수준에서 논하는 데이터의 단위는 Packet이다.
  • TCP 수준에서 논하는 데이터의 단위는 Segment이다.
• User mode Application (L5~L7)
  • Socket 수준에서 논하는 데이터의 단위는 Stream이다.
  • 사실 Stream은 단위라고 하긴 힘들고, 데이터 덩어리 그 자체를 의미하는 것이다.
  • 하나의 단위가 될 때는 적어도 세그먼트를 논해야 하고, 그 다음에 패킷, 프레임 이렇게 논한다.
• 세그먼트를 패킷이라고 부르는 사람도 많다.
  • 특별히 구별해서 불러야 할 때가 아니라면 그냥 패킷이라고 부른다.

Stream

• Stream은 시작은 있으나 끝이 어디인지 정확하게 정의할 수가 없다.
• 이 끝은 프로세스 수준, 즉 어플리케이션 수준에서 정의해버리기 때문에 데이터를 송수신하는 운영체제 입장에서는 Stream은 연속적으로 이어진 크기를 정확히 알 수 없는 큰 데이터이다.
• Stream을 Socket에 대고 Write한다.

데이터의 최대 크기

• 인터넷의 데이터 단위 최대 크기는 MTU라고 정해져있다.
  • 1500bytes 정도.
• Segment 에도 Maximum Segment Size(MSS)가 있다.
  • 특별한 이유가 없다면 1460byte 정도이다.
• 스트림이 이 최대 크기보다 크다면, 스트림을 잘라서 분할한다.
  • 세그먼트화될 때 일정 단위(Maximun Segement Size)로 분할이 일어난다. → Segmentation

Datagram

• TCP가 아닌 UDP 프로토콜에서 데이터그램이라고 이야기한다.
• 정해진 데이터 덩어리이다.

TCP/IP 송수신 구조

그림으로 이해하기

• Naver에서 파일을 다운로드 한다고 하자.
  • Server에서는 파일을 송신하고, PC에서는 파일을 수신한다.
  • 정확히는 PC 내의 Process가 파일을 송신하고 수신한다.
• 인터넷 구간에서 정보가 유통될 때는 패킷의 형태로 간다.
  • 만약 파일이 1.4MB라면, 패킷의 MTU(1.4KB)와 1024배 이상 차이가 난다.
  • 즉, 1000개 이상의 패킷으로 바뀌어서 전송된다.

TCP/IP로 보낸다고 가정한다면

• TCP는 연결지향, Connection Oriented Protocal이다.
• 즉, TCP 연결이 됐다는 가정 하에 송수신이 이루어진다.

Socket

• 소켓의 본질은 File이다.
• 소켓에 대고 입출력(I/O)가 일어난다.
  • 이런 입출력이 일어날 때는 이 File 혹은 소켓에 Attached된 메모리 공간, 즉 버퍼가 있기 마련이다.
  • 이 버퍼가 있으면 Buffered I/O를 하는 것이고, 버퍼 없이 입출력을 직접한다면 Non-Buffered I/O를 하게 된다.
• 버퍼는 두 가지이다.
  • 프로그램(프로세스)에서 연결된 애가 관리하는 버퍼
  • 소켓 입출력 버퍼

파일 전송

송신 측

송신하는 쪽에선 항상 Encapsulation이 일어난다.

1. 1.4MB의 비트맵 파일을 보낸다고 가정한다면, 프로세스가 관리하는 버퍼에는 1.4MB를 모두 메모리에 올릴 수도 있고 일부를 올릴 수도 있다.
   • 파일(일정 수준의 Block)을 Copy해서 버퍼에 올린다.
2. 프로세스가 관리하는 버퍼를 Copy해서 소켓 입출력 버퍼에 올린다.
   • Send할 Data Copy
   • 이때의 데이터 단위는 Stream이며, 파일 전체를 읽어서 보낼 때 파일이 끝이 난다.
3. L4(TCP)로 내려갈 때 분해가 일어난다.
   • Segmentation
   • 이렇게 자른 Segment에 번호를 붙인다.
   • Segment는 하나씩 보내지고, 1번을 보낸 후 2번을 바로 보낼 수도 있고 wait를 줄 수도 있다.
4. L3(IP)로 내려가면 박스 형태로 Segment를 포장 후 송장을 붙인다.
   • 즉, Packet이 된다.
5. L2로 내려가면 트럭(Frame) 안에 택배를 담는다.
   • 즉, Frame 형태로 내려간다.
   • 이 Frame은 유통과정에서 수시로 바뀐다. → 한 번에 배달되지 않고 트럭이 바뀌어가며 배달된다.
6. 데이터를 전송 후 일정 수준이 지나면 wait를 걸고 잘 받았는지(ACK)를 기다린다.
   • 1번과 2번을 보냈다면 ACK 3이 오기를 기다린다.
   • ACK 3이 온다면 3번을 보낸다.

수신 측

수신하는 쪽에선 항상 Decapsulation이 일어난다.

1. L2 수준에서 트럭에서 하차가 일어난다.
   • Frame이 도착해서 Packet을 끄집어낸다. → Frame은 사라진다.
2. L3(IP)로 올라가서 Packet에서 Segment를 꺼낸다.
3. Segement가 소켓 입출력 버퍼에 쌓인다.
   • 운영체제의 TCP 스택에서 버퍼를 채워준다.
4. 소켓 입출력 버퍼의 내용을 프로세스 버퍼로 옮겨줘야 한다.
   • 개념적으로는 Read라고 하는데, 네트워크에서는 Receive라고 한다.
   • 리시브를 시도할 때는 프로세스 버퍼의 전체 사이즈만큼 리시브를 시도한다.
   • 1번과 2번이 입출력 버퍼에 있다면, 둘을 합쳐서 프로세스 버퍼에 MOVE한다.
5. 중요한 것은 속도 차가 있다는 것이다.
   • 네트워크에서는 소켓 입출력 버퍼를 계속 채우고, 프로세스는 계속해서 비워서 여유 공간을 지속적으로 확보한다.
6. TCP에서는 데이터를 받은 후 잘 받았다고 피드백을 준다.
   • 이 피드백을 ACK(acknowledgement)라고 한다.
   • ACK#3 → 1번과 2번까지 잘 받았다는 의미이다.
   • ACK를 보낼 때 여유공간도 함께 보낸다. 송신 측에서는 이 여유공간이 있으면 데이터를 보내고, 없으면 못보낸다.

Network 장애

Network에서 장애가 발생하는 경우가 잦은데, 대표적으로 다음 것들이 있다.

• H/W 수준에서 Loss(유실, Lost Segment) 발생
  • 100% 네트워크 상에서 문제가 있다.
• Re-transmission
  • ACK가 오지 않으면 다시 보낼 때가 있다. (1번과 2번을 다시 보냄)
  • 복잡한 타이머로 정교하게 도는 것이어서, 간발의 차로 ACK와 재전송이 같이 일어날 수 있다.
  • 그러면 ACK-Dupplication(중복)이 일어난다.
  • 네트워크 문제일 수도 있고, End-point 간에 합이 안 맞아서 문제가 난 걸 수도 있다.
• Out of order
  • 1번 오고 2번 왔는데, 그 다음에 3번이 아닌 4번이 와버린다.
  • 이렇듯 순서가 잘못된 경우를 Out of order라고 한다.
  • 이 경우에는 TCP 스택에서 보정을 하게 된다.
  • 네트워크 문제일 수도 있고, End-point 간에 합이 안 맞아서 문제가 난 걸 수도 있다.
  • 주로 네트워크 상에서 이슈가 난다.
• Zero window
  • 여유공간의 메모리 공간을 Window size라고 부르는데, 이게 0이 된 것이다.
  • 즉, 네트워크의 송수신 속도가 프로세스(프로그램)이 버퍼를 비우는 속도보다 빨라서 Full이 난 것이다.
  • 확실하게 End-point에서 Application 문제다. → 문제를 프로그램에서 찾아야 한다.

IP 헤더 형식

IPv4 Header

• MTU(Header+Payload)는 1500bytes, Header는 20bytes가량 한다.
  • Options 이 붙으면 더 늘어나기도 한다.
• 그림을 보면 Data는 최대 65515 bytes(64K가량)도 될 수 있다고 되어 있다.
  • 실제로는 그렇진 못하고, MTU에 맞춰서 운영된다.
  • 늘어나는 사례도 있긴 하다.

구성

• Version
  • IPv4이므로 항상 4byte이다.
• IHL (Internet Header Length)
  • Header의 크기를 말한다.
  • 보통 5행이다.
  • $5\times4byte=20bytes$
• TOS (Type of service)
• Total Length
  • Payload의 길이
  • 16비트이므로, 나올 수 있는 경우의 수는 $2^{16}=65535$이다.
  • 여기서 헤더 길이 20을 빼서 대략 65515bytes 정도이다.
  • 이론상 IP 패킷은 헤더를 포함하여 64KB가 가장 큰 숫자이다.
• 두번째 행은 모두 단편화(Fragment)와 관련이 있다.
  • 예를 들어 패킷이 MTU가 1500인데, 어느 네트워크에 갔더니 MTU가 1300이어서 패킷을 잘라야할 때가 있다.
  • 이렇게 잘라야할 때 단편화가 난다고 한다.
• TTL (time to live)
  • 유통과정에서 TTL 값은 HOP이라는 단위를 지날 때마다 감소하는데, 0이 되면 이 패킷은 버려진다.
  • 최대 크기는 $2^8=255$이다.
• Protocal
  • L3 Payload 안에 또 다른 Header가 올 수 있는데, 이 Header를 어떤 형태로 해석해야 되는지 프로토콜이 뭔지 설명이 된다.
  • 프로토콜마다 고유 번호를 부여한 것이 있다. (TCP는 6)
• Header Checksum
  • 네트워크로 패킷을 송수신하는 과정에서 손상이 일어났는지 검사하는 값이다.
• 출발지/목적지 주소
  • 32bit

서브넷 마스크와 CIDR

Subnet Mask

• 서브넷 마스크를 기준으로 Network ID와 Host ID를 분리한다.
• 어떤 패킷이 온다면, 네트워크 장비나 이런 데서 서브넷 마스크와 IP주소를 bit단위로 AND 연산한다.
  • Mask 연산이라고 한다.
  • 네트워크 ID가 나와 일치한다면 우리 네트워크로 유입되는 것이라고 판단
• 서브넷 마스크를 $255.255.255.0$라고 표기하면 앞에서부터 24비트를 Network ID라고 보는 것이다.
  • 서브넷 마스크에서 1bit인 부분은 AND 연산 시, 자기 자신이 나온다.
  • 즉, 255는 $11111111$이므로 자기 자신이 통째로 나오는 것이다.

Class

• IP 주소에 Class 개념을 도입해서 등급을 매겼었다.
  • IP 주소가 A.B.C.D라면,
  • A만 Network ID로 사용한다면 A클래스
  • B만 Network ID로 사용한다면 B클래스
  • C만 Network ID로 사용한다면 C클래스
• 요즘은 Class라는 개념을 사실상 쓰지 않는다.

CIDR (Classless Inter-Domain Routing)

• 클래스 개념 없이, 즉 네트워크 구분을 Class로 하지 않는다.
  • Class는 사이더가 나오기 전 사용했던 네트워크 구분 체계
• 사이더 표기법이라고 한다.
• 예를 들어, $192.168.0.10/24$ 라면 왼쪽부터 24개의 bit를 Network ID로 규정한다.
  • $255.255.255.0$ 대신 슬래시로 표현

서브네팅

• 이미 잘려진 네트워크를 또 자르고 싶을 때 서브네팅이라고 한다.
• 서브넷 마스크할 때 Host ID 부분의 앞 부분의 비트가 올라간다.
  • 예를 들어, $192.168.0.10$이고 서브넷 마스크가 $255.255.255.0$이라면, 뒤의 2비트가 올라가서 $255.255.255.192$가 된다.
  • Host ID는 6bit가 되므로 나올 수 있는 수는 $2^6$이 된다.

Broadcast IP 주소

• MAC 주소는 48bit 주소 체계를 갖는다.
  • FF-FF-FF-FF-FF-FF
• IP에서 Host ID를 모두 1로 채우면 해당 네트워크에서 방송 주소로 쓰인다.
  • 예를 들어, $192.168.0.255$ 라면 $192.168.0$ 네트워크에서 방송 주소가 된다.
  • MAC 주소도 FF-FF-FF-FF-FF-FF로 되어 있다.
• 만약 특정 주소를 찍어서 간다면 Unicast지만, Host ID를 1로 채워서 간다면 Broadcast이다.
  • Multicast도 전체에 전달한다는 점에선 브로드캐스트와 유사하지만, 전달받은 애들을 따로 모아서 그룹핑하는 경우가 있다.
    • IGMP를 다룬다?
• 브로드캐스트를 자주하면 효율이 떨어진다.
  • 네트워크 장비 전체에 부담이 늘어난다.
  • 따라서 브로드캐스트 범위를 일정 범위 안에서 통제해야 한다.
• 브로드캐스트는 안 할 수 있으면 안 하는게 정답이다.

네트워크에서 쓸 수 없는 주소

• Host 부분이 0이면 서브넷 마스크와 일치하므로 사용할 수 없다.
• Host 부분이 255면 브로드캐스트가 되므로 사용할 수 없다.
• 따라서, Host 부분에서 실제로 사용할 수 있는 IP주소는 $256-2=254$이다.
• 게이트웨이에 보통 1번을 많이 준다.
  • 네트워크 장비 말고 순수하게 PC같은 애들이 쓸 수 있는 주소 개수는 250개 정도밖에 안된다.

Host 자신을 가리키는 IP 주소

127.0.0.1

• 인터넷을 사용하는 주체는 컴퓨터가 아니고, 컴퓨터에서 실행 중인 Process이다.
• 프로세스들이 내 프로세스들 간에 통신을 해야 할 때 (내가 나에게 접속) 쓸 수 있는 IP 주소가 $127.0.0.1$ 이다.
  • 이때, 1은 다른 걸 쓸 수도 있지만 보통 1을 쓴다.
• 이러한 주소를 Loopback Address라고 부른다.
• IP 주소를 특정하지 않고, $127.0.0.1$ 로 하면 내 컴퓨터 내의 프로세스 간 정보를 주고 받게 된다.
  • 실제로 패킷은 IP 계층 밑으로 내려가지 않는다.
• 루프백 어드레스는 프로세스 간 통신을 할 때도 구현이 된다.
  • IPC (Inter Process Communication)이라고 한다.
  • 소켓을 이용해서 내가 나한테 접속하는 방식으로 프로세스 간 통신이 이루어지도록 지원할 때 흔히 사용된다.

💡 프로세스 간 통신(Inter-Process Communication, IPC) 프로세스들 사이에 서로 데이터를 주고받는 행위 또는 그에 대한 방법이나 경로

TTL과 단편화

Router VS L3 Switch

• 두 가지 의견이 있다.
  • 라우터는 L3 스위치의 일종이므로 둘을 구분하는 것은 의미가 없다.
  • L3 스위치가 라우터의 일종이다.
• 둘을 구분하는 것은 의미는 없다는 것이 강사님의 의견이다.
  • 또한 개념적으로 L3 스위치에 포함되는 것으로 보는 게 타당하지 않을까?

TTL

• Time To Live(TTL)은 다음과 같은 역할을 한다.
  • Packet을 전송할 때 목적지를 찾지 못하고 실패하는 경우가 있다.
  • 이때 패킷이 네트워크에 좀비처럼 남아서, 좀비 패킷이 넘쳐나서 네트워크 전체가 다운되는 일이 없도록 빨리 버리고 폐기시켜야 한다.
• TTL의 값은 128인 경우도 있고 255인 경우도 있다.
  • 라우터에서 어떤 라우터를 지날 때 단위를 Hop 단위라고 한다.
  • Hop 단위로 지날 때마다(라우터를 지날 때마다) 값을 감소시킨다.
  • 값이 0이 되면 목적지를 찾는데 실패했다고 보고 폐기한다.
  • 라우터가 출발지에게 패킷이 폐기되었다고 알려주기도 하고, 보안 상의 이유로 알려주지 않기도 한다.

단편화

• 단편화는 MTU 크기 차이로 발생한다.
  • 특별한 이유가 없다면 MTU는 1500bytes 정도 하는데, 다른 곳에서 MTU가 1400bytes라면 그에 맞춰서 패킷을 잘라줘야 한다.
  • MTU 크기가 달라서 패킷의 크기를 잘라야 할 때 단편화라고 한다.
• 보통 단편의 조립은 수신측 Host에서 이루어진다.

예제

• 송신측 MTU는 1500인데 중간에 경로의 라우터 하나는 MTU가 1400이다.
• 그럼 해당 라우터로 갈 때 단편화가 발생한다.
  • Payload를 둘로 나누고, 각각 IP 헤더를 붙여준다.
  • 이 IP 헤더들은 flag나 offset 등 디테일한 값에서는 차이가 조금 있다.
• 이렇게 분리된 패킷들은 수신 측 End-point에서 조립한다.
  • IP 프로토콜을 만나면 조립이 일어난다.
  • 패킷을 조립한 후 Segment를 꺼낸다.

주의사항

• 단편화는 가급적 발생되지 않는 것이 좋다.
  • 베스트는 처음부터 패킷을 보낼 때 1400으로 보내는 것이다. (하향평준화)
  • 처음부터 단편화가 나지 않도록 낮춰서 보내는 것이 일반적이다.
• 가장 대표적으로 VPN이 적용되었을 때 MTU가 줄어드는 경우가 생긴다.
  • 특히 IPSec VPN이 적용되면서 보안성은 올라가지만 단편화가 발생할 수 있다.
• 그 외에는 단편화가 날 가능성이 생각보다 높지 않다.

인터넷 설정 자동화를 위한 DHCP

인터넷 사용 전에 해야 할 설정

• IP 주소
• Subnet mask
• Gateway IP주소
  • 여기까지는 L3에서 설정해야 하는 것이다.
• DNS 주소
  • 도메인을 입력한다면 DNS 서버가 해당 도메인의 IP 주소가 무엇인지 알려준다.

ISP (Internet Service Provider)

• Host를 유니크하게 식별할 수 있는 식별자를 IP 주소라고 한다.
• 문제는 사용자는 IP주소의 값이 뭔지 구체적으로 알 수가 없다.
• 이러한 서비스를 제공해주는 회사를 ISP라고 한다.
• ISP쪽에서 IP주소들을 가지고 있다.
  • 서비스를 돈 주고 구매하면 이 주소 중 하나를 쓸 수 있게 허락해준다.

자동 설정

• 보통 이러한 인터넷 설정들은 내가 직접하지 않고, 자동 설정해준다.
  • 제어판 - 네트워크 설정으로 볼 수 있다.
• 자동으로 설정하겠다는 것은 DHCP를 활용하겠다는 것이다.

DHCP (Dynamic Host Configuration Protocol)

• DHCP 체계는 주소를 할당하는 서버와 할당 받으려는 클라이언트로 구성된다.
  • 서버가 자동이라고 할 만한 모든 설정의 정보를 가지고 있다.
  • 클라이언트가 접속하면 IP 주소를 포함한 설정(게이트웨이, 서브넷 등)을 모두 서버가 알려준다.
• 복잡한 인터넷 설정을 자동으로 해준다고 볼 수 있는데, 핵심은 내가 사용할 IP주소를 서버가 알려준다는 것에 있다.
• Dynamic은 IT쪽에서 Runtime과 동일한 말이다.
  • 동적이다.
  • 컴퓨터 작동 중에 되는 것
• Broadcast domain 안에 묶여 있어야 한다.

동작 과정

• PC의 전원이 켜지면 네트워크로 브로드캐스트 패킷이 나간다.
  • DHCP 관련돼서 리퀘스트를 디스커버리라고 한다.
  • 우리 네트워크 중에 DHCP 서버가 있는지를 묻는 디스커버리 트래픽이 나온다.
  • 액세스 스위치에 도달하면 브로드캐스트하고 업링크해서 전달한다.
  • 즉, 네트워크 전체에 퍼진다.
• DHCP Server가 response를 보낸다.
  • 다른 컴퓨터들은 DHCP 서버가 아니므로 브로드캐스트 트래픽을 수신해도 아무런 응답을 보내지 않는다.
• 이전에 할당받은 주소가 있다면 DHCP Server에게 전에 받은 주소를 써도 되는지 묻는다.
  • 써도 된다고 허락하거나 새로 주소를 내려준다.

ARP

ARP (Address Resolution Protocol)

• ARP는 IP주소로 MAC 주소를 알아내려 할 때 활용된다.
  • ARP의 Address는 IP주소와 MAC 주소를 말한다.
• 보통의 경우 PC를 부팅하면 Gateway의 MAC 주소를 찾아내기 위해 ARP Request가 발생하며 이에 대응하는 Reply로 MAC 주소를 알 수 있다.
  • 인터넷을 하기 위해서 Gateway의 MAC 주소를 반드시 알아야 한다.

예제

💡 PC의 IP 주소가 192.168.0.100이고 Gateway의 주소가 192.168.0.1이고 통신하고자하는 Naver 주소가 3.3.3.3이라고 가정하자.

• 인터넷으로 넘어오면 L3이므로 IP 주소가 중요하다.
  • MAC 주소는 L2 구간에서만 중요하다.
  • 다시 말해, 내가 Naver의 MAC 주소를 안다고 해도 그걸로 통신하지 않는다.
• PC가 인터넷에 접속하려고 한다면 Gateway MAC 주소를 반드시 알아야 한다.

1. ARP 리퀘스트를 브로드캐스트로 보낸다.
   • 처음 PC를 켰을 때 DHCP 서버에서 받은 Gateway 주소로, 이 주소를 사용하고 있는지를 확인
2. Gateway는 해당 주소를 사용하고 있으므로 ARP reply를 보낸다.
   • 이 때, MAC 주소를 같이 보낸다.
3. PC는 Naver로 패킷을 보내는데, L2 Frame에서의 주소는 다음과 같다.
   • 출발지: PC의 MAC 주소
   • 목적지: Gateway의 MAC 주소
   • 물론 L3의 IP 패킷의 출발지/목적지는 PC와 Naver의 IP 주소이다.
4. Gateway는 IP 패킷의 헤더를 보고 목적지가 어딘지 판단한다.

ARP 캐시

• PC가 Gateway를 주소를 한 번 알아낸 후, 계속 다시 물을 이유는 없다.
  • 따라서 캐시해서 메모리에 담고 있다.
• CMD에서 arp -a 를 입력하면 arp 캐시가 나온다.
  • IP 주소 ~의 Gateway 주소는 무엇이다라는 정보가 출력됨

Ping과 RTT

Round Trip Time

왕복 시간(RTT)은 네트워크 요청이 시작점에서 목적지로 갔다가 다시 시작점으로 돌아오는 데 걸리는 시간(밀리초)이다.

참고: https://www.cloudflare.com/ko-kr/learning/cdn/glossary/round-trip-time-rtt/

Ping

• Ping 유틸리티(그냥 프로그램)는 특정 Host에 대한 RTT(Round Trip Time)을 측정할 목적으로 사용된다.
  • Ping은 그냥 프로그램 이름이다.
  • 보통 RTT로 네트워크의 회선 속도를 결정하고, RTT를 측정하는 가장 전형적인 프로그램이 Ping이다.
• ICMP 프로토콜을 이용한다.
• DoS(Denial of Service) 공격용으로 악용되기도 한다.
  • 서버에 핑을 계속해서 보내는 등
• ping은 Echo Request로 일정 길이의 알파벳들을 보내고, Reponse로 똑같은 문자열이 돌아온다.

예제

만약, 철수와 영희와 길동이 같이 게임을 하고 있다. 이때, 각자의 Ping 속도가 다음과 같다.

• 철수: 20ms
• 영희: 25ms
• 길동: 50ms

그러면 길동이는 속도가 느리므로 화면이 서로 달리 보이게 된다.

이런 경우 “라운드 트립 타임이 시간이 오래 걸린다”, “라운드 트립에 문제가 있는 것 같다”고 표현한다.

💡 이때, 하향평준화를 시킬 것인지 화면 동기화를 어떻게 할 것인지 기술적인 노하우가 필요하다. 이러한 노하우는 어느 정도 공개가 되어있다.

활용

• 인터넷 연결이 안 될 때 Gateway에 Ping을 보내본다.
  • 답이 없으면 Gateway가 다운되었다는 의미가 된다.
• 이때 몇 ms가 소요되었는지 나오는데, 이게 RTT가 된다.
  • Gateway는 거의 LAN 수준, 즉 로컬 네트워크에 가깝기 때문에 매우 빠르다. (1ms 이내에도 응답이 온다.)
• 물리적 거리가 멀다 해도 네트워크 회선 속도가 훨씬 빠르다면 응답은 빠를 것이다.
  • RTT는 거리에 비례하는 것이 아니고 네트워크 속도가 중요한 것이다.
  • 물론 거리가 멀어지면 속도가 떨어질 가능성은 높다.

Reference

외워서 끝내는 네트워크 핵심이론 - 기초 강의 - 인프런

TCP와 UDP 개요

인터넷 환경에서 가장 중요한 4계층 프로토콜들이다.

TCP와 UDP

• TCP에만 연결(Connection, Session) 개념이 있다.
  • 연결지향(Connection Oriented)

연결 (Connection, Session)

• 연결은 매우 논리적이다.
  • 그래서 TCP 연결은 Virtual Circuit라고도 한다.

💡 아래는 강사님 의견이므로, 네트워크를 깊게 공부한 사람은 의견이 다를 수 있다.

• 연결은 결과적으로 순서번호로 구현된다.
  • 앞서 세그먼트에 순서를 붙였던 것이 순서번호다.
  • 이 순번은 세그먼트 사이즈의 바이트 수만큼 증가한다.
    • 1을 보냈는데 용량이 400이라면 401이 된다.
  • 바이트 수만큼 시퀀스 번호(순서번호)가 증가하게 되어 있다.
    • 이걸로 송수신 양을 측정하기도 한다.
• 연결은 ‘상태(전이)’ 개념을 동반한다.
  • 예를 들어, 통화를 한다면 통화하기 전, 통화 연결, 통화를 종료한 후가 있을 것이다.
• TCP는 배려남, UDP는 배려가 없는 나쁜 남자에 비유할 수 있다.
  • 상대가 못 받으면 TCP는 보내지 않는다.
  • UDP는 상대가 받든지 말든지 무조건 보낸다.

TCP

• Client와 Server로 나뉜다.
  • 클라이언트는 연결을 하는 주체
  • 서버는 기다리고 있다 연결을 받는다.
• Server는 연결을 대기하고 있다.
  • 웹 서버는 기본적으로 TCP 80번을 사용한다.
  • listen 상태의 소켓을 생성하고 열어서 연결 대기
• Client(프로세스)가 소켓을 생성해서 오픈한다.
  • 프로세스는 자신의 식별자인 PID를 갖는다.
  • 소켓을 열면 OS가 소켓에 TCP 포트 번호를 부여한다. (번호는 남는 것으로 랜덤하게 부여됨)
• TCP(와 UDP) 통신을 하려면 IP 주소와 포트 번호를 알아야 연결을 개념적으로 시도해볼 수 있다.
• 클라이언트가 연결 Request를 보냈는데 Server에서 연결 대기를 하고 있지 않다면, 커널의 TCP 계층에서 연결을 못 받아준다는 답이 간다. → 운영체제 수준에서 자동으로 이루어진다.

UDP

• 연결이라는 개념은 없지만, 구조는 비슷하다.
  • 소켓 통신을 하며 포트 번호를 갖는다.
• 특정 포트 번호를 지정할 것인지 아무거나 available한 것을 달라고 할 것인지 정도의 차이만 있다.

TCP 연결 과정

3-way handshaking

가정: 클라이언트와 접속 대기 중인 서버가 있다.

• RTT가 50ms 걸렸다고 가정한다면, 응답하는 데 걸리는 시간을 제외하고 오고 가는데 각각 약 20ms 정도 걸렸다는 이야기이다.
  • 이때 통신되는 단위가 Segment이다.
  • 여기서의 Segement는 Payload가 없다. → 단순 내부 연결 관리 목적의 세그먼트
• 연결 과정 (3-way handshaking)
  1. Client에서 랜덤으로 Sequence Number(1000)를 생성한다.
  2. 이렇게 생성한 번호를 Server에게 알려준다. (SYN)
  3. Server도 랜덤으로 Sequence Number(4000)를 생성하고, 클라이언트가 보낸 번호에 1을 증가시켜서 응답한다.
     • 이때, Server가 생성한 번호도 함께 보낸다.
  4. Client도 Server가 보낸 번호에 1을 증가해서 응답한다.
• Client와 Server의 연결 사이에 시간 차가 있다.
  • Client는 Server에게 ACK를 받으면 연결이 완료되었다고 판단
  • Server는 최종적으로 Client에게 ACK를 받은 시점에 연결이 완료되었다고 판단
  • 즉, 클라이언트와 서버가 각각 연결이 완료되었다고 판단하는 시점이 약 20~25ms의 시간 차가 생긴다.
• TCP 연결의 실체는?
  • Seq 번호 교환
  • 정책 교환
    • 정책에는 여러 가지가 있다.
    • Seq 번호+1 한 것
    • Maximum Segment Size
• 실제로 전선을 서버와 클라이언트와 물리적으로 연결하는 것이 아닌, 논리적 연결이다.

TCP 연결 종료 및 상태변화

• 특별한 이유가 없다면 Client가 행동이 Active하다.
  • 연결을 하자고 하는 것도, 끊겠다고 하는 것도 Client여야 한다.
  • 만약 Server가 연결을 끊겠다고 하는 것은 특수한 경우다.

4-way handshaking

가정: 클라이언트와 서버는 서로 연결된 상태이다.

• 종료 과정 (4-way handshaking)
  1. 클라이언트가 연결을 끊자고 FIN을 보낸다.
  2. 서버는 ACK를 보낸다.
  3. 클라이언트는 ACK를 받으면 FIN_WAIT2 상태로 넘어가면서 FIN+ACK를 기다린다.
  4. 서버가 FIN+ACK를 보내면, 클라이언트는 TIME_WAIT 상태가 된다.
     • TIME_WAIT가 발생한다는 것은 누군가 연결을 끊자고 할 때, 연결이 최종적으로 완료되기 전에 발생한다.
     • 만약 서버 측에서 TIME_WAIT 상태가 발생한다면 서버가 연결을 끊자고 했단 건데, 이러면 어플리케이션 프로토콜 설계가 정상적이지 않은 상황인 것이다.
  • 서버는 CLOSE_WAIT 상태로 클라이언트가 보낼 마지막 ACK를 기다린다.
  • 클라이언트가 ACK를 보내고 서버에 도착하면 최종적으로 연결이 종료된다.
    • 클라이언트는 일정 시간이 지난 후 CLOSED되고 소켓이 회수된다.
• 어플리케이션 프로토콜을 설계할 때 서버 측에서 연결을 끊게 하지 말고, 클라이언트가 먼저 끊게 하자.
  • 소켓은 유한한 자원이기 때문에 회수되어야 한다.
  • 자신이 연결을 끊자고 하면 소켓 회수가 바로 안 되기 때문이다.

TCP (연결) 상태 변화

TCP 트랜지션 상태 변화에 대한 다이어그램

• 처음에 소켓은 닫혀있으므로 열어준다.
  • 소켓은 파일이니 Create 개념을 적용하는게 맞겠지만,
  • 있는 것 중에 번호를 부여해서 열어야 하다 보니 Create라는 표현이 아닌 Closed라고 주로 표현한다.
• Server는 LISTEN 트랙을 탄다.

TCP, UDP 헤더 형식과 활용

TCP Header 형식

• 총 32bit

• Port 번호는 $2^{16}$ 개가 나올 수 있다.

  • 0~65535

  • 포트번호의 0번과 65535번은 없으므로, 실제로 쓸 수 있는 번호는 $2^{16}-2$ 개이다.

  • well-known 포트 번호라는 것이 있다.

    💡 well-known 포트

    잘 알려진 포트(well-known port)는 특정한 쓰임새를 위해서 IANA에서 할당한 TCP 및 UDP 포트 번호의 일부이다. 일반적으로 포트 번호는 다음과 같이 세 가지로 나눌 수 있다.

    0번 ~ 1023번: 잘 알려진 포트 (well-known port) 1024번 ~ 49151번: 등록된 포트 (registered port) 49152번 ~ 65535번: 동적 포트 (dynamic port)

    출처: https://ko.wikipedia.org/wiki/TCP/UDP의_포트_목록

• Sequence number

  • 데이터를 보낼 때, 데이터의 길이(byte)에 따라 증가한다.
  • 데이터가 1000byte라면 1000 증가

• Data offset

  • 뒤에 Option이 있는지, 아니면 TCP (segment) Payload 위치를 계산할 때 사용한다.
  • TCP 세그먼트가 시작되는 위치를 기준으로 데이터의 시작 위치를 나타내므로 TCP 헤더의 크기가 된다.
  • IP 헤더의 IHL과 비슷한 개념이다.

• flag 값들

  • NS ~ FIN
  • TCP의 상태를 결정할 때 사용한다.
  • RST: 리셋, 잘못되었을 때 연결을 끊자고 하는 것. → 비정상적으로 끊길 때 리셋
  • PSH: 푸시, TCP 통신할 때 버퍼링하지 말고 즉시 보내자는 뜻이다.

• 혼잡제어

  • 앞서 설명했던 다섯 가지 장애 유형이 발생했을 때 네트워크가 혼잡하다고 보고, 통제(천천히 간다던지)하기 위해 존재하는 필드들이다.

UDP 헤더 형식

• 혼잡제어를 하지 않는다.
• 수신하는 측의 버퍼가 얼마나 남았는지(Window Size) 등도 고려하지 않는다.
• UDP를 사용해야 하는 경우
  • 예를 들어, IPTV의 어떤 영상을 송출해주는 서버가 있다. 해당 서버에 연결되어 있는 수많은 사용자들은 각자 속도가 다를 것이다. 속도가 느린 사용자에게 맞추면 속도가 빠른 사용자는 손해를 보게 된다.

UDP의 활용

• UDP는 멀티미디어 데이터 전송에 최적화되어 있는 측면이 있다.
• HTTP3 에도 UDP가 활용된다.

게임 서버 개발

• TCP를 이용해 게임 서버 간에 동기화를 하게 되면, 하향평준화 문제가 발생한다.
  • 한 사용자가 느려지면 전체가 전부 느려지게 프로토콜을 구성할 수밖에 없다.
• 따라서 동기화를 위해 UDP를 이용해 게임 서버 간 구현을 많이 한다.
  • TCP가 가지고 있는 혼잡 제어 기능은 직접 구현하면 된다.

TCP ‘연결’이라는 착각

💡 파일 다운로드 중 LAN 케이블을 분리했다가 다시 연결하면 TCP 연결은 어떻게 될까?

• 소켓 프로그래밍을 할 때는 연결이 되어있는지 지속적으로 검사한다.
  • TCP 3-way handshake가 끝났음에도 계속해서 재확인한다.
  • 이 행위를 하트 비트라고 한다.
• (RFC 문서에서는) 재전송 타이머의 기본 근사 값은 대략 3다. 하지만 대부분의 운영체제들은 1초 미만이다.
• 재전송 타이머 만료 후에도 확인 응답을 받지 못한 경우 세그먼트를 재전송하고 RTO(Retransmission Time-Out) 값은 두 배로 증가한다.
  • 예를 들어 1초 > 2초 > 4초 > 8초 > 16초 간격으로 재전송한다.
• 보통 최대 5회 재전송을 시도하고 5회 이상 모두 실패할 경우 전송 오류가 발생한다.

TCP 연결과 게임 버그

• 어떤 MMORPG 게임에서 아이템 복제 버그가 발생했다.
  • 과거 TCP 연결의 착각을 이용한 해킹이 있었다.
• 이는 논리적 TCP 연결과 물리적 링크 간 차이를 이용한 시간차 공격이라고 볼 수 있으며, 연결이 사실은 End-point의 주관적 판단에 불과하다는 것을 보여준다.

TCP 연결은 보안성이 없다

• 보안의 3대 요소
  • 기밀성: 누가 도청할 수 있는가?
  • 무결성: 누군가 조작(변조)할 수 있는가?
  • 가용성: 재해 대책과 관련된 것
• TCP 연결은 보안성이 없으므로, 신뢰할 수 없다.
  • 연결은 착각이다!

Reference

외워서 끝내는 네트워크 핵심이론 - 기초 강의 - 인프런

동시성(Concurrency)이란

• 여러 가지 일이 동시에 진행되는 것!
• 예를 들어, 라면 먹는 일과 TV보는 일이 있다고 하자.
  • 두 가지 일은 개별 사건의 독립적 사건이다.
  • 두 가지 일은 동시에 일어날 수 있는가? → 동시성이 있다.
  • 두 가지 일이 동시에 일어날 수 없다면 동시성이 없는 것이다.
• 상호 간섭이 없고 동시에 연산하고 실행한다고 문제될 것이 없으면 동시성이 없다.
  • “컨커런시가 문제가 없다”, “컨커런트하다”고 표현한다.

병렬성(Parallelism)이란

• 같은 일을 여러 주체가 함께 동시에 진행하는 것!
• 병렬성도 동시성 범주 안에 들어가는 걸로 생각해볼 수 있다.

질문과 답변

• 이해를 돕기 위한 질문과 답변

💡 동시성과 병렬성의 차이

강의에선 위와 같이 설명했지만, 찾아보니까 동시성은 싱글 코어에서 여러 작업(멀티 쓰레드)를 동작시키는 방식이고 병렬성은 멀티 코어에서 멀티 쓰레드를 동작시키는 방식이라고 한다.

병렬성은 “실제로 동시에” 실행되는 것이고, 동시성은 시간적으로 겹쳐 발생(스케줄링 등)이다. 즉, 위의 설명은 조금 다른 게 아닐까? 출처: https://seamless.tistory.com/42

💡 동시성과 병렬성의 추가 설명 출처: https://www.inflearn.com/questions/897157 출처: https://www.inflearn.com/questions/1023922/동시성과-병렬성의-예시

원자성, 동기화 그리고 교착상태

원자성

• 예를 들어서
  1. 강력한 자연의 부름을 온 몸으로 느낀다! (시작)
  2. 화장실로 이동
  3. 화장실에 들어가기 전에 노크
     • 화장실이라는 자원을 누군가 쓰고 있는지(선점했는지) 조사한다.
  4. 화장실에 진입
     • 쓰고 있지 않다면 진입 후 Lock을 걸어 선점한다.
  5. 볼일
  6. 손을 씻는다
  7. 편안한 얼굴로 화장실을 나온다. (끝)
     • Unlock을 한다.
  • 이때, Lock을 건 4번부터 6번까지는 원자성이 보장된다.
• 동시라는 것은 여러 일이 동시에 일어날 때고, 그런 게 아니라면 원자성은 늘 보장받는다.

동기화(synchronization)

이런 것들이 외부의 어떤 자원과 결합했을 때 항상 동기화 현상이 일어난다.

• (운영체제나 컴퓨터 구조같은 데에서 동기화는) 신호등과 잠금 장치의 필요성과 유사하다.
  • 교차로에서 차가 멈춰야 할 지 가야 할지 신호를 가지고 통제한다. → 동기화한다.
• 동기화를 할 때, 동기화에 필요한 잠금장치에 해당되는 것들은 보통 OS가 제공해준다.
  • 이런 걸 이용해서 무언가를 하기도 한다.

교착상태(Deadlock)

동기화 이야기가 나오면 항상 논리적인 오류에 대해 고민하게 된다.

• 휴지가 없어서 못 나가는 자, 나와야 들어가는 휴지 든 자
  • 예를 들어, 철수가 화장실에 Lock을 걸고 들어갔는데 휴지가 없다.
  • 그럼 철수는 wait를 하게 된다. (휴지가 공급될 때까지 못나간다)
  • 밖에서 기다리는 영수는 휴지를 갖고 Unlock되기를 기다리고 있다.
• 이러한 상태를 교착상태(Deadlock)이라고 한다.
• 전형적인 잘못된 오류현상이다.

정리

여러 연산 주체가 동시에 접근해서 문제가 나는 걸 막기 위해 락도 걸고 동기화도 해서 원자성을 보장받는다.

그런데 잘못된, 특히 외부 자원에 대한 어떤 무언가를 요구하는 것에서 그 무언가를 중심으로 해서 양단 간의 의존성이 존재하는 애들이 동시에 일을 하다 교착상태에 빠질 수도 있다.

이것은 전형적인 논리 오류이다.

컴퓨터의 구성요소와 아바타

컴퓨터와 구성요소

• Computer는 H/W와 S/W로 구성된다.
• S/W는 (User mode) Application과 System S/W로 구분된다.
• 가장 대표적인 System S/W는 OS(Operation System)이다.

프로그램, 프로세스, 스레드

• 프로그램(Program)은 설치하는 것이다.
• 설치된 프로그램을 실행하면 프로세스(Process)가 생성된다.
  • 운영체제가 프로그램을 프로세스로 만들어준다.
  • 운영체제는 프로세스 단위로 메모리를 이만큼 써 라고 준다.
  • 프로세스는 PID를 얻는다.
  • 프로세스는 작업관리자에서 실행 중인 프로세스 목록을 확인할 수 있다.
  • 즉, 프로세스는 실관리적인 단위, 환경적 의미에서의 단위이다.
• 스레드(Thread)는 프로세스 속에 존재하는 실행단위이다.
  • 실행의 단위다. → 실행의 다른 이름은 ‘연산’이다.
  • CPU를 사용하는 놈은 쓰레드다.
  • 프로세스는 기본적으로 하나의 쓰레드이다.
  • 쓰레드 단위로 무언가 실행된다.
• 스레드는 프로세스에게 할당된 자원을 공유한다.
  • 여기서 자원은 메모리를 생각하면 된다.

용도에 따른 기억공간의 구분

• 메모리는 용도에 따라 구분된다.
• 메모리는 공간에 따라 여러 형태로 나뉜다.
  • 가장 대표적으로 유명한 공간은 Stack과 Heap이다.
  • Stack은 Thread가 사용한다.
  • Heap은 Process 전체가 사용한다.
• 주거공간으로 비유하자면, 스택은 개인공간(침실)이고 힙은 공용공간(거실)이다.

왜 공간을 구분했을까?

• 동시성 문제와 같은 여러 문제를 해결하기 위해 구분한 것이다.
• 공간은 특수한 목적을 가지고 구분한 것이고, 어떤 말도 안되는 현상이 나지 않도록 만든 것이다.
  • 예를 들어, 거실에서 볼일을 보거나 화상실에서 밥을 먹는 현상

정리

• 컴퓨터라는 세상에서 당신의 유전자는 프로그램이고 프로세스라는 모습으로 존재한다.
  • 가장 대표적으로 ‘나’로 지칭되는 프로그램은 Shell이다. → 윈도우로 치면 탐색기
• 예를 들어, 게임(세상)이라는 세상 속에 로그인해서 들어가면 캐릭터를 이용해 사냥하고 뛰어다닌다.
  • 그 캐릭터 하나가 아바타이다.
• 윈도우라는 컴퓨터에 로그인한다면, 그 속에는 아바타가 프로세스 형태로 존재하고 있다.

국가와 국민으로 이해하는 컴퓨터 세상

비유적인 것으로 먼저 이해하자.

국가와 국민으로 이해하기

• 국가의 구조

  • 레이어드이다. → 요소를 계층적으로 나열, 하위 요소는 상위 요소의 존립기반(전제조건)이다. 상위 요소는 하위 요소에 대해 존립 의존적이다.

• 영토는 물리적인 부분이다.

  • 하드웨어에 해당

• 정부 영역과 민간 영역은 소프트웨어에 해당한다.

  • 정부 영역의 행정 조직은 논리적 의미에서의 조직이다.
    • System 스프트웨어에 해당
    • 가장 대표적으로 운영체제가 있다.
  • 민간 영역의 국민은 각자 공간을 갖는다.
    • 민간 영역은 Application 계층에 해당

• 한 사람과 그 사람이 점유하는 공간을 세트로 묶어 프로그램이라고 보자.

  • 프로그램은 디스크에 설치되어 있는 것이다.
  • 프로그램을 실행하면 메모리 공간을 개별적으로 갖는 것이 프로세스, 즉 국민이 된다.

국민이 다른 국민의 공간에 침입

• 즉, 주거침입이다.
• 한 프로세스가 다른 프로세스의 메모리 공간에 침투하려고 하면 운영체제가 Access Violation 오류를 일으킨다.
  • “프로그램이 죽었다”고 표현하지만, 실제로는 연산을 못하도록 강제로 멈춘 것이다.
• 프로세스가 여러 개 존재하는 것을 멀티 태스킹 환경이라고 한다.
  • 각자의 프로세스가 동시성이 있다.
  • 운영체제로부터 공간, 행위, 연산에 대해 독립성과 원자성을 보장받는다.

국가 기관이 남의 공간에 침입

• 검찰이나 경찰은 남의 공간에 침입할 수 있다.
• 이렇게 특별한 권한을 가진 프로그램은 ‘디버거’이다.
  • OS가 디버거가 남의 메모리를 볼 수 있도록 허용해준다.

커널(Kernel)

• 운영체제의 핵심을 이루고 있는 알맹이를 커널이라고 부른다.
• 커널의 여러 역할 중 ‘접근 통제’가 가장 대표적이다.

User mode와 Kernel mode 그리고 가상화까지!

계층은 ‘모드’라고도 한다.

OS의 핵심 Kernel

• 컴퓨터라는 국가의 법은 Kernel로 구현된다.
• Kernel 영역과 사용자(User) 영역은 완전히 다른 세상이다.
• 소프트웨어가 작동할 때는 User mode Application 계층에서 작동하는 게 일반적이다.
• Kernel mode에서 작동한다고 하면 OS의 일부라고 보면 된다.
  • Kernel mode에서 작동하는 애들 중 OS가 아닌 경우는, 키보드 보안 등의 보안 쪽 소프트웨어가 포함되어 있다.

Kerner의 역할

• I/O
  • 정보를 입력하고 출력하는 것을 제어
• 자원 관리
  • 여기서 자원은 전산 자원(CPU와 메모리)이다.
  • CPU와 메모리를 어떤 프로세스가, 혹은 어떤 스레드가 얼마나 쓸 것인지를 통제한다.
• 접근 통제

User mode와 Kernel mode

• 하드웨어를 이루고 있는 가장 핵심적인 장치는 CPU이다.
  • CPU는 다른 말로 machine이라고 이야기한다.
• 하드웨어 계층을 설명할 때 가장 중요한 어휘는 Physical이다.
• 소프트웨어 계층을 설명할 때는 Logical이다.
  • IT쪽에서는 Virtual이라는 단어를 Logical과 유사하게 사용한다.
• 운영체제는 하드웨어에 대해 의존성이 존재한다.
  • 운영체제와 하드웨어 수준에서 플랫폼(Platform)이라는 말을 쓴다.
  • 플랫폼은 다른 것들이 작동할 수 있게 인프라가 되어주는 것이다.
  • 64bit platform이라고 이야기하면 OS도 64bit, CPU도 64bit라는 것을 말한다.
• 하드웨어에 어떤 디바이스(Device)가 있을 때, (어떤 운영체제 건) 해당 장치를 움직이기 위한 전용 소프트웨어가 있다.
  • 전용 소프트웨어는 커널에서 작동하는 소프트웨어이다.
  • 커널 모드 소프트웨어를 디바이스 드라이버(Driver)라고 부른다.
  • 장치가 무엇을 하는 장치냐에 따라 운영체제의 어떤 구성 요소(커널의 어떤 요소, 그림의 요소)같은게 있다.
• 컴퓨터라는 월드에서 나라는 존재는 프로세스 형태로 존재한다.
  • 프로세스를 다른 말로 Task라고도 한다.
  • 컴퓨터 안에서 프로세스는 여러 개가 동시에 실행된다. 이러한 환경을 다른 말로 멀티 태스킹 환경이라고 한다.

디바이스 파일

• User mode를 인간계, Kernel mode를 신계로 비유할 때
  • 인간계에서 신계의 어떤 신에게 메시지를 전달하고 싶다면 신이 정해주는 방법대로 무언가를 해야한다. ex) 기도
  • 신에게 메시지를 보내려면 반드시 매개체를 이용해야 한다. ex) 예수
  • 이러한 매개체는 Interface 역할을 하며 File의 형태로 존재한다.
• 즉, 커널 모드 영역에 진입하기 위해서 유저 모드 어플리케이션 프로세스가 커널에서 제공하는 어떤 인터페이스를 타고 그 영역에 접근해야 한다.
  • 이 인터페이스는 파일의 모습을 하고 있다.
  • 이러한 파일은 디바이스 파일(Device File)이라고 부른다.
• 커널의 구성 요소에 대한 추상화된 인터페이스를 유저 모드에 제공해줄 때 파일의 형태를 띄고 있다.
• 파일을 대상체라고 한다면 프로세스는 어떤 행위(입출력)의 주체가 되며, 파일에 대해 접근 권한을 획득해야 한다.
  • 접근 권한은 운영체제가 부여한다.
  • 즉, OS가 허락해주는 파일에 대해서만 무언가를 할 수 있다. → 접근 통제

Hello world를 출력할 때

• 출력은 모니터 화면에 출력한다. → 모니터 화면을 제어해야 한다.
• 모니터를 제어하는 본체와 연결된 장치(Device)가 있을 것이다.
  • 보통은 장치 중 비디오(Video) 카드
  • 비디오 카드에서 선이 나가서 HTMI 케이블같은 것과 연결될 것이다.
• 그러면 커널의 구성 요소는 Graphic Engine이 된다.
  • 핵심적인 역할을 하는 소프트웨어
  • 소프트웨어에 엔진이라는 말을 붙이면 코어 역할을 하는 중요한 프로그램이라는 비유적인 표현이다.
• “Hello world”라는 글자를 Device File을 통해 Write(I/O)하도록 내려보낸다.

파일 시스템

• 하드웨어가 HDD이고, HDD를 움직일 수 있는 디바이스 드라이버가 커널 모드 소프트웨어로 존재한다.
• 이때, 그 위의 커널의 구성 요소는 ‘파일 시스템’이 된다.
• 파일 시스템을 추상화한 인터페이스가 있고, 인터페이스(디바이스 파일)에 접근해서 이 보조기억장치의 정보들을 볼 수 있는 프로세스가 있을 것이다.
  • 대표적으로 탐색기.

실시간 감시 엔진

• 운영체제에서 드라이버와 요소 사이의 공간을 하나 만들어서 둔다.
  • 예를 들어, 이 공간이 필터라고 하고 필터는 I/O를 모니터링한다고 하자.
  • 그러면 프로세스에서 내려오는 Request를 필터가 감시한다. → 바이러스인지 아닌지 검사 후, 바이러스라면 차단하고 아니라면 넘어간다.
  • 이러한 필터를 실시간 감시 엔진이라고 한다.

가상화

• 하드웨어를 소프트웨어로 구현, 즉 소프트웨어화하는 것을 가상화라고 한다.
• 기본적인 원리는 하드웨어를 소프트웨어로 구현해내는 기술이 가상화 기술이다.

가상 메모리 소개

가상 메모리 시스템

Page와 Paging, Non-paging

• 페이징 파일은 운영체제에서 RAM처럼 사용하는 하드 디스크의 영역이다.
• 예를 들어 8GB의 RAM이 있고 프로그램 10개를 실행할 수 있다고 하자.
  • 이때, 15개를 실행해야 한다면 HDD 영역의 일부를 끌고 와서 RAM인 것처럼 연결시켜준다.
  • 속도는 느려지겠지만 15개가 실행된다.
  • Page라고 하는 조각난 단위를 하드디스크와 램 사이를 번갈아 왔다갔다하며 공간 이동을 한다.

page-in/out

• 하나의 프로세스가 실행될 때, 그 프로세스에게 부여하는 메모리 공간이 VMS(Virtual Memory Space)이다.

• 크롬이라는 32bit Application이 있다고 가정하자.

• OS가 크롬에게 4GB의 메모리를 부여한다.

• 공간을 쓸 때 4KB 가량의 Page라는 조각 단위가 있다.

  • 따라가보면 실제로 RAM 영역 공간일 수도 있고 HDD 영역일 수도 있다.

• MS Word 프로그램을 동시에 실행한다면

  • 워드가 RAM을 달라고 요청하는데 공간이 없다면, OS는 공간을 확보하기 위해 RAM을 사용하던 애들을 HDD로 이사시킨다.

• 이렇게 RAM에서 HDD로 Page가 쫓겨나는것을 Page-out 또는 Swap-out이라고 한다.

• 반대로 들어오면 Page-In 또는 Swap-In이라고 한다.

가상 메모리 시스템의 단점

• 프로그램 A와 B가 실행되고 있을 때, 각 프로그램에 부여된 공간을 페이지 단위로 잘라서 실제로 사용되는 영역(페이지 단위로 사용되는 것)만 어떤 메모리인가에 매핑해준다.
• 만약 A가 메모리를 많이 사용하고 있는데 B를 사용하게 된다면, 운영체제는 RAM의 공간을 HDD로 page-out 시켜버린다.
• 컴퓨터가 RAM이 부족하면 다른 프로그램으로 스위칭할 때 하드디스크에 대한 읽기 쓰기가 빈번히 벌어진다.
  • 프로그램을 스위칭할 때마다 RAM에서 HDD로 공간을 보내고, 다시 HDD에서 읽어오는 작업을 거친다.
• 운영체제는 page-in/out 시 프로그램을 잠깐 다 멈춘다.
• 정리하자면, 부족한 공간을 하나의 메모리로 논리적으로 추상화해주니까 돌아는 가지만 매우 느리다.

가상 메모리 시스템을 사용하는 이유

• 각 프로세스 공간을 완벽하게 분리하고 통제할 수 있다.
• 프로세스 오류가 운영체제에까지 영향을 주지 못하도록 차단할 수 있다.
  • 다른 프로그램에 영향을 주는 것도 막을 수 있다.
• 메모리가 부족해도 여러 프로그램이 작동하는 등 효율적으로 활용할 수 있다.

추가적으로

• 더 깊은 내용은 운영체제를 공부해야 한다.
• C/C++로 프로그램을 만들면 그 안에서 메모리를 직접 관리하는데, 이 메모리는 기본적으로 다 가상 메모리이다.
• 커널 모드 소프트웨어를 개발하는게 아니라면 기본적으로는 모두 가상메모리이다.

Reference

넓고 얕게 외워서 컴공 전공자 되기 | 널널한 개발자 - 인프런

디지털 회로와 덧셈

어떻게 하면 CPU를 제작할 수 있을까?

• CPU는 전자식 계산기다.
  • 산술 연산을 할 수 있는 계산기
  • 전자식인 이유는 빠르기 때문이다.
  • 보통 사칙 연산, 그 중에서도 더하기부터 만든다.

디지털 회로

• A와 B는 Input

컴퓨터가 덧셈하는 방법

반가산기

• 덧셈 연산을 수행하기 위한 논리회로

• 2진수 $1 + 1$은 2진수 $10_{(2)}$이다.
• A가 1, B가 1이면 XOR 연산결과 S는 0이다.
  • A와 B는 1bit이다.
• 동시에 A가 1, B가 1이면 AND 연산결과 C는 1이다.
  • 이 1은 자리 올림(Carry)이다.

반가산기의 단점

• 반가산기는 1bit 이진수 두 개로 덧셈 연산을 수행한다.
• 예를 들어 65라는 숫자는 16진수로 0x41이다.
  • 41은 각각 ‘0100’과 ‘0001’로 표현한다. → 즉, 8비트
  • 그럼 반가산기도 8개가 필요하다.
• 자리올림이 발생하기 때문에, A와 B뿐만 아니라 자리올림도 포함하여 3가지를 더해야 한다.
  • 세 개의 비트를 합산할 수 있는 로직이 필요하다.

전가산기

💡 이걸로 더하기를 만들 수 있다.

• 자리올림 수까지 포함하여 덧셈 연산을 수행한다.

• 전가산기 4개를 병렬로 이으면 4bit 전가산기가 된다.

컴퓨터가 뺄셈하는 방법

보수의 덧셈

• 보수를 덧셈하면 자동으로 뺄셈이 이루어진다.
• 6에 4를 더하면 10이다.
  • 즉, 4는 6에 대한 10의 보수이다.
  • 10의 보수는 수에 얼마를 더해야 10이 될까를 찾는 것이다. 6에 4를 더하면 10이 되므로, 4는 6에 대한 10의 보수이다.
• 13 - 6은 7이다.
  • 13에서 ‘6에 대한 10의 보수 4’를 더하고 10 자리에서 1을 빼도 역시 7이다.

2진수의 덧셈

• 2진수에서 0은 1로, 1은 0으로 뒤집으면 1의 보수가 된다.
  • Not Inverter를 사용하면 된다.
  • Not 게이트를 Inverter라고 부른다고 한다.
• 1의 보수에 1을 더하면 2의 보수이다.
• 어떤 숫자에 2의 보수를 더하면 자동으로 2진수 뺄셈이 된다. 단, 자리올림은 버린다.

컴퓨터의 뺄셈

• 컴퓨터는 보수를 구해서 더하게 하는 방식으로 구현되어 있다.
• 이를 응용해, 곱하기는 여러 번 더하면 되고 나누기는 여러 번 빼면 된다.
  • 사칙연산(덧셈, 뺄셈, 곱하기, 나누기)이 된다.

CPU가 곱하고 나누는 방법

shift

• 곱셈을 보다 효율적으로 하기 위해 등장했다.
• 비트를 왼쪽/오른쪽으로 미는 것이다.
  • 2진수 상태에서 비트를 왼쪽으로 한 칸 밀면 곱하기 2한 효과가 난다.
  • 2진수 상테에서 비트를 오른쪽으로 한 칸 밀면 곱하기 2한 효과가 난다.

컴퓨터가 곱셈하는 방법

• 4비트로 5를 표현하면 ‘0101’이다.
• 4비트 ‘0101’을 왼쪽으로 한 칸씩 밀면(Shift) ‘1010’이다.
• 맨 오른쪽에 0이 채워진다. (Zero Padding)
• 4비트로 표현하는 2진수 ‘1010’은 10이다.
• 왼쪽으로 한 칸 밀면 곱하기 2, 두 칸 밀면 곱하기 4가 된다.

홀수 곱셈

• Shift 후 한 번 더 더해주거나 하는 식으로 계산한다.
• 참고할만한 사이트: 2진수의 곱셈과 나눗셈에 관한 질문입니다. 도와주세여~ | KLDP

컴퓨터가 나눗셈하는 방법

• 4비트로 6을 표현하면 0110이다.
• 4비트 0110을 오른쪽으로 한 칸씩 밀면 0011이다.
• 맨 오른쪽에 0이 채워진다. (Padding)
• 4비트로 표현하는 2진수 0011은 3이다.

0으로 나누기

• 나눗셈은 뺄셈이다.
  • 즉, 어떤 수 X에서 Y를 뺀다면 결과 S가 Y보다 작은 수가 나올 때까지 X(S)-Y를 반복한다.
• 7을 0으로 나누면?
  • 7에서 0을 빼면 7이고, 7은 0보다 크다.
  • 7에서 0을 계속 뺀다면 언젠가는 0보다 작은 숫자를 만날 수 있는가?
  • 만날 수 없다면 뺄셈 연산은 언제 끝날까?
    • 무한히 반복한다. CPU가 열을 발생시키다 펑!
    • 범용 CPU는 이러한 말도 안되는 연산은 소프트웨어 인터런트가 발생하면서 연산을 해주지 않는다.

컴퓨터가 연산하는 과정

컴퓨터

• CPU는 연산장치이다. (비메모리)
  • 메모리가 아닌, 즉 저장할 목적이 아닌 연산이 목적이다.
• RAM은 메모리 반도체이다. (메모리)
  • 정보를 담는 저장이 목적이다.
• SSD나 하드디스크같은 보조기억장치에서 정보를 가져와서, CPU로 옮겨서 연산한다.
  • 운영체제가 해주거나 하드웨어 수준에서 하거나 한다.
  • 즉, 이 과정에서 우리가 뭔가 하지 않는다.

메모리 관리

• RAM을 보면 일련번호마다 공간이 존재하고, 그 공간에 정보를 저장한다.
  • 일련번호는 42억 9천만 정도 되는데, $2^{32}$, 즉 32bit이다. (4GB)
  • 그래서 32비트는 특수 목적 외엔 사용하지 않는다.
  • 64비트는 이론상 16 엑사바이트까지 컨트롤이 가능한데, 물론 윈도우 운영체제는 거기까지 지원하지는 않는다.
• 0번과 1번은 OS가 사용한다.
• CPU는 메모리에서 가져온 값을 레지스터라는 임시 공간에 담는다.
  • 이미지 상에선 결과가 밑으로 떨어졌는데, 실제론 3에 덮어씌우기 되는 식으로 처리된다.
• ALU(arithmetic and logical unit)이 연산한다.

연산 과정

1. RAM같은 메모리에서 정보를 가져와서 레지스터에 담는다.
2. ALU를 통해서 산술 연산을 실시한다.
3. 결과를 다시 메모리에 보낸다.

추가 정리

• RAM을 1차 메모리라고 한다.
  • RAM은 메모리 반도체가 컴퓨터가 연산하는데 가장 서포트해주는 역할을 중추적으로 해주고 있다.
• SSD(HDD)같은 애들을 2차 메모리라고 한다.
• 레지스터는 이름이 A, B, C 이런 식으로 되어 있다.
  • 뒤에 X가 붙기도 하고 앞에 E가 붙기도 한다.

컴퓨터가 기억공간을 관리하는 방법

기억장치의 종류와 역할

• CPU 수준에서 가지고 있는 메모리
  • CPU가 연산을 할 때는 레지스터까지 끌고 와야 한다.
• 컴퓨터 내부의 내부 메모리 (그 중 RAM은 1차 메모리가 된다)
• External로 넘어가면 2차 메모리 정도로 분류한다.
  • 이때부터 주변 기기로 보면 된다.

CPU의 속도

• CPU의 속도는 무척, 제일 빠르다.
• CPU가 4.xGHx(4.x기가 헤르츠) 정도면 RAM은 1.xGHz쯤 된다.
  • 헤르츠는 1초에 몇 번 주파수라는 의미다. 즉, 주파수 단위.
  • 그럼 RAM을 왜 쓰는 걸까?
• CPU와 2차 메모리의 속도 차이는 갭이 더 크다.
  • 이러한 갭을 극복하게 위해 중간 영역(Cache memory, RAM)이 있다.

휘발성

• Register에서 RAM까지는 휘발성 메모리이다.
  • 전원이 꺼지면 그 안의 내용이 모두 날아간다.
• HDD나 SSD같은 것들이 RAM만큼 속도가 빨라진다면 RAM은 필요가 없을 것이다.

가격

• 밑으로 내려갈 수록 용량이 커지고 속도가 느려진다.
• 위로 올라갈 수록 속도는 빨라지지만 값이 비싸져서 대용량으로 쓰지도 못한다.
• 그래서 연산을 하는 CPU 안에 들어있는 레지스터는 극소량의 메모리이다.
  • 보통 메모리로 분류하지 않고 CPU의 일부라고 본다.
  • Cache까지도 CPU 안에 들어간다.

캐시 메모리의 역할

• RAM이 CPU에 비해 속도가 많이 느려서, CPU는 미리 예측을 한다.
• 저장된 정보는 두 가지로 나뉠 수 있다.
  • 프로그램 코드
  • 연산 대상
• CPU는 각각에 대한 것을 미리 예측해서 캐시 메모리에 옮겨둔다.
  • 예를 들어, 연산 중에 A도 연산 대상이 되겠다고 예측하고 미리 읽어서 캐시 메모리에 옮겨둔다.
• 즉, RAM과 CPU의 속도 차이를 극복하기 위해 캐시 메모리같은 게 있다.
  • 램 메모리는 속도 차를 극복하기 위해 존재하는 걸 수도 있다.
  • 캐시는 확실히 CPU와 RAM 사이의 속도 차를 극복하기 위해서 존재한다.

캐시 폴트

• 히트가 되지 않고 미스가 난 것이다.
• 다시 말해, 예측한 것이 맞지 않았을 경우.

컴퓨터가 기억공간을 관리하는 방법

레지스터와 캐시는 CPU의 일부로 본다. CPU는 관리를 한다고 보기 어렵고, 캐시는 CPU 스스로 알아서 통제한다.

• 컴퓨터는 기본적으로 모든 것이 다 ‘숫자’이다.
• 정보가 저장된 위치도 ‘숫자’ (보통은 일련번호)로 표시한다.
  • RAM은 일련번호로 관리한다.
  • 이러한 숫자를 메모리 주소라고 한다.
• 이 같은 관리 체계는 아파트 단지에서 각 가구를 동, 호 숫자로 관리하는 것과 유사하다.
• 레지스터, 주 기억장치(RAM), 보조 기억장치(HDD, SDD)를 관리하는 방법은 조금씩 다르다.
  • 레지스터는 개별 기억공간마다 고유 이름을 붙인다.
  • 주 기억장치는 일련번호(주소)를 붙인다.
  • 보조기억장치는 트랙(Track) 번호와 섹터(Sector) 번호를 붙여 관리한다.
    • 파일(File)의 등장

프로그램 실행 시

• 하드디스크에 프로그램이 설치된다.
• 설치된 프로그램을 실행시키면, 프로그램은 RAM 메모리로 카피되어 올라온다.
• 프로그램 내부의 어떤 명령들을 CPU에게 보내서 연산을 시킨다. → 실행

HDD, SSD와 파일 시스템

주 기억장치

• 주 기억장치 공간은 ‘일련번호’로 관리한다.

HDD의 논리적 구조

• 자기 디스크 원판이다.
• 자기 디스크의 마그네틱에 자성 정보를 저장하는 방식
• 중앙에 Spindle 모터가 붙어 있어서 고속으로 회전하고 있다.
  • 하드디스크의 어떤 스펙을 논할 때 이 디스크 회전 속도를 이야기한다.
  • ex) 물리적으로 몇천, 몇백 RPM이다.
• 헤드는 디스크 표면에 붙는 게 아니다.
  • 헤드가 표면에 붙으면, 고속회전하다 보니 표면을 긁다가 헤드 자체가 불탈 수도 있다.
  • 위 상황을 막기 위해 산소 대신 다른 걸 넣는 등… 온갖 방법을 한다.

트랙과 섹터

• 논리적으로 봤을 때, 어떤 개념으로 관리체계에 따라 나눈다.
  • 관리체계는 트랙과 섹터
• 물리적으로도 트랙과 섹터로 나뉜다.
  • 디스크 제조사마다 다른데, 로우 레벨이라고 얘기를 한다.
• 섹터에 정보를 기술한다.
• 섹터 하나에 데이터를 Write한 후, 다시 Write하면 Overwrite가 된다.
  • overwrite를 반복하면(ex. 몇 십만번) 섹터가 망가져서 못 쓰게 된다.
  • 이렇게 손상되어서 사용할 수 없게 된 섹터를 Bad Sector라고 한다.
  • 따라서 빈공간을 위주로 채워서 쓴다. → 운영체제가 관리
• 논리적 구조 상에서 섹터 하나의 용량은 보통 512 바이트 정도 잡힌다.

조각 모음의 의미

• 섹터가 512B 정도 될 때, 4개(클러스터)로 묶으면 약 2KB정도 된다.
• 보조기억장치를 쓸 때는 파일의 형태로 많이 사용한다.

다음 두 가지 경우를 생각해보자.

• 용량이 100 바이트일 때
  • 한 섹터에 100바이트를 저장하고, 섹터 조각 하나를 완전히 다 쓴 걸로 처리한다. → 약간의 낭비 발생
  • 섹터를 촘촘히 채워쓰려고 하면 CPU를 더 쓰기 때문에 연산과 로직이 복잡해진다.
• 용량이 512 바이트 이상일 때
  • 같은 트랙 다음 섹터까지 저장한다.
  • 다음 섹터에 이미 데이터가 있으면, (강의에선 다른 트랙으로 감) 다음 빈 섹터로 워프(건너뛰기)하여 저장한다.
  • 디스크가 회전하면서 데이터를 읽는데, 이렇게 공간이 조각나있으면 I/O(입출력)를 할 때 입출력의 어떤 성능, 즉 속도 문제가 발생한다.
• 조각 모음을 하면 사이에 껴있던 데이터를 다른 곳으로 이동하고, 한 트랙에 쭉 잇도록 만들어 준다.
• 요즘은 OS가 조각 모음을 알아서 잘 하고 있다.
• 오류 검사는 디스크 상에 오류가 있는지 검사
  • Bad Sector같은 것

파일이 저장되는 방법 (파일 시스템)

• 운영체제별 파일 시스템이 있다.
  • MAC(매킨토시)는 애플의 파일 시스템
  • 윈도우는 NTFS (NT라는 코드의 파일 시스템)
• 기본적으로 모든 파일 시스템은 FAT이라는 형태를 가지고 있다.

File Allocation Table (FAT)

• 파일의 위치를 알려준다.
• 메타 데이터같은 정보들을 표 형태로 관리한다.
  • 몇 번 트랙, 몇 번 섹터에 무엇이 저장되었고 크기가 무엇인지
• 파일을 삭제하면 디스크에서 완전히 삭제하지 않고, 테이블의 칼럼(Delete 여부)에 삭제되었다고 체크한다.
  • 파일 명은 펀치를 한다. → 앞 글자 몇 개를 #으로 바꾼다거나?
  • 즉, 관리 체계 상에서 지워졌다고 마킹만 되는 것이다.
• 복원은 이 테이블 정보를 찾아서 분석한 다음, 위치와 데이터가 살아있다면 찾아가서 데이터를 복사하는 것이다.
  • 이런 걸 해주는 프로그램 소프트웨어가 있다.

마스터 부트 레코드 (MBR)

• 0번 트랙 0번 섹터를 말한다.
• OS의 부트 로더라고 하는 코더가 들어간다.
• 컴퓨터 전원을 켰을 때, MBR을 찾아가서 OS 부트 로더 코드를 가져와서 운영체제 프로그램을들 하나씩 메모리에 적재해서 실행한다.
  • 이걸 Booting이라고 한다.
• 바이러스가 MBR을 못 쓰게 만들면(몇 만번쯤 오버라이트한다거나) 컴퓨터가 부팅이 안된다.
• 따라서 마스터 부트 레코드는 여러 차원에서 보호를 한다.

Format

• USB를 하나 샀는데 파일 시스템이 EXFAT로 되어 있는데, NTFS를 쓰겠다고 하면 파일 시스템을 바꿔치기하면서 포맷을 한다.
  • Allocation Table을 NTFS 형식대로 만들고, 클리어시킨다.
• 파일 시스템을 디스크에 올린다, 적용한다.
  • 트랙과 섹터로 나눠준다는 것
• 빠른 포맷은 FAT에 해당되는 메타 데이터를 지우는 것이다.
• 느린 포맷은 전체 트랙과 섹터를 찾아서 모두 0으로 오버라이트하는 것이다.

SSD

• SSD도 똑같이 트랙과 섹터로 관리한다
• 자기 디스크에서 칩으로 바뀐 것 뿐이다.
  • 근본적인 측면에서는 미디어가 다른 것 뿐이다.
  • 관리적인 측면에서 따지자면 똑같다.
• 조각 모음은 의미가 없다.
  • 회전하는 것이 아니다 보니 속도가 굉장히 빠르고, 물리적인 것이 아니라 칩 자체의 읽기쓰기 성능에 따라 결정이 난다.

Reference

넓고 얕게 외워서 컴공 전공자 되기 | 널널한 개발자 - 인프런

CPU 기초

• 제일 중요한 것은 코어(Core) 개수
  • 연산을 수행하는 주체를 코어라고 한다.
• Thread는 실행의 단위이다.
  • 코어가 6개고 쓰레드가 1000개면, 1000개의 일거리를 6개의 코어가 분담해서 처리한다.

1비트와 디지털

1bit와 2수 (다른 말로 디지털)

• 1 비트란 ‘전기 스위치 1개’를 의미한다.
  • 비트는 소문자로 사용하며, 복수형으로 사용하지 않는다.
• 전기가 흐르는 On 상태는 1
• 전기가 흐르지 않는 Off 상태는 0
• 2진수는 0과 1로 표현하는 수

4bit란

• 스위치 4개를 조합해서 4bit라고 한다.
• 조합은 $2^4$ 이다.
• $0000$ 이란 2진수가 있으면, 각 자리수는 8, 4, 2, 1이다.

16진수

2진수는 인간이 이해하기에는 너무 어렵고, 숫자가 길어질 수 있다. 따라서, 컴퓨터의 데이터를 표현할 때 16진법도 많이 사용한다.

16진법은 수가 15을 넘어가는 시점에 자리 올림을 한다. 수학적 표기 방식으로는 아래첨자 16을 사용하고, 코드 상으로는 앞에 0x를 붙어 16진수라는 것을 표기한다.

U+라고 표기하기도 한다(유니코드에서 사용).

자리 올림을 쉽게 이해하는 법

0부터 9까지는 동일하게 세고, 10부터는 주먹을 쥔 상태로 이해를 한다.

• 주먹을 쥔 상태: 10를 A로 표현
• 손가락 하나를 편 상태: 11를 B로 표현
• 손가락 두 개를 편 상태: 12를 C
• 손가락 세 개를 편 상태: 13를 D로 표현
• 손가락 네 개를 편 상태: 14를 E로 표현
• 손가락을 모두 편 상태: 15를 F로 표현

2진수 → 16진수로 변환

16진수는 4비트이다. $2^4$ 는 16이므로.

10진수도 있는데 왜 16진수를 사용하느냐 하면, 그것은 16진수와 2진수 간의 변환이 간단하고 쉽기 때문이 아닌가 한다.

아무튼, 16진수는 4비트로 표현할 수 있으므로 2진수에서 16진수로 변환할 때는 각 숫자를 4비트로 표현하기만 하면 된다.

즉, 4비트를 16진수 하나라고 생각하면 된다.

16진수 → 2진수로 변환

4비트씩 떼어, 그것을 2진수로 표현한다. 즉, 4비트는 16진수 한 자리 숫자다.

C언어같은 데에서는 0xF4처럼 앞에 ‘0x’를 붙여주기도 한다.

16진수 표기가 사용되는 예

1. 색상 표현

• 빛의 삼원색, RGB
• RGB는 각 컬러가 8비트를 사용한다. 즉, $2^8=256$ (0~255)
• CSS에서도 16진수로 색상을 표기한다.
  • #B7 1C 1C → 8비트가 3개니까 24bit 컬러가 된다.
  • 위에서 8비트를 더하면 32비트 트루 컬러가 된다.

2. 컴퓨터 하드웨어 주소 표현

• 컴퓨터 내부의 어떤 정보들을 표현할 때, 주소같은 수치적인 표현들이 있을 때는 거의 16진수로 표기한다.
• 예를 들어, 비주얼 스튜디오에서 C언어의 메모리의 내용을 조사할 때 메모리 윈도우라는 내용을 본다. 이 내용은 모두 16진수로 되어 있다.

3. 메모리 값 표현

• 메모리 값은 정보.

정리

• 컴퓨터에서 모든 정보는 디지털이다.
• 디지털은 0과 1로 표현이 된다.
• 4비트씩 묶으니 전부 16가지가 있어서 16진수로 표현한다.

외워야 할 단위 체계와 숫자

바이트

• 8 비트를 하나로 묶어 1바이트(byte)라고 한다.
  • 1비트는 너무 작아서 용량으로는 잘 안치고, 1바이트부터 용량 얘기를 하기 시작한다.
• 1바이트는 영문자 한 글자가 저장될 수 있는 메모리 크기이며, 관리의 최소단위이다.
  • 한글 한 글자를 저장하려면 2 바이트가 필요하다. (코드 체계에 따라 다르기도 하다)
  • 가장 작은 메모리의 단위가 1 바이트이다.
  • 즉, 메모리는 1바이트 단위로 관리한다.

정보 단위

비트 Bit

비트는 표현의 최소 수준이다.

컴퓨터는 0과 1만 이해할 수 있다. 전기가 흐르는 상태를 1로 따진다면, 전기가 흐르지 않는 상태를 0으로 표현하는 식이다.

비트는 컴퓨터가 이해하는, 0과 1을 표현하는 가장 작은 단위이다.

1비트로는 2가지의 정보(꺼짐과 켜짐)을 표현할 수 있다. 2비트로는 총 4개를, 3비트로는 8개의 정보를 표현할 수 있다.

즉, 비트 수가 n개라면 $2^n$ 를 표현할 수 있다.

비트의 단위

용량을 말할 때는 바이트 단위

우리는 평소에 비트 단위로 말하지 않는다. 비트보다 큰 단위로 말하는데, 그것은 아래와 같다.

이런 단위를 1024개씩 묶은 단위는 kiB(키비바이트), GiB(기비 바이트)라고 한다.

일부 문서는 1024씩 묶은 단위가 표에 정리한 단위다, 라고 이야기하는데 실제로는 둘은 단위가 다르다.

과거에는 정보의 단위가 크지 않았으니 1000개씩 묶으나 1024개씩 묶으나 별 차이가 없어서 두 용어를 혼용해서 썼으나, 최근에는 다루는 정보의 크기가 커지면서 그 차이도 커지게 됐다.

따라서, 1000씩 묶은 단위와 1024개씩 묶은 단위를 구별해서 쓰는 추세이다.

워드 word

CPU가 한 번에 처리할 수 있는 정보의 크기 단위를 말한다. 예를 들어, 컴퓨터가 한 번에 32비트씩 다룰 수 있다면 1워드 크기는 32비트가 된다.

워드 단위의 파생 단위도 생겼는데, 아래와 같다.

• 하프 워드 (half word): 워드의 절반 크기
• 풀 워드 (full word): 워드 크기
• 더블 워드 (double word): 워드의 두 배 크기

컴퓨터가 글자를 다루는 방법

컴퓨터는 0과 1만 이해할 수 있다. 그러므로, 우리 인간이 사용하는 문자를 컴퓨터에게 이해시키기 위해서는 0과 1로 표현해야 한다.

문자 집합 Charter set

문자 집합이란, 컴퓨터가 이해할 수 있는 문자의 모음이다. 우리가 컴퓨터가 이해할 수 있도록 문자 하나에 숫자 하나를 매칭하고, 이 숫자는 이런 문자라는 의미야 하고 약속한 것과 비슷하다.

이 문자 집합은 여러 개가 있을 수 있으며, 매칭한 숫자를 ‘코드 포인트’라고 한다.

• 컴퓨터가 글자를 표현하기 위해 숫자와 글자를 매핑한다.
• 이러한 규약을 ‘코드체계’라고 한다.

코드 체계의 예

• 십진수 65

  = 컴퓨터에겐 영문 대문자 ‘A’

  = 16진수로는 0x41

• ‘B’는 66, ‘C’는 67이 된다.

💡 문자 1과 숫자 1은 다르다!

ASCII 코드

• American Standard Code for Information Interchange
• 미국에서 사용하는 표준 코드체계
  • 회사 별로 만드는 컴퓨터마다 사용하는 코드체계가 다르면, 서로 표기할 때 깨지는 문제가 발생한다. 이를 위해 국가가 표준을 만든 것이다.

알파벳, 아라비아 문자, 몇 개의 특수문자, 제어문자를 포함한 문자 집합으로, 8비트를 사용한다.

당연히 128개밖에 표현을 못하므로, 영어 외의 다른 언어를 표현할 수가 없다. 그 외의 특수문자도 마찬가지다.

이 8비트 중에 1비트는 오류 검출을 위한 패리티 비트로 사용하기 때문에, 실질적으로 문자를 표현하는 데에 사용하는 비트는 7비트이다.

7비트로는 128개의 문자를 표현할 수 있다. A는 65, a는 97 등이 그 예다. 여기서 A는 문자, 65는 코드 포인트가 된다.

그래서 우리는 언어별 문자 집합을 만들었다.

KS X 1001와 KS X 1003

이 둘은 한국어를 표현하기 위해 만들어진 문자 집합이다. 이 문자집합를 인코딩하는 언어는 euc-kr 이다.

유니코드

그런데, 이렇게 국가별로 언어를 정의하면 호환성이 너무 복잡해진다. 예를 들어 한국어, 영어, 중국어, 일본어를 제공하는 웹 사이트를 만들고 싶으면 총 4개의 문자 집합과 인코딩을 사용해야 하는 것이다.

그래서 등장한 것이 바로 통합된 문자 집합, 유니코드이다. 유니코드는 전 세계의 문자를 모두 담아내려고 한 문자 집합이며, 문자 하나 당 16비트를 사용한다.

이 유니코드를 인코딩하기 위해 나온 것이 utf-8, utf-16 등 이다.

인코딩

이렇게 매칭된 숫자는 기본적으로 16진수로 표현되어 있다. 당연하게도 컴퓨터는 이 숫자를 이해하지 못한다. 이해하려면 0과 1로 바꿔줘야 한다.

인코딩은 이렇게 매칭된 코드 포인트를 컴퓨터가 이해할 수 있도록 변환하는 것을 말한다.

💡 16진수를 사용하는 이유는, 2진수와 12진수를 서로 변환하는 과정이 가장 간단하기 때문이다.

EUC-KR

한국어 문자 집합을 인코딩하기 위해 사용하는 인코딩 방식이다.

UTF

유니코드를 인코딩하기 위해 사용하는 인코딩 방식이다. 이 인코딩 방식은 여러 가지가 있다.

대표적인 예로 UTF-8이 있는데, 각 문자별로 가변적인 비트 수를 사용한다. 코드 포인트의 범위가 어디에 속하느냐에 따라 달라지는 것이다.

디코딩

인코딩이 컴퓨터가 이해할 수 있도록 0과 1로 바꾸는 것이라면, 디코딩은 역으로 인간이 이해할 수 있도록 변환하는 것을 말한다.

보통 디코딩은 잘 다루지 않는다.

바이너리

• 숫자와 글자를 구별하지 않고 정보를 말할 때는 바이너리(Binary)라고 한다.
  • 컴퓨터 안에 모든 정보는 바이너리다. (2진수로 표현되니까)
  • 문자로 표현할 수 있으면 텍스트라고 부르기도 한다. (바이너리 안에 텍스트 포함)
  • 이진수로 나열해서 쭉 보는 정보를 바이너리라고 한다.
• 엔터는 ‘0D 0A’ 이다.
  • Escape Sequence (\r\n)

위키백과에 따르면, 바이너리는 다음의 의미로도 쓰인다.

• 바이너리는 0과 1, 두 숫자로만 이루어진 이진법을 의미한다.
• 컴퓨터에서 정보는 이진 형태로 저장되며, 바이너리는 이진 파일(텍스트 형태가 아닌 이진 형태로 인코딩된 파일. 많이 쓰이진 않는다)을 의미한다.
• 프로그램 배포에서 소스코드가 아닌 실행 파일을 나타낸다. 출처: https://ko.wikipedia.org/wiki/바이너리

컴퓨터가 사진을 다루는 방법

픽셀

• 모니터 화면 상 ‘점’ 하나를 화소(Pixel)이라 한다.
  • 화소가 작을 수록(=점이 작을 수록) 해상도가 높다고 한다.
  • 하나의 화소는 RGB를 포함한다.
• 여러 점들을 모아 사진을 만들 수 있다.
  • 사진은 화소들의 집합체
• 화소 하나를 표현하는데 8비트 16비트, 24비트, 32비트 정보가 필요할 수 있다.
  • 보통은 24비트로 표현한다.
  • RGB니까 각각 8비트씩
  • 투명도를 포함하여 32비트로 표현하기도 한다.

빛의 3원색

• 빛의 3원색은 Red, Grean, Blue
• 이 점에 착안해 RGB 컬러가 등장한다.
• 화소가 작을 수록 사진이 매끄럽다. (고해상도)

투명도

• 두 개의 픽셀이 겹쳐 있을 때, 앞에 나와있는 화소가 어느 정도의 투명도를 갖느냐에 따라서 겹친 지역이 다르게 렌더링 된다.
  • 여기서 렌더링은 화면에 표시해준다를 고급스럽게 표현한거라고 이해하고 넘어가자.
• 투명도를 결정하는 걸 다른 말로 알파 채널이라고 한다.
• 알파 채널을 포함하여 RGBA라고도 이야기를 한다.
  • 32비트 트루 컬러

RGB 색상 표현과 픽셀

• 수직수평 해상도가 각각 가로 1024, 세로 768의 이미지가 있을 때, 화소가 4바이트(32비트)면 4*768KB정도 된다.
  • 대략 2.8MB 가량
• RGB다, RGBA다를 명시해서 모든 컬러셋의 집합체를 비트맵이라고 한다.
  • 비트맵 파일은 각 화소별로 RGB값 32비트 비트맵일 때 걔가 어떤 값이에요라고 쓴 것이다.
• 각 픽셀의 정보를 일일이 다 나열한 것이 로우 비트맵
• 실제로 비트맵을 통째로 쓰는 경우는 없다.
  • 보통 JPG 등으로 압축해서 쓴다.

비트맵(Bitmap) 이란?

비트맵은 디지털 이미지를 저장하는 방식 중 하나입니다.

각 픽셀(화소)의 정보를 비트(0과 1) 단위로 저장하기 때문에 비트맵이라고 불립니다.

비트맵 이미지는 사진처럼 실제 이미지를 표현하는 데 적합하며, .bmp, .jpg, .png 등 다양한 파일 형식으로 저장됩니다.

비트맵을 .jpg로 저장할 수 있다는 것은 비트맵 이미지를 JPG 형식으로 변환할 수 있다는 의미이지, 비트맵 자체가 JPG라는 의미는 아닙니다. 비트맵과 JPG는 서로 다른 이미지 저장 방식입니다.

비트맵 이미지의 특징:

• 픽셀 기반: 이미지를 구성하는 각 픽셀의 색상 정보를 저장합니다.
• 높은 해상도: 사진처럼 실제 이미지를 표현하는 데 적합합니다.
• 용량: 이미지 크기와 해상도에 따라 용량이 커질 수 있습니다.
• 확대: 이미지를 확대하면 픽셀이 보이고 화질이 저하될 수 있습니다.

비트맵 이미지의 장점:

• 실제 이미지를 사실적으로 표현할 수 있습니다.
• 다양한 색상을 표현할 수 있습니다.
• 사진 편집 프로그램에서 쉽게 편집할 수 있습니다.

비트맵 이미지의 단점:

• 용량이 커질 수 있습니다.
• 이미지를 확대하면 화질이 저하될 수 있습니다.
• 벡터 이미지에 비해 편집 기능이 제한적일 수 있습니다.

비트맵 이미지의 활용:

• 사진
• 그림
• 로고
• 아이콘
• 웹 이미지

비트맵 이미지는 다양한 분야에서 활용되고 있습니다. 사진 촬영, 그림 그리기, 웹 디자인 등 다양한 작업에 비트맵 이미지를 사용할 수 있습니다.

Reference

넓고 얕게 외워서 컴공 전공자 되기 | 널널한 개발자 - 인프런

[컴퓨터 공학 기초 강의]『혼자 공부하는 컴퓨터 구조+운영체제』

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

동적 계획법 (Dynamic Programming)

사실 모든 알고리즘 문제들은 완전 탐색을 이용해 정답을 도출할 수 있다. 단지 비효율적인 연산과 시간을 없애고, 답을 효율적으로 도출하기 위해 여러 알고리즘 기법이 생긴 것이다.

• 동적 계획법(DP)은 가장 광범위한 여러 유형의 문제를 논리적인 사고를 이용해 효율적으로 풀 수 있는 알고리즘이다.
• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이다.

핵심 이론

원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
   • 이를 메모이제이션(Memoization) 기법이라고 한다.
4. 동적 계획법은 Top-down 방식과 Bottom-up 방식으로 구현할 수 있다.

피보나치 수열

동적 계획법의 가장 대표적인 문제이다.

• 피보나치 수열의 공식은 다음과 같다.

$$ D[N]=D[N-1]+D[N-2] $$

1. 동적 계획법으로 풀 수 있는지 확인하기

   • N번째 피보나치 수열은 N-1번째 피보나치 수열과 N-2번째 피보나치 수열의 합이다.
   • 즉, N번째 피보나치 수열을 구하는 문제는 N-1번째 피보나치 수열과 N-2번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있다.
   • 수열의 값은 항상 같다.
   • 따라서 동적 계획법으로 풀 수 있다.

2. 점화식 세우기

   • 점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.
   • 피보나치 수열의 점화식은 $D[i]=D[i-1]+D[i-2]$이 된다.

3. 메모이제이션 원리 이해하기

   • 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다.
   • 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이때 DP 테이블에 값이 저장된다. 나중에 앞의 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP 테이블에서 바로 값을 추출한다.
   • 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측변에서 많은 이점을 가질 수 있다.

4. 톱-다운 구현 방식 이해하기

   • 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수를 사용해 코드를 구현한다.

   • 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있다.

   • 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.

     ```java /**

   • Top-down 방식의 피보나치 수열

   • /

     static int[] D; public static void main(String[] args) {

     Scanner sc = new Scanner(System.in); int n = sc.nextInt();

     D = new int[n+1]; for(int i=0; i<=n; i++) {

        D[i] = -1;

     }

     D[0] = 0; D[1] = 1; fibo(n);

     System.out.println(D[n]); }

     static int fibo(int n) { // 기존에 계산한 적이 있는 부분의 문제일 경우 if (D[n] != -1) {

        return D[n];

     } // 메모이제이션: 구한 값을 바로 리턴하지 않고 // DP 테이블에 저장한 후 리턴하도록 구현 return D[n] = fibo(n-2) + fibo(n-1); }

5. 바텀-업 구현 방식 이해하기

   • 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식이다.

   • 주로 반복문의 형태로 구현한다.

   • 톱-다운 방식보다는 바텀-업 방식이 좀 더 안전한 방식이다.

     ```java /**

   • Bottom-up 방식의 피보나치 수열

   • /

     static int[] D; public static void main(String[] args) {

     Scanner sc = new Scanner(System.in); int n = sc.nextInt();

     D = new int[n+1]; for(int i=0; i<=n; i++) {

        D[i] = -1;

     }

     D[0] = 0; D[1] = 1; for(int i=2; i<=n; i++) {

        D[i] = D[i-1]+D[i-2];

     }

     System.out.println(D[n]); }

     static int fibo(int n) { // 기존에 계산한 적이 있는 부분의 문제일 경우 if (D[n] != -1) {

        return D[n];

     } // 메모이제이션: 구한 값을 바로 리턴하지 않고 // DP 테이블에 저장한 후 리턴하도록 구현 return D[n] = fibo(n-2) + fibo(n-1); }

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

순열과 조합 (Combination)

조합은 그 자체로 코딩 테스트에 자주 출제되는 주제이며, 동적 계획법을 이해하는데 기초가 된다.

• 조합은 $_nC_r$으로 표현하며, n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.
• 순열은 $_nP_r$로 표현하며, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 말한다.
• 순열과 조합의 차이는 순서의 고려 유무이다.
  • 조합에서는 1, 2, 3과 3, 2, 1을 같은 경우로 판단한다.
  • 순열에서는 1, 2, 3과 3, 2, 1을 다른 경우로 판단한다.

핵심 이론

순열

• 순열의 수학적 공식은 다음과 같다.

$$ _nP_r= \frac {n!}{(n-r)!} $$

• 예를 들어, 5개 중 3개를 순서대로 선택하는 경우의 수는 다음과 같다.
  • 첫 번째 선택은 5개를 선택할 수 있고, 두 번째 선택은 4개를 선택할 수 있고, 세 번째 선택은 3개를 선택할 수 있다.
  • 따라서 경우의 수는 $543=60$가지가 된다.

조합

• 조합의 수학적 공식은 다음과 같다.
  • $r!$은 순서가 다른 경우의 수를 제거하는 역할을 한다.

$$ _nC_r= \frac {n!}{(n-r)!r!} $$

• 예를 들어, 5개 중 2개를 선택하는 경우의 수를 구한다고 가정하자.
  • 경우의 수는 $5*4/2=10$가지가 된다.

조합의 점화식

알고리즘에서 조합을 구현할 때는 수학 공식을 코드화하는 것이 아니라, 점화식을 사용해 표현한다.

조합의 점화식은 다음 3가지 단계로 세울 수 있다.

1. 특정 문제를 가정하기

   • 예를 들어, 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정한다.

2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

   • 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정하고, 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다.

   • 다음 2가지 경우의 수를 합치면 데이터 5개 중 3개를 선택하는 경우의 수가 나온다.

     1) 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면, 이미 선택이 완료되었다고 가정한 4개의 데이터에서 2개를 선택해야 한다.

     2) 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면, 이미 선택이 완료되었다고 가정한 4개의 데이터에서 3개를 선택해야 한다.

$$
_5C_3\ =\ _4C_3\ +\ _4C_2
$$

```java
// 5개 중 3개를 선택하는 경우의 수 점화식
D[5][3] = D[4][3]+D[4][2]
```

3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

   • 이렇게 일반화된 점화식을 이용하면 조합과 관련된 모든 경우의 수를 쉽게 구할 수 있다.

     D[i][j] = D[i-1][j]+D[i-1][j-1]

이항계수 구하기 (백준 11050)

❓ 자연수 N과 정수 K가 주어졌을 때 이항 계수 $\binom{N}{K}$를 구하는 프로그램을 작성하시오.

문제 풀이

private static void answer() throws IOException {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int D[][] = new int[N+1][N+1];

    // 초기화
    for (int i = 0; i <= N; i++) {
        D[i][i] = 1;
        D[i][0] = 1;
        D[i][1] = i;
    }

    // 점화식으로 배열 완성하기
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            D[i][j] = D[i-1][j] + D[i-1][j-1];
        }
    }

    System.out.println(D[N][K]);
}

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

트리 알아보기

• 트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다.
  • 즉, 그래프의 표현으로도 tree를 표현할 수 있다.
• 트리의 특징은 다음과 같다.
  • 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
  • 루트 노드를 제외한 모든 노드는 단 1개의 부모 노드를 갖는다.
  • 트리의 부분 트리(sub tree) 역시 트리의 모든 특징을 따른다.
  • 트리의 임의의 두 노드를 이어주는 경로는 유일하다. (1개만 나온다)

핵심 이론

• 트리의 구성 요소

코딩 테스트의 트리 문제

• 두 가지 유형으로 구분할 수 있다.
  1. 그래프로 푸는 tree 문제
  2. tree만을 위한 문제
• DFS, BFS를 이용하여 푸는 tree 문제가 있다.
  • tree의 Node와 Edge는 인접 리스트로 표현할 수 있다.
• 이진 트리 & 세그먼트 트리(index tree) & LCA(최소공통조상)는 tree만을 위한 문제이다.
  • 1차원 배열로 tree를 표현할 수 있다. (1차원 배열로 구현하려면 무조건 이진 트리여야 한다)
  • 부모 노드로 이동할 때 인덱스 연산(index/2)을 통해 접근한다.

이진 트리

• 이진 트리(binary tree)는 각 노드의 자식 노드(차수)의 개수가 2개 이하로 구성된 트리를 말한다.
• 트리 영역에서 가장 많이 사용되는 형태이다

트리의 종류

이진 트리의 종류에는 다음 세 종류가 있다.

• 편향 이진 트리
• 포화 이진 트리
• 완전 이진 트리

편향 이진 트리

• 노드들이 한쪽으로 편향돼 생성된 이진 트리
• 데이터를 트리 자료구조에 저장할 때, 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다.

포화 이진 트리

• 트리의 높이가 모두 일정하며 레프 노드가 꽉 찬 이진 트리

완전 이진 트리

• 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있다.
• 마지막 레벨은 왼쪽부터 채워진 트리이다.

이진 트리의 순차 표현

코딩 테스트에서 트리 문제가 나오면 그래프의 표현 방식보다 다음 방식으로 데이터를 담는 것이 일반적이다.

• 가장 직관적이면서 편리한 트리 자료구조 형태는 ‘배열’이다.

• 이진 트리는 1차원 배열의 형태로 표현할 수 있다.

  • 만약 노드가 없다면(아직 채워지지 않는다면) 해당 공간은 비워놓는다.

    int[] tree = new int[N];
    tree[1] = A; // 루프 노드
    tree[2] = B; // 루프 노드의 자식 노드 1
    tree[3] = C; // 루프 노드의 자식 노드 2
    tree[4] = D; // B 노드의 자식 노드 1
    tree[5] = E; // B 노드의 자식 노드 2
    tree[6] = F; // C 노드의 자식 노드 1
    tree[7] = G; // C 노드의 자식 노드 2

• 트리의 노드와 배열의 인덱스 간의 상관관계는 다음과 같다.

  • 아래의 인덱스 연산 방식은 세그먼트 트리나 LCA 알고리즘에서도 기본이 되는 연산이다.

    이동 목표 노드	인덱스 연산	제약 조건 (N=노드 개수)
    루트 노드	index = 1
    부모 노드	index = index / 2	현재 노드가 루트 노드가 아님
    왼쪽 자식 노드	index = index * 2	index * 2 ≤ N
    오른쪽 자식 노드	index = index * 2 + 1	index * 2 + 1 ≤ N

세그먼트 트리 (인덱스 트리)

• 세그먼트 트리는 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태이다.
  • 구간 합에서 사용하는 합 배열은 업데이트가 잦으면 속도가 느려진다.
• 더 큰 범위는 ‘인덱스 트리’라고 불린다.
  • 코딩 테스트 영역에서는 큰 차이가 없다.

핵심 이론

• 세그먼트 트리의 종류는 다음과 같이 나눌 수 있다.
  • 구간 합
  • 최대/최소 구하기
• 세그먼트 트리의 구현 단계는 다음과 같이 나눌 수 있다.
  • 트리 초기화하기
  • 질의값 구하기 (구간 합 또는 최대/최소)
  • 데이터 업데이트 하기

구현 단계

1. 트리 초기화하기

   • 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다.

     • 트리 배열의 크기는 $2^k≥N$을 만족하는 k의 최솟값을 구한 후, $2^k*2$를 트리 배열의 크기로 정의한다.

       // 샘플 데이터 (N=8이므로, k는 3이 된다)
       int[] sample = new int {5, 8, 4, 3, 7, 2, 1, 6};
       
       // 트리 배열의 크기 size
       int size = 2^3 * 2;

   • 리프 노드에 원본 데이터를 입력한다. 이때, 리프 노드의 시작 위치를 트리 배열의 인덱스로 구한다. (시작 인덱스 = $2^k$)

       int[] tree = new int[N+1];
     
       int start_index = 8;
       tree[start_index++] = node;

   • 리프 노드를 제외한 나머지 노드의 값을 채운다. ($2^k-1$부터 1번 쪽으로 채운다)

     • 채워야 하는 인덱스가 N이라고 가정하면 자신의 자식 노드를 이용해 해당 값을 채울 수 있다.

     • 자식 노드의 인덱스는 2N과 2N+1이다.

       // 구간 합 (자식 노드들의 합)
       A[N] = A[2N] + A[2N+1];
       
       // 최대 (자식 노드 중 큰 값)
       A[N] = max(A[2N], A[2N+1]);
       
       // 최소 (자식 노드 중 작은 값)
       A[N] = min(A[2N], A[2N+1]);

> 💡 이렇게 세그먼트 트리를 구성해 놓으면 그 이후 질의와 관련된 결괏값이나 데이터 업데이트 요구 사항에 관해 좀 더 빠른 시간 복잡도 안에서 해결할 수 있게 된다.

2. 질의값 구하기

   • 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다.

     • 기존 샘플을 기준으로 한 인덱스값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야 한다.

       // 인덱스 변경 방법
       (세그먼트 트리 index) = (주어진 질의 index) + 2^k - 1

   • 질의에서의 시작 인덱스와 종료 인덱스에 관해 부모 노드로 이동하면서 주어진 질의에 해당하는 값을 구한다.

       // 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에,
       // 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고,
       // 해당 노드의 부모 노드는 대상 범위에서 제외한다.
       1. start_index % 2 == 1일 때 해당 노드를 선택한다. (두 자식 노드 중 오른쪽일 때)
       2. end_index % 2 == 0일 때 해당 노드를 선택한다. (두 자식 노드 중 왼쪽일 때)
     
       // 부모 노드를 대상 범위에서 제거하는 방법 (범위를 부모 노드로 이동)
       3. start_index depth 변경: start_index = (start_index + 1)/2 연산을 실행한다.
       4. end_index depth 변경: end_index = (end_index - 1)/2 연산을 실행한다.
     
       5. 1~4번 과정을 반복하다가 end_index < start_index가 되면 종료한다.

   • 질의에 해당하는 노드를 선택하는 방법은 구간 합, 최댓값 구하기, 최솟값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.

     • 구간 합: 선택된 노드를 모두 더한다
     • 최댓값 구하기: 선택된 노드 중 MAX 값을 선택해 출력한다.
     • 최솟값 구하기: 선택된 노드 중 MIN 값을 선택해 출력한다.

3. 데이터 업데이트하기

   • 자신의 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만, 어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 다르다.
   • 구간합에서는 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경한다.
   • 최댓값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 큰 값으로 업데이트한다. 업데이트가 일어나지 않으면 종료한다.
   • 최솟값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 작은 값으로 업데이트 한다. 업데이트가 일어나지 않으면 종료한다.

최소 공통 조상 LCA

• 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상(Lowest common ancestor)이라고 한다.
• 시간 복잡도는 트리의 높이에 밀접하다.

일반적인 최소 공통 조상 구하기

• 트리의 높이가 크지 않을 때 최소 공통 조상을 구하는 방법
• 트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다.
  • 이러한 문제를 해결하기 위해 새롭게 제안된 방식이 ‘최소 공통 조상 빠르게 구하기’이다.

구현 방식

1. 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다.

   • DFS 또는 BFS를 이용해 탐색을 수행한다.
   • 트리라는 특징 덕분에 바로 직전 탐색 노드가 부모 노드가 되고, depth를 쉽게 구할 수 있다.

2. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춘다.

   • 이때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.

3. 선택된 두 노드의 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.

   • 이때 처음 만나는 노드가 최소 공통 조상이므로 탐색을 종료한다.

최소 공통 조상 빠르게 구하기

• 일반적인 최소 공통 조상 구하기 알고리즘을 약간 변형한 형태이므로, ‘일반적인 구하기’ 원리를 정확하게 학습해야 한다.
• 서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주던 방식에서 $2^k$씩 올라가 비교한느 방식이다.
• 따라서 기존에 자신의 부모 노드만 저장해 놓던 방식에서 $2^k$번째 위치의 부모 노드까지 저장해 둬야 한다.

구현 방식

1. 부모 노드 저장 배열 만들기

   • 부모 노드 배열의 정의

     P[K][N] = N번 노드의 $2^k$번째 부모의 노드 번호

   • 부모 노드 배열의 점화식

     P[K][N] = P[K-1][P[k-1][N]]

     N의 $2^k$번째 부모 노드는 N의 $2^{k-1}$번째 부모 노드의 $2^{k-1}$번째 부모 노드라는 의미이다.

     배열에서 K는 트리의 깊이 > $2^k$ 를 만족하는 최댓값이다.

     즉, K=4라고 가정하면 N의 16번째 부모 노드는 N의 여덟 번째 부모 노드의 여덟 번째 부모 노드라는 의미이다.

2. 선택된 두 노드의 깊이 맞추기

   • P 배열을 이용해 기존에 한 단계씩 맞췄던 깊이를 $2^k$ 단위로 넘어가면서 맞춘다.

3. 최소 공통 조상 찾기

   • 공통 조상을 찾는 작업도 $2^k$ 단위로 점프하면서 맞춘다.
   • K값을 1씩 감소하면서 P배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.
   • 최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동한다.
   • K가 0이 될 때까지 반복하며, 반목문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

최소 신장 트리 (MST)

• 최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
  • 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
  • N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 $N-1$이다.
• 최소 신장 트리의 대표적인 알고리즘은 2개 가 있다.
  • 크루스칼 알고리즘
  • 프림 알고리즘
• 다른 그래프 알고리즘과는 달리 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다.
  • 에지를 기준으로 하는 알고리즘이기 대문이다.
• 사이클이 존재하면 안 되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 한다.

핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기

   • 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.
   • 에지 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.
   • 사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화한다. 리스트의 인덱스를 해당 자리의 값으로 초기화하면 된다.

2. 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

   • 오름차순 증렬은 input 데이터의 순서 조정을 위해 높은 자유도로 정렬할 수 있다.

3. 가중치가 낮은 에지부터 연결을 시도한다.

   • 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다.
   • 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않았을 때만 union 연산을 이용해 두 노드를 연결한다.

4. 전체 노드의 개수가 N이면 에지의 개수가 N-1이 될 때까지 과정 3 반복

5. 에지의 개수가 N-1이 되면 완성된 최소 신장 트리의 총 에지 비용 출력

최소 신장 트리 문제

백준 1197

문제 분석하기

• 최소 신장 트리를 구하는 가장 기본적인 문제이다.
• 가중치의 범위는 int형의 범위로, int를 사용해도 된다는 것을 말하고 있다.

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[] unionFind;

    public static void main(String[] args) throws Exception {
        BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        // 초기화
        int[][] array = new int[E][3];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            array[i][0] = a;
            array[i][1] = b;
            array[i][2] = c;
        }

        unionFind = new int[V+1];
        for (int i = 1; i < unionFind.length; i++) {
            unionFind[i] = i;
        }

        // 오름차순 정렬
        Arrays.sort(array, (o1, o2) -> {
            return o1[2] - o2[2];
        });

        // 에지 만들기
        int edge = 0;
        int result = 0; // 가중치
        while (edge != V-1) {
            for (int[] in : array) {
                // 대표 노드 찾기
                int rep_a = myFind(in[0]);
                int rep_b = myFind(in[1]);

                if (rep_a != rep_b) {
                    // 대표 노드끼리 연결
                    myUnion(rep_a, rep_b);
                    result += in[2];
                    edge++;
                }
            }
        }

        System.out.println(result);
    }

    private static void myUnion(int a, int b) {
        if (a < b) {
            unionFind[b] = a;
        }
        else {
            unionFind[a] = b;
        }
    }

    private static int myFind(int num) {
        if (num == unionFind[num]) {
            return num;
        }
        return unionFind[num] = myFind(unionFind[num]);
    }
}

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

다익스트라 (Dijkstra)

• 다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
  • 출발 노드와 모든 노드 간의 최단 거리를 탐색한다.
  • 에지는 항상 모두 양수이다.
• 노드 수를 $V$, 에지 수를 $E$라고 했을 때 시간 복잡도는 $O(ElogV)$이다.

핵심 이론

1. 인접 리스트로 그래프 구현하기

   • 인접 행렬도 구현해도 좋지만, 시간 복잡도 측면에서 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다.
   • 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결한다.
   • 인접 행렬로 구현하면 없는 자리도 모두 검색해야 한다.

2. 최단 거리 배열 초기화하기

   • 출발 노드는 0, 이외의 노드는 무한으로 초기화한다.
   • 이때, 무한은 적당히 큰 값을 사용하면 된다. (예를 들어 99,999,999)

3. 최단 거리 배열에서 현재 값이 가장 작은 노드 고르기

4. 최단 거리 배열 업데이트하기

   • 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트 한다.

   • 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트 한다.

   • 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트 한다.

     $$ Min(선택\ 노드의\ 최단\ 거리\ 배열의\ 값+에지\ 가중치, 연결\ 노드의\ 최단\ 거리\ 배열의\ 값) $$

5. 과정 3~4를 반복해 최단 거리 배열 완성하기

   • 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리한다.
   • 모든 노드가 선택될 때까지 반복한다.

벨만-포드 (Bellman-Ford)

• 벨만-포드(bellman-ford-moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
  • 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다.
  • 음수 가중치 에지가 있어도 수행할 수 있다.
  • 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
• 노드 수를 $V$, 에지 수를 $E$라고 했을 때 시간 복잡도는 $O(VE)$이다.
• 실제 알고리즘 코딩 테스트에서는 벨만-포드 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제된다.

핵심 이론

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기

   • 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. (edge 클래스는 일반적으로 노드 변수 2개와 가중치 변수로 구성되어 있다)
   • 최단 경로 리스트는 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.

2. 모든 에지를 확인해 정답 리스트 업데이트하기

   • 최단 거리 리스트에서 업데이트 반복 횟수는 $노드 개수-1$이다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 $N-1$이기 때문이다.

   • 모든 에지 $E=(s,e,w)$에서 다음 조건을 만족하면 업데이트를 실행한다.

     • 음수 사이클이 없을 때 최대 에지 개수가 나오려면 사항 트리 형태에서 양 도착 노드를 선택해야 한다.

       # 정답 리스트: D
       # 에지의 출발 노드: s, 종료 노드: e, 에지의 가중치: w
       IF (D[s] != 무한대이며 D[e] > D[s] + w일 때)
         D[e] = D[s] + w로 리스트의 값을 업데이트

   • 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리이다.

   • 음수 사이클이 없을 때 $N-1$번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려주는 정답 리스트가 완성된다.

3. 음수 사이클 유무 확인하기

   • 음수 사이클 유무를 확인하기 위해 모든 에지를 한 번식 다시 사용해 업데이트되는 노드가 발생하는지 확인한다.
   • 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이고, 음수 사이클이 존재하면 이 사이클을 무한하게 돌 수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.
   • 즉, 2단계에서 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다.

플로이드-워셜 (Floyd-Warshall)

• 플로이드-워셜 (Floyd-Warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
  • 모든 노드 간에 최단 경로를 탐색한다.
  • 음수 가중치 에러가 있어도 수행할 수 있다.
  • 동적 계획법의 원리를 이용해 알고리즘에 접근한다.
• 노드 수를 $V$라고 했을 때 시간 복잡도는 $O(V^3)$이다.
  • 따라서 플로이드-워셜을 사용하는 문제라면 노드 개수(N)의 범위가 다른 그래프에 비해 작게 나온다. (200~300 등)

핵심 이론

• 플로이드-워셜 알고리즘의 핵심 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

  • 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다.

• 이 원리로 다음과 같은 점화식을 도출할 수 있다.

  $$ D[S][E]=Math.min(D[S][E], D[S][K]+D[K][E]) $$

구현 방법

1. 리스트를 선언하고 초기화하기

   • D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다.
   • S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화한다.
   • 여기서 S==E는 자기 자신에게 가는데 걸리는 최단 경로값을 의미한다.

2. 최단 거리 리스트에 그래프 데이터 저장하기

   • 출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E]=W로 에지의 정보를 리스트에 입력한다.
   • 이로써 플로이드-위셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.

3. 점화식으로 리스트 업데이트하기

   • 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트한다.

     # 노드 개수는 N
     for 경유지 K에 관해 (1~N)
       for 출발 노드 S에 관해 (1~N)
           for 도착 노드 E에 관해 (1~N)
               D[S][E] = Math.min(D[S][E], D[S][K]+D[K][E])

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

위상 정렬 (Topological sort)

• 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
  • 노드 간의 순서를 결정한다.
  • 사이클이 없어야 한다.
• 노드 수를 $V$, 에지 수를 $E$라고 했을 때 시간 복잡도는 $O(V+E)$이다.
• 위상 정렬에서는 다음 사항들을 주의해야 한다.
  • 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.
  • 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로, 위상 정렬을 적용할 수 없다.

핵심 이론

진입 차수

진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.

예를 들어, 다음과 같은 관계를 갖는 그래프가 있다고 하자.

• 1 → 2, 3
• 2 → 4, 5
• 3 → 4
• 4 → 5

이때 진입 차수 배열 D는 다음과 같다.

• D[1] = 0
• D[2] = 1
  • 1이 가리키고 있다.
• D[3] = 1
  • 1이 가리키고 있다.
• D[4] = 2
  • 2와 3이 가리키고 있다.
• D[5] = 2
  • 2와 4가 가리키고 있다.

위상 정렬 단계

1. ArrayList로 사이클이 없는 그래프를 표현한다.

   • 진입 차수 배열 D를 업데이트한다.

2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

   • 예를 들어, 선택된 1의 인접 리스트 연결값으로 2와 3이 있다면 1) 정렬 배열에 1을 추가 2) D[2] = D[2]-1; D[3] = D[3]-1;

     주의! 여기서 진입 차수가 0인 것들 중 어떤 것을 먼저 선택하느냐에 따라 정렬이 달라진다. 즉, 위상 정렬은 늘 같은 정렬 결과를 보장하지 않는다.

3. 모든 노드가 정렬될 때까지 2번 과정을 반복한다.

   • 정렬이 종료되면 진입 차수 배열은 모두 0이 된다.

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

유니온 파인드 (Union-Find)

• 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

핵심 이론

• 유니온 파인드는 union, find 연산을 완벽히 이해하는 것이 핵심이다.

union 연산

• 각 노드가 속한 집합을 1개로 합치는 연산이다.
• 노드 a, b가 $a \in A$, $b \in B$일 때 union(a, b)는 $A \cup B$이다.

find 연산

• 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다.
• 노드 a가 $a \in A$일 때 find(a, b)는 A 집합의 대표 노드를 반환한다.

💡 단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간 복잡도를 향상시킨다.

구현 방법

1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다.

   • 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다.

   • 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화한다.

     int[] array = new int[5];
     array[1] = 1;
     array[2] = 2;
     array[3] = 3;
     array[4] = 4;

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다.

   • 대표 노드는 작은 값으로 설정한다고 하자.

   • 이때, 대표 노드끼리 연결해야 한다.

   • 만약 1과 4를 연결하려면 array[4] 의 대표 노드값을 1로 변경한다.

     // union(1, 4)
     array[4] = 1;
     
     // union(5, 6)
     array[6] = 5;
     
     // union(4, 6) -> 대표 노드인 1과 5를 연결한다.
     array[5] = 1;

find 연산의 작동 원리

1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1~2번 과정을 반복한다.
   • 반복되므로 이 부분은 재귀 함수로 구현한다.
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드로 변경한다.

• 한 번의 find 연산을 이용해 모든 노드가 루트 노드에 직접 연결되는 형태로 변경된다.
• 이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다.

💡 경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

그래프 기본

그래프란?

• 노드와 에지로 구성된 집합이다.
  • 노드: 데이터를 표현하는 단위
  • 에지: 노드를 연결하는 선
• Tree도 그래프의 일종이다.
• 그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩 테스트에 자주 등장한다.

그래프 관련 알고리즘

• 유니온 파인드 (Union-Find)
  • 그래프 외에서도 사용된다.
  • 그래프의 사이클이 생성되는지 판별하는 알고리즘이다.
• 위상 정렬 (Topological sort)
  • 사이클이 없는 방향이 있는 그래프일 때, 그래프의 각 노드들을 선형으로 정리하는 알고리즘이다.
  • 정렬 결과가 꼭 1개인 것은 아니다.
• 다익스트라 (Dijkstra)
  • 최단 거리 알고리즘
  • 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘이다.
  • 단, 음수 간선이 있으면 안 된다.
• 벨만-포드 (Bellman-Ford)
  • 최단 거리 알고리즘
  • 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘이다.
  • 음수 간선이 있어도 된다.
  • 음수 사이클이 있는지를 판별하는 문제에서 자주 쓰인다.
• 플로이드-워셜 (Floyd-Warshall)
  • 최단 거리 알고리즘
  • 주어진 노드들 중 임의의 노드와 다른 노드 사이에서의 최단거리를 구하는 알고리즘이다.
  • 시작점이 없다.
  • 다익스트라와 벨만-포드 알고리즘에 비해 시간 복잡도가 좋지 않다.
• 최소 신장 트리 (MST)
  • 최소의 가중치 합으로 모든 노드를 연결할 수 있도록 해주는 알고리즘이다.
  • 최소 신장 트리에서는 사이클이 나올 수가 없으므로, 유니온 파인드 알고리즘이 필요하다.

그래프의 표현

그래프를 구현하는 방법은 총 3가지가 있다.

에지 리스트

• 에지 리스트(edge list)는 에지를 중심으로 그래프를 표현한다.
• 에지 리스트는 다음과 같이 사용한다.
  • 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현
  • 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현
• 노드는 여러 자료형을 사용할 수 있다.
• 에지 리스트는 구현하기 쉽다.
• 벨만 포드나 크루스칼(MST) 알고리즘에 사용한다.
  • 이 둘은 에지 기준의 알고리즘이다.

가중치 없는 그래프 표현하기

• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.

• 다음과 같이 그래프의 노드들이 방향을 가지고 있다고 하자.

  • 1 → 2 → 5

  • 1 → 3 → 4 → 5

  • 2→ 4

    Integer[][] A = new Integer[2][N];
    
    // A[0][0] = 1, A[1][0] = 2
    // A[0][1] = 1, A[1][1] = 3
    // A[0][2] = 3, A[1][2] = 4
    // A[0][3] = 2, A[1][3] = 4
    // A[0][4] = 2, A[1][4] = 5
    // A[0][5] = 4, A[1][5] = 5

  • 만약 방향이 없는 그래프라면 $[1, 2]$와 $[2, 1]$은 같은 표현이다.

가중치 있는 그래프 표현하기

• 가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.

• 다음과 같이 그래프의 노드들이 방향을 가지고 있다고 하자.

  • 1 → 2 (가중치 8)

  • 2 → 5 (가중치 15)

  • 1 → 3 (가중치 3)

  • 3 → 4 (가중치 13)

  • 4 → 5 (가중치 2)

  • 2 → 4 (가중치 4)

    Integer[][] A = new Integer[3][N];
    
    // A[0][0] = 1, A[1][0] = 2, A[2][0] = 8
    // A[0][1] = 1, A[1][1] = 3, A[2][1] = 3
    // A[0][2] = 3, A[1][2] = 4, A[2][2] = 13
    // A[0][3] = 2, A[1][3] = 4, A[2][3] = 4
    // A[0][4] = 2, A[1][4] = 5, A[2][4] = 15
    // A[0][5] = 4, A[1][5] = 5, A[2][5] = 2

  • 만약 방향이 없는 그래프라면 $[1, 2]$와 $[2, 1]$은 같은 표현이다.

주의

• 에지 리스트로 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다.
  • 만약 노드 2와 관련 있는 노드를 찾고 싶어서 배열을 탐색한다면, 배열을 정렬하거나 전체를 뒤지며 노드가 2인 것을 찾아야 한다.
• 따라서 노드 중심 알고리즘에는 잘 사용하지 않는다.

인접 행렬

• 인접 행렬(adjacency matrix)은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.

• 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.

    Integer[][] A = new Integer[N][N];

가중치가 없는 그래프 표현하기

• 1에서 2를 향하는 에지를 1행 2열에 1을 저장하는 방식으로 표현한다.
• 여기서 1을 저장하는 것은 유무(있고 없음)의 구분값이다.

가중치가 있는 그래프 표현하기

• 1에서 2를 향하는 에지에 8이라는 가중치가 있을 때, 1행 2열에 8을 저장하는 방식으로 표현한다.
• 즉, 가중치를 저장한다.
• 인접 행렬을 이용한 그래프 구현은 쉽고, 두 노드를 연결하는 에지의 여부와 가중치값을 배열에 직접 접근하면 바로 확인할 수 있다는 장점이 있다.

주의

• 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
• 노드 개수가 많은 경우 2차원 배열 선언 자체를 할 수 없는 결함이 있다.
  • 예를 들어 노드가 3만 개가 넘으면 Java heap space 에러가 발생한다.
• 따라서 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단해야 한다.

인접 리스트

• 인접 리스트(adjacency list)는 ArrayList로 그래프를 표현한다.
• 노드 개수만큼 ArrayList를 선언하며, 자료형은 경우에 맞게 사용한다.
• 그래프를 구현하는 다른 방법에 비해 구현이 복잡한 편이지만, 다음과 같은 이유로 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.
  • 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나다.
  • 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러가 발생하지 않는다.

가중치 없는 그래프 표현하기

• N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.

• 다음과 같이 ArrayList의 배열로 선언한다.

  • 배열의 하나 하나가 모두 노드이다.

  • 노드 1에서 2와 3으로 가는 그래프가 있다면 다음과 같다.

    ArrayList<Integer>[] A = new ArrayList[5];
    A[1].add(2);
    A[1].add(3);

가중치 있는 그래프 표현하기

• 가중치가 있는 경우, 자료형을 클래스로 사용한다.

• 다음은 (도착 노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용한다.

    class Node {
        int E;
        int V;
  
        Node(int E, V) {
            this.E = E;
            this.V = V;
        }
    }
  
    ArrayList<Node> A = new ArrayList[N];
    A[3].add(new Node(4, 3));

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

DNS

• 도메인 네임으로 IPv4 주소를 검색해서 그 결과(IP 주소)를 알려주는 서비스를 제공한다.
  • 도메인 네임: www.naver.com 과 같은 이름
• 분산 구조형 데이터베이스
  • 데이터베이스 시스템(DNS 네임서버)의 분산 구성
  • 데이터 영역별 구분(Domain Zone) 및 분산관리
  • 도메인의 네임서버 및 도메인 데이터는 해당 관리주체에 의해 독립적으로 관리됨
• 트리(tree) 구조의 도메인 네임(Domain Name) 체계
  • Domain: 영역, 영토를 의미
  • 도메인 네임의 자율적 생성
  • 생성된 도메인 네임은 언제나 유일(Unique)하도록 네임 체계 구성

도메인 네임

www.naver.com

• 뒤로 갈수록 큰 개념이 된다.
  • www은 naver에 속한 것이고, naver는 com에 속한 것이다.
• www 는 호스트 네임이다.
• naver.com 은 도메인 네임이다.

분산구조형

인터넷을 사용하는데 ISP(Internet Service Provider)는 KT를 사용하고 있다고 가정하자.

1. 주소창에 www.naver.com 를 입력한다.
2. 컴퓨터의 IP 설정에 포함된 DNS 서버 주소로 질의를 보낸다.
   • 운영체제 내부에서 “www.naver.com 로 접속하려고 하는데 IP 주소를 알려줘”라고 질의를 보낸다.
   • 컴퓨터의 IP 설정에는 반드시 DNS 서버 주소가 포함되어 있다.
3. DNS 서버가 IP 주소와 유효기간을 반환한다.
4. IP 주소를 보고 접속한다.

DNS 주소

• 보통 ISP에서 정해준 것을 사용한다.
• DNS가 응답이 느려지면 인터넷 전체가 느려지는 일이 벌어진다.
• 사용하는 ISP의 DNS에 속한 게 아니라 다른 ISP에 세팅을 했다면, 접속할 때 다른 ISP에 가서 응답을 받아오기 때문에 내가 사용하는 주소에서 응답받는 것이 더 빠르다.
  • 예를 들어, 구글 DNS(8.8.8.8)에 세팅을 했는데 네이버에 접속하려고 한다면…

DNS Cache

• 질의해서 IP 주소를 반환받으면, PC에서 IP 주소를 메모리에 저장해서 가지고 있다.
  • ipconfig/displaydns 로 확인 가능
• 다음에 똑같은 질의를 하면 DNS 캐시에서 읽어서 접속한다.

유효기간

• DNS는 IP 주소와 함께 유효기간을 반환한다.

DNS가 거짓말을 한다면?

• 큰 일이 날 것이다.
  • 1.25 인터넷 대란
• 따라서 DNS는 강력한 보안이 적용되어 있다.

정리

• PC에는 다음 것들이 있다.
  • DNS Cache
  • hosts 파일 (윈도우)
• DNS Cache는 유효기간이 만료될 때까지 메모리에 상주한다.
  • 여기 들어있는 정보가 있다면 DNS에게 묻지 않는다.
• hosts 파일은 IP 주소와 URL을 써놓은 것이다.
  • 여기 써져 있다면 DNS에게 묻지 않고, 여기 써진 대로 움직인다.
• 만약 DNS와 공유기 주소가 같다면, 공유기가 DNS 포워딩 기능을 해서 공유기가 DNS 역할을 약간 대행해주는 식으로 작동하기도 한다.
  • 공유기가 실제 DNS에게 질의?

계층 구조

만약 아무도 www.naver.com의 주소를 물은 적이 없다면 어떻게 될까?

• DNS가 어떻게 작동하도록 설정했느냐에 따르기는 하지만 보편적으로
  1. Cache DNS에게 질의??
  2. Cache DNS가 RootDNS에게 com 을 담당하는 DNS를 알려달라고 요청한다.
  3. RootDNS는 DNS IP 목록을 반환한다.
  4. 목록 중 하나에게 naver 주소를 질의하고, 네이버 네임 서버를 응답받는다.
  5. 네이버 서버에게 이름이 www 인 컴퓨터가 있는지 물어보고, 네이버 서버는 IP 주소를 알려준다.
  6. Cache DNS는 IP와 도메인을 쌍으로 저장한다.
     • 누군가 www.naver.com 주소로 접속하면 캐시된 걸로 접속한다.

트리 구조

• 정점에 있는 것이 RootDNS이다.
  • 전세계에 13대 정도가 있다.
  • 13대는 서로 동기화를 하고 있다.
  • IANA.org에 가면 RootDNS를 알아낼 수 있다.
  • DNS를 위한 DNS이다.
• com 만 담당하는 DNS들이 여러 개 존재한다.

참고 사이트

우리가 주소창에 naver.com을 쳤을 때 일어나는 일

웹 기술 창시자와 대한민국 인터넷

웹 기술의 창시자

티모씨 버너스리

• CERN(입자물리연구소)에서 컨설턴트로 근무
  • CERN은 썬 혹은 쎄른이라고 읽는다.
• 정보검색 시스템 구축
• 이를 바탕으로 현재의 웹 기술을 창안
• HTML, HTTP의 창시자

HTML

• 연구소에서 논문을 읽어야 했다.
  • 논문에는 참고문원(Reference)가 있다.
  • 참고문원을 보고 다른 논문을 읽고, 그 논문의 참고문원을 보고 다시 다른 논문으로 가는 등의 작업을 한다.
• 문서 하나를 보고 다음 문서를 볼 때 쉽게 가기 위해, ‘문서 간 연결’을 고민했다.
• 이렇게 탄생한 것이 HTML이다.
  • Link를 클릭해서 다른 문서로 넘어간다.
• HTML의 정체성은 ‘문서’이다.

HTTP

• HTTP는 HTML 문서를 실어 나르기 위해 만들어졌다.
  • 현재는 복잡해졌지만.
  • 웹 기술의 본질은 HTML 문서를 잘 전달하는 것
• 인프라 스트럭처로 TCP/IP 즉 인터넷 기술을 활용했다.
• “HTTP://” 에서 “//”는 사실은 쓸모없는 것이며 큰 실수였다고 인터뷰했다.

대한민국 인터넷

• 대한민국 인터넷의 아버지, 전길남 박사님
• 아시아에서 최초이자 세계에서 두 번째로 인터넷을 구축했다.

URL과 URI

• Uniform Resource Locator (위치)
• Uniform Resource Identifier (식별자)
  • URL을 포함한다.

Resource

웹 기술에 한정지어서 생각해보자.

• Resource의 본질은 “파일”이다.
• 파일이 저장된 위치를 Resource Locator라고 본다.
  • 웹에서 이 파일은 HTML, CSS, JS, Image 등이다.

URI 구조

• URI = scheme “:” [”//” authority] path [”?” query] [”#” fragment]

URI와 URL

• Protocol://Address:Port number/Path(or filename)?Parameter=value
• Path는 디렉토리의 경로 개념을 생각하자.
  • 특정 기준점(C://Program Files)을 기준으로 잡고, 그 하위의 어떤 파일에 접속한다.
• 파라미터가 하나 더 있으면 &Parameter=value로 덧붙인다.
• web은 보통 TCP 80번을 사용한다.
  • 포트 번호를 안 쓰면 TCP 80이다.

굵고 짧게 살펴보는 HTTP

HTTP

• HTTP는 HTML 문서를 전송 받기 위해 만들어진 응용 프로그램 계층 통신 프로토콜이다.
  • L7에 속한 프로토콜
  • L7(L5 이상)은 소켓 통신이고, 스트림 데이터이다. 즉, 시작은 확실하지만 끝이 어딘지는 해석해봐야 한다. → 해석하는 규정이 HTTP에 있다.
• 1996년에 1.0 스펙이 발표됐으며 1999년 6월에 1.1이 발표됐다.
• 기본적으로 클라이언트의 요청에 대응하는 응답형식으로 작동한다.
• 헤더는 다음과 같이 분류된다.
  • 일반 헤더
  • 요청 헤더
  • 응답 헤더
  • 엔티티 헤더
• 문자열로 되어 있어서 내용을 이해하기가 생각보다 쉽다.
  • 헤더도 문자열로 되어 있다.
• 요청에 사용되는 메서드는 주로 GET, POST이다.

HTTP 응답 코드

• 200 OK
  • 요청이 정상적으로 처리됨
• 201 Create
  • 요청에 대한 새로운 자원을 생성하는데 성공함
• 301 Moved permanently
• 302 Found
• 400 Bad request
  • HTTP 규약에 맞지 않는 요청
• 403 Forbidden
  • 권한이 없거나 잘못된 파일 실행 접근 시도
• 404 Not found
• 500 Internal server error
  • 내부 오류때문에 요청을 처리할 수 없음.

HTTP method

• GET
  • 다운로드에 가깝다.
  • 리소스를 달라고 요청
• POST
  • 업로드 성격이 강하다.
  • 리소스를 달라고 요청
• HEAD
  • 데이터 영역을 떼고 뭐만 보내고 하는 것
• TRACE
• PUT
• DELETE
• OPTIONS
• CONNECT

그림 한 장으로 외워서 끝내는 웹 서비스 구조 기본이론

웹 서비스 기본 구조

• HTTP는 TCP 연결 그 다음에 존재한다.
  • → 이건 무슨 말일까?
• HTTP 트래픽은 소켓 수준에서 만들어지는 거고, 스트림(끝을 알기 어려운 데이터)가 나열된다.
  • 따라서 웹에 대한 이야기를 할 때 기본적으로 패킷이나 세그먼트 등의 이야기는 나오지 않는다.

웹 통신

• 웹을 이루고 있는 가장 근간이 되는 두 축의 기술은 HTML과 HTTP이다.
• 웹 서버의 앞에는 보통 라우터 같은 기본적인 장비를 제외하고서 항상 거의 3개 정도가 있다.
• 클라이언트와 웹 서버는 TCP/IP 기반에서 연결하고, 이 연결을 기반으로 HTTP 통신이 이루어진다.

초창기 웹 통신

• 초창기 클라이언트는 ‘문서뷰어’였다.
• HTML 문서 속의 링크가 있어서, 링크를 클릭하면 아래 과정을 거친다.
  1. HTTP request GET으로 요청
  2. HTML 문서 반환
  3. HTML 문서를 화면에 표시한다.

개발 시 설계 원칙

• 아래 영역들의 세계를 구분하라
  • UI 영역
  • Data 영역
  • 제어 체계
• 좋은 설계 원칙은 유지 보수 문제를 따진다.
  • 구분하지 않으면, 자료구조(Data) 변경하면 UI도 고쳐야 하게 된다.

변천사

• HTML 문서를 예쁘게 꾸미고 싶어서 문법을 집어넣으려 하는데, 둘을 섞으면 나쁘므로 분리했다.
  • 화면을 꾸미자고 논문을 뜯어 고치면 안되므로.
  • 이렇게 분리한 화면을 예쁘게 꾸미기 위한 요소가 CSS(스타일 시트)이다.
  • HTML이 Data에 해당
• 넷스케이프 내비게이터(Netscape Navigator)
  • 정적인 문서에 움직임을 넣거나 동적인 제어가 가능한 무언가를 만들려 했다.
  • 이 동적 움직임에는 규칙이 따르기 마련이고, 이러한 규칙을 스크립트 형태로 기술하게 된다.
  • 이렇게 탄생한 것이 Mocha script이다. 모카 스크립트는 이후 Live script → JavaScript 순서로 이름을 바꾸었다.
• HTML 문서가 오면 화면에 렌더링했는데, 렌더링하기 전 구문 분석부터 해야 한다.
  • Text와 Tag를 분리한 후, 태그를 해석해서 그에 맞게 렌더링해야 한다.
• 브라우저를 이루는 구성 요소
  • 구문 분석기 (파서)
  • 렌더링
  • 핵심적인 역할을 하는 엔진
  • JS 엔진
• 즉, CSS도 나오고 JS도 추가되고 그랬다. → 움직임(동적) 추가됨.

POST의 등장

• GET은 단방향이어서 적극적인 상호작용을 할 수 없었다.
• POST가 포함되면서 양방향 상호작용을 할 수 있게 됐다.
• 양방향 상호작용이 되면서 ‘상태 전이’가 필요해졌다.
  • HTTP는 Stateless(무상태)이므로 저장을 안했다.
  • 상호작용 과정에서 전이 과정을 어딘가에 기억(저장)해야 했다.
• 양방향이므로 서버와 클라이언트 모두 ‘기억’하는 것을 구현했다.
  • 클라이언트에서는 쿠키의 형태로 구현되었다.
  • 서버는 기억해야 할 것이 많아서(사용자 별로 기억해야 함) 아카이브 형태로 Database로 만들게 된다.

💡 쿠키 key와 value 형태로 되어 있다.

WAS

• 예를 들어 로그인을 한다면, POST에서는 id="tester"&password="1234" 를 보내야 한다.
  • 이렇게 전송하는 것들은 서버 관점에서 “원격지 사용자 입력”이 된다.
• 원격지 사용자 입력은 서버 관점에서는 신뢰해서는 안 된다.
  • 반드시 검증해야 한다.
  • 즉, 원격지 사용자 입력은 검증 대상이다.
• 데이터베이스와 연동하는 것은 웹 서버가 하지 않고, 중간에 중개해주는 역할을 담당하는 서버가 하나 더 들어가게 된다.
  • 보통 웹 서비스는 “웹 서버 - 중개 서버 - 데이터베이스”로 연결이 되어 있다.
  • 웹 서버는 기본적으로 송수신 담당이다. → 리소스를 보내고 받는다.
  • 데이터베이스의 역할은 자료 담당이다. → 기억
  • 중개 서버는 연산을 담당하는 요소로 작용한다. → 동적인 HTML이 생성된다.
• 중개 서버는 ODBC, JDBC 같은 인터페이스로 DB에 연결해서 조회한다.
  • 조회 결과가 있으면(Found) 정보를 화면에 보여주고, 조회 결과가 없으면(Not Found) 정보를 보여주지 않는 등의 결과가 나온다.
  • 이렇게 중간에서 처리를 담당하는 서버를 WAS(Web Application Server)라고 한다.
• WAS에서…
  • 눈에 보이는 역할(HTML 문서 등)을 하는 View
  • 자료를 결합해서 최종적인 View를 생성하는 Model
  • 네트워크 상에서 어떤 리퀘스트에 대한 제어 체계를 포함하는 Controll 이라는 제어 체계
  • 합쳐서 MVC 아키텍처가 된다.

WAS와 RESTful API 그리고 JVM

WAS

APM (Application Performace Management)

• 웹 서비스 시스템이 얼마나 잘 작동하고 있는가를 항상 모니터링 해야 한다.
• 네트워크가 아무리 빨라도 DB가 응답을 안하면 굉장히 느려진다.
  • 응답 시간은 서비스의 어떤 품질을 확인하는데 매우 중대한 역할을 한다.
• WAS와 Databasae 장치를 모니터링해서 DB 응답 시간과 WAS 상태를 모니터링해서 웹 어플리케이션이 잘 작동하는지 관리하는 시스템을 APM라고 한다.
  • 오픈 소스 중 스카우터라는 APM이 있다.
• 모니터링
  1. 응답 시간
  2. JVM

JVM

• Java를 위해서 소프트웨어로 구현된 CPU라고 생각하면 된다.
• 이 CPU가 인식할 수 있는 명령체계는 Java ByteCode이다.

서블릿과 WAS

• 미들웨어
  • Java byte code를 아래에 깔고 어플리케이션을 작동시켜주는 소프트웨어
  • 또 다른 소프트웨어가 잘 작동할 수 있도록 도와주는 소프트웨어
  • 모든 프로그램들이 공통으로 필요한 TCP/IP 통신, DB 입출력, 파일 입출력 등 기본 기능을 가지고 있다.
  • 미들웨어가 이러한 기본 기능을 제공하므로 소프트웨어는 뭐… 필요한 것만 개발하면 된다.
• JSP는 서블릿이라는 형태로 들어간다.
  • JSP를 활용하면 몇 개는 가져다 쓰면 되고… 함수 하나만 짜면 되고… 알아서 번역해서 들어가고….
• 이런 애들(JSP, PHP, ASP)을 감싸 안아주고 연동시켜주는 미들웨어를 서블릿(Suvlet)이라고 한다.
• 전체를 서블릿 컨테이너라고 부른다.
• 이런 미들웨어(서블릿 컨테이너?)를 다른 말로 WAS라고 한다.
  • 대표적으로 톰캣
• 스프링도 컨테이너.

API

• 서버에서 HTML을 만들어서 보내는데, 클라이언트 쪽 사용자 환경이 다양해졌다.
• HTML 문서는 결국 UI와 Data 분리가 안된다는 단점이 있다.
  • 일정 수준의 UI 적 요소를 갖고 있다.
  • 사용자 환경마다 UI를 따로 만들어야 하는 문제 발생
• 따라서 UI와 데이터를 분리하자는 시도가 일어난다.
  • 요청 시, 응답 값이 Data(자료)만 날아오게 변경했다.
  • XML, JSON 형태로 온다.
• JavaScript 기반의 소프트웨어가 실행되어서(클라이언트 사이드에서) 데이터를 받아서 그 자리에서 HTML을 생성한다.
  • JavaScript가 사용자 환경에 따라 UI를 생성해준다.
  • JavaScript Framework로 React, Vue 등이 있다.

RESTful API

• 리퀘스트는 어떤 처리에 대한 리퀘스트가 되었다.
  • 대표적으로 CRUD
• CRUD를 각각 함수 형태(객체든 뭐든 기능 요소 단위)로 만들고, 사용자가 이 함수를 호출하게 한다.
  • 함수를 사용자가 호출하는 것이 리퀘스트의 또 다른 형태가 된다.
  • 이 함수 자체를 URI로 만든다. → URI로 기술
  • 이 함수를 다른 말로 API라고 부른다.
• 웹에서 이런 걸 구현한 함수를 RESTful API라고 부른다.

보안

보안 시스템

백엔드 개발하면 보안도 신경 써야 한다.

웹 서버 앞단에는 항상 순서대로 아래 것들이 들어간다. (앞에서 미리 언급했던 라우터 같은 장비 외에 들어가는 것들)

• IPS 보안 장치
  • 1차 방어체계
  • Intrusion Prevention System
  • IPS는 기본적으로 패킷단위 데이터를 처리하면서 공격을 방어합니다. DPI(Deep Packet Inspection)를 실시합니다만 응용 프로그램 수준 스트림 데이터를 정밀하게 관찰하기에는 부족함이 있습니다. 이 때문에 웹 서비스를 보호하기 위해서는 WAF(Web Application Firewall, 웹 방화벽) 시스템을 운영하는 것이 일반적입니다.
• SSL 처리를 담당하는 가속기
  • 이게 중간에 있으면 HTTPS 통신이 된다.
  • 이걸 지나면 HTTP 평문으로 바뀐다.
• 웹 서버를 보호하는 웹 어플리케이션 파이어월
  • 2차 방어체계
  • 가끔 웹 서버와 WAS 사이에 들어가 있을 수도 있다.

SQL Injection

• 원격지 사용자 입력은 신뢰하지 말아야 한다.
• 사용자 입력 속에 SQL 문에 있는지 조사한다.
  • 있으면 SQL Injection 공격이 되는지 검증한다.

추가로

• 자바스크립트는 클라이언트에서 실행이 이루어진다.
  • 따라서 조작이 가능하다.
• 검증은 서버에서 해야 한다.

Reference

참고 강의

외워서 끝내는 네트워크 핵심이론 - 기초 강의 - 인프런

참고 사이트

Apache HTTP Server? Apache Tomcat? 서버 바로 알기

Java 백엔드 개발자는 이러한 웹 애플리케이션을 개발할 때 대부분 스프링 MVC를 사용한다.

백엔드 웹 기술을 학습하기 어려운 이유

Java 백엔드 웹 기술은 매우 방대하고 공부할 분량도 무척 많다. 웹 기술을 학습하기 어려운 이유는 대략 3가지 때문이다.

1. HTTP
   • 모든 웹 기술은 HTTP를 기반으로 하고 있기 때문에, HTTP 기반 지식이 있어야 한다.
2. 오래된 Java 백엔드 웹 개발
   • 오랜 시간 동안 불편한 점들을 개선하고 발전하면서 너무 많은 것들이 자동화 및 추상화되었다.
   • 따라서 과거의 어떤 문제 때문에 지금 이런 방식으로 개선되고 사용되는지, 과거의 문맥을 제대로 이해하고 사용하기가 어렵다.
   • ‘왜?’가 없이 단순히 사용법 위주로만 사용을 하게 된다.
3. 많은 기능을 제공하는 스프링 MVC
   • 스프링 MVC는 실무 백엔드 개발에 필요한 모든 기능을 거의 다 제공한다.
   • 즉, 그만큼 방대하고 학습할 내용도 많다.

하지만 Spring MVC Framework의 기본 구조는 굉장히 탄탄하게 설계되어 있어서, 지금까지 수많은 기능이 추가되어도 그 기본 구조는 변하지 않았다.

따라서 스프링 MVC의 기본 구조를 확실하게 이해하는 것이 중요하다.

웹 서버와 웹 애플리케이션 서버

웹은 HTTP 프로토콜을 기반으로 통신을 한다. 다음과 같이 거의 모든 형태의 데이터 전송이 가능하다.

• HTML, TEXT
• 이미지, 음성, 영상, 파일
• JSON, XML (API의 경우)

웹 서버란

• 웹 서버란 HTTP를 기반으로 동작하는 서버이다.
• 정적 리소스와 기타 부가 기능들을 제공한다.
  • 정적 리소스란, 특정 디렉토리에 있는 파일들을 그대로 전달해주는 것을 말한다.
  • 정적 HTML, CSS, JS, 이미지, 영상 등
• 대표적으로 NGINX, APACHE 등이 있다.

웹 애플리케이션 서버

• Web Application Server는 보통 WAS라고 부른다.
• 웹 서버와 마찬가지로 HTTP를 기반으로 동작하며, 웹 서버의 기능들을 대부분 포함하고 있다.
• 프로그램 코드를 실행해서 애플리케이션 로직을 수행할 수 있다.
  • 사용자에 따라서 사용자의 이름을 보여주거나 다른 화면을 보여줄 수 있다.
  • 즉, 동적인 HTML을 생성하거나 HTTP API(REST API)를 제공한다.
  • Servlet, JSP, Spring MVC 등이 WAS에서 동작한다.
• 대표적으로 Tomcat, Jetty, Undertow 등이 있다.

웹 서버 VS 웹 애플리케이션 서버

• 단순하게는 웹 서버는 정적 리소스를 제공하는 것, WAS는 애플리케이션 로직까지 실행할 수 있는 것으로 이해하면 된다.
• 사실, 둘의 용어도 경계도 모호하다.
  • 웹 서버도 프로그램을 실행하는 기능을 포함하기도 한다.
  • 웹 애플리케이션 서버도 웹 서버의 기능을 제공한다.
• 자바는 서블릿 컨테이너 기능을 제공하면 WAS라고 한다.
  • 하지만 서블릿 없이 자바 코드를 실행하는 서버 프레임워크도 있으므로 이 구분법도 애매하다.
• WAS는 애플리케이션 코드를 실행하는데 더 특화되어 있다고 보는 것이 좋다.

웹 시스템 구성

WAS만 사용할 경우

• WAS와 DB만을 사용하여 최소한의 시스템 구성이 가능하다.
• WAS는 정적 리소스도 제공할 수 있고, 애플리케이션 로직도 제공이 가능하기 때문이다.

단점

• WAS가 너무 많은 역할을 담당하고 있다.
  • 서버 과부하 우려
• 가장 비싼 애플리케이션 로직이 정적 리소스 때문에 수행이 어려울 수 있다.
  • 정적 리소스를 제공하는 것은 있는 파일을 보내주면 되지만, 애플리케이션 로직은 비즈니스 로직이 들어가기 때문에 훨씬 비싸다.
• WAS에 장애가 발생하면 웹 접속 자체가 안된다.
  • 접속 오류 화면조차도 노출이 불가능하다.

일반적인 구성

• 웹 서버와 WAS, DB를 모두 둔다.
• 웹 서버가 정적 리소스를 처리하고, 애플리케이션 로직과 같은 동적인 처리는 WAS에 요청을 위임한다.

장점

• WAS는 중요한 애플리케이션 로직 처리를 전담할 수 있다.
• 효율적으로 리소스를 관리할 수 있다.
  • 정적 리소스가 많이 사용되면 웹 서버를 증설한다.
  • 애플리케이션 리소스가 많이 사용되면 WAS를 증설한다.

참고

• CDN이라는 정적 리소스를 캐시할 수 있는 중간 서버를 놓기도 한다.
• API로 데이터만 제공하는 API 서버일 경우, 굳이 웹 서버를 두지 않아도 괜찮다.
  • WAS 서버만 구축

서블릿

회원가입을 하도록 HTTP 요청을 한다고 가정하자. 그렇다면 웹 애플리케이션 서버에서는 아래 항목을 직접 구현해야 한다.

1. 서버 TCP/IP 연결 대기
2. 소켓 연결
3. HTTP 요청 메시지를 파싱해서 읽기
   • HTTP 메소드 방식과 URL 확인
   • Content-Type 확인
   • 데이터를 사용할 수 있도록 HTTP 메시지 바디의 내용을 파싱
4. 저장 프로세스 실행
5. 비즈니스 로직 실행
   • 데이터를 가지고 데이터베이스에 저장 요청
6. HTTP 응답 메시지 생성 시작
   • HTTP 시작 라인 생성
   • Header 생성
   • 메시지 바디에 HTML 생성해서 입력
7. TCP/IP에 응답 전달
8. 소켓 종료

이 과정에서 실질적으로 비즈니스 로직은 5번 과정 뿐이다. 그런데 그러기 위해서 비즈니스 로직 실행 전후 단계가 너무 많다.

매번 이렇게 개발하고 있다면 비효율적이므로, 등장한 것이 Servlet이다.

Servlet

• 비즈니스 로직(위의 5번 과정)을 제외한 모든 과정을 지원해준다.
  • 서블릿을 지원하는 WAS들이 이 기능들을 해준다.

특징

클라이언트에서 서버로 요청이 왔을 때, 서블릿 코드에 있는 service 메소드가 실행된다.

@WebServlet(name = "helloServlet", urlPatterns = "/hello")
public class HelloServlet extends HttpServlet {
    @Override
    protected void service(HttpServletRequest reqeust, HttpServletResponse response) {
        // 애플리케이션 로직
    }
}

• urlPatterns 의 URL이 호출되면 서블릿 코드가 실행된다.
• HTTP 요청 정보를 편리하게 사용할 수 있는 HttpServletRequest 객체
• HTTP 응답 정보를 편리하게 제공할 수 있는 HttpServletResponse 객체
• 이처럼 개발자는 서블릿을 통해 HTTP 스펙을 매우 편리하게 사용할 수 있다.

동작 과정

1. 웹 브라우저에서 localhost:8080/hello 로 요청을 한다.
2. WAS 서버에서는 HTTP 요청 메시지를 기반으로 HttpServletRequest 객체와 HttpServletResponse 객체를 생성한다.
3. 서블릿 컨테이너는 이렇게 생성한 두 객체를 helloServlet에 파라미터로 넘겨 실행한다.
4. 실행이 끝나고 리턴되면, WAS는 HttpServletResponse 객체를 기반으로 HTTP 응답 메시지를 만든다.
5. 웹 브라우저에 응답 메시지를 전달한다.

즉, HTTP 요청 시 다음과 같이 흘러간다.

• WAS는 Request, Response 객체를 새로 만들어서 서블릿 객체를 호출
• 개발자는 Request 객체에서 HTTP 요청 정보를 편리하게 꺼내서 사용
• 개발자는 Response 객체에 HTTP 응답 정보를 편리하게 입력
• WAS는 Response 객체에 담겨있는 내용으로 HTTP 응답 정보를 생성

서블릿 컨테이너

• Tomcat처럼 서블릿을 지원하는 WAS를 서블릿 컨테이너라고 한다.
• 서블릿 컨테이너는 다음과 같은 일을 한다.
  • 서블릿 객체를 생성, 초기화, 호출, 종료
  • 서블릿 객체의 생명주기 관리
• 서블릿 객체는 싱글톤으로 관리한다.
  • 고객의 요청이 올 때마다 계속 객체를 생성하는 것은 비효율적이므로 최초 로딩 시점에 서블릿 객체를 미리 만들어 두고 재활용한다.
  • 따라서 모든 고객 요청은 동일한 서블릿 객체 인스턴스에 접근한다.
  • 서블릿 컨테이너가 종료되면 함께 종료된다.
  • 공유 변수를 사용할 시 주의해야 한다.
• JSP도 서블릿으로 변환되어서 사용한다.
• 동시 요청을 위한 멀티 쓰레드 처리를 지원한다.

동시 요청 - 멀티 쓰레드

1. TCP/IP 커넥션 연결
2. WAS에서 서블릿 객체 호출 → Thread가 한다.

Thread

• Thread는 애플리케이션 코드를 하나하나 순차적으로 실행한다.

• Thread가 없다면 자바 애플리케이션 실행이 불가능하다.

  • 예를 들어, 자바 메인 메서드를 처음 실행하면 main이라는 이름의 Thread가 실행된다.

    public static void main(String[] args) {
      // ...
    }

• Thread는 한 번에 하나의 코드 라인만 수행한다.

• 동시 처리가 필요하면 Thread를 추가로 생성해주어야 한다.

Thread가 하나일 경우

단일 요청 시

1. HTTP 요청을 한다.
2. WAS는 Thread를 할당한다.
3. Thread는 코드를 실행한다.
4. HTTP 응답을 하고 나면 Thread는 휴식을 한다.

다중 요청 시

1. HTTP 요청이 1건 들어온다. (요청 1)
2. WAS는 Thread를 할당한다.
3. Thread는 요청 1을 처리하는데, 어떠한 이유로 처리가 지연되고 있다.
4. HTTP 요청이 1건 더 들어온다. (요청 2)
5. 요청 2는 Thread를 기다려야 한다.
   • 이렇게 기다리다가 Timeout 등이 발생하면서 요청 1과 2 모두 오류가 날 수 있다.

요청마다 Thread를 생성할 경우

다중 요청에서 다음과 같이 동작한다.

1. HTTP 요청이 1건 들어온다. (요청 1)
2. WAS는 Thread를 할당한다.
3. Thread는 요청 1을 처리하는데, 어떠한 이유로 처리가 지연되고 있다.
4. HTTP 요청이 1건 더 들어온다. (요청 2)
5. 요청 2는 새로운 Thread를 할당한다.

장점

• 동시 요청을 처리할 수 있다.
• 리소스(CPU, 메모리)가 허용할 때까지 처리 가능
• 하나의 Thread가 지연되어도 나머지 Thread는 정상 동작한다.

단점

• Thread의 생성 비용은 매우 비싸다.
  • 고객의 요청이 올 때마다 Thread를 생성하면 응답 속도가 늦어진다.
• Thread는 Context-swtiching 비용이 발생한다.
  • CPU의 코어는 Thread의 여러 개를 번갈아 실행하는데, 이를 컨텍스트 스위칭이라고 한다.
  • Thread가 많아지면 이 컨텍스트 스위칭 비용이 점점 커진다.
• Thread 생성에 제한이 없다.
  • 고객 요청이 너무 많이 오면 CPU와 메모리 임계점을 넘어서 서버가 죽을 수 있다.

Thread Pool

요청마다 Thread를 생성할 때 발생하는 단점을 해결하기 위해 WAS는 내부에 Thread Pool을 사용한다.

• 필요한 Thread를 Thread Pool에 보관하고 관리한다.
• Thread Pool에 생성 가능한 Thread의 최대치를 관리한다.
  • Tomcat의 기본 설정은 최대 200개이다.
• Thread Pool은 다음과 같이 사용한다.
  • Thread가 필요하면 Thread Pool에서 이미 생성되어 있는 Thread를 꺼내서 사용한다.
  • Thread의 사용을 종료하면 Thread Pool에 해당 Thread를 반납한다.
  • 최대 Thread가 모두 사용 중이어서 Thread Pool에 Thread가 없을 경우, 기다리는 요청은 거절하거나 특정 숫자만큼 대기하도록 설정할 수 있다.

동작 과정

1. WAS의 Thread Pool에 미리 Thread를 만들어 둔다.
2. HTTP 요청이 1건 들어온다. (요청 1)
3. WAS는 Thread Pool에서 Thread를 꺼내 요청 1에게 할당한다.
4. Thread는 요청 1을 처리하는데, 어떠한 이유로 처리가 지연되고 있다.
5. HTTP 요청이 1건 더 들어온다. (요청 2)
6. WAS는 Thread Pool에서 Thread를 꺼내 요청 2에게 할당한다.
7. 요청이 끝나면 Thread를 Thread Pool에 반납한다.

장점

• Thread가 미리 생성되어 있으므로 Thread를 생성하고 종료하는 비용(CPU)이 절약되고, 응답 시간이 빠르다.
• 생성 가능한 Thread의 최대치가 있으므로 너무 많은 요청이 들어와도 기존 요청은 안전하게 처리할 수 있다.

성능 튜닝 관점에서

• WAS의 주요 튜닝 포인트는 Max Thread(최대 쓰레드) 수이다.
• 이 값이 너무 낮을 경우
  • 동시 요청이 많으면, 서버 리소스는 여유롭지만 클라이언트는 금방 응답 지연될 수 있다.
• 이 값이 너무 높을 경우
  • 동시 요청이 많으면, CPU와 메모리 리소스 임계점 초과로 서버가 다운될 수 있다.
• 따라서 적정값을 찾는 것이 중요하다.
  • 적정값은 애플리케이션 로직의 복잡도, CPU, 메모리, IO 리소스 상황에 따라 모두 다르다.
  • 따라서 최대한 실제 서비스와 유사하게 성능 테스트를 시도해야 한다.
  • 성능 테스트 툴로는 아파치 ab, 제이미터, nGrinder 등이 있다.

정리

• 멀티 쓰레드에 대한 부분은 WAS가 처리해준다.
  • 개발자가 멀티 쓰레드 관련 코드를 신경쓰지 않아도 된다.
• 멀티 쓰레드 환경이므로 싱글톤 객체(서블릿, 스프링 빈 등)는 주의해서 사용해야 한다.

HTML, HTTP API, CSR, SSR

정적 리소스

• 주로 웹 브라우저들이 요청을 한다.
• 웹 서버는 고정된 HTML 파일, CSS, JS, 이미지, 영상 등을 제공한다.
  • 특정 폴더 아래에 이미 생성되어 있는 리소스 파일 제공

HTML 페이지

• WAS는 동적으로 필요한 HTML 파일을 생성해서 전달한다.
  • 예를 들어서, 주문 내역 페이지를 보려고 한다면 주문 정보로 조회한 데이터로 HTML을 동적으로 생성하여 웹 브라우저에 제공한다.
• 웹 브라우저는 HTML을 받아서 해석 후 사용자에게 보여준다.

HTTP API

• HTML이 아니라 데이터를 전달한다.
  • 주로 JSON 형식을 사용한다.
  • 데이터만 주고 받으므로, UI 화면이 필요하면 클라이언트가 별도로 처리해야 한다.
• 다양한 시스템에서 호출한다.

활용 상황

• 앱 클라이언트 to 서버
  • 앱에 UI 컴포넌트가 있기 때문에 데이터만 전달 받는다.
  • 앱 클라이언트로는 아이폰, 안드로이드, PC 앱 등이 있다.
• 웹 클라이언트 to 서버
  • 웹 브라우저에서 자바스크립트에서 ajax 등의 API를 통해 서버에 있는 API를 호출할 수 있다.
  • 이때 자바스크립트에서 필요한 데이터만 받아서 HTML을 동적으로 만들어서 뿌린다.
  • React, Vue.js와 같은 웹 클라이언트도 있다.
• 서버 to 서버
  • 서버 간의 통신에는 데이터만 주고받으면 되므로 HTTP API를 사용한다.
  • 예를 들어, 주문 서버와 결제 서버가 서로 데이터를 주고 받아야 할 경우가 있다.
  • 기업 안에서 여러 서비스들이 잘게 쪼개져 있을 때(MSA) HTTP API를 통해서 많이 통신한다.

SSR과 CSR

서버 사이드 렌더링 (SSR)

• 서버에서 (동적으로) HTML 최종 결과를 만들어서 웹 브라우저에 전달한다.
  • 웹 브라우저는 HTML을 보여주기만 하면 된다.
• 주로 정적인 화면에 사용한다.
• 관련 기술
  • JSP, Thymeleaf

클라이언트 사이드 렌더링 (CSR)

• 웹 브라우저에서 자바스크립트를 사용해 HTML 결과를 동적으로 생성해서 적용한다.
  1. 웹 브라우저에서 서버로 HTML 요청을 한다.
  2. 서버에서는 빈 HTML과 자바스크립트 링크를 전달한다.
  3. 웹 브라우저에서 자바스크립트를 요청한다.
  4. 서버에서는 클라이언트 로직과 HTML 렌더링 코드가 들어있는 자바스크립트를 전달한다.
  5. 웹 브라우저에서 HTML API로 데이터를 요청한다.
  6. 서버가 JSON 형식으로 데이터를 전달한다.
  7. 웹 브라우저는 자바스크립트로 HTML 결과를 렌더링한다.
• 주로 동적인 화면에 사용하며, 웹 환경을 마치 앱처럼 필요한 부분만 변경할 수 있다.
  • 대표적인 예로는 구글 지도, Gmail, 구글 캘린더 등이 있다.
• 관련 기술
  • React, Vue.js

CSR과 SSR의 경계

• React, Vue.js를 CSR+SSR 동시에 지원하는 웹 프레임워크도 있다.
• SSR을 사용하더라도 자바스크립트를 사용하여 화면 일부를 동적으로 변경할 수 있다.

자바 백엔드 웹 기술 역사

과거의 기술

• 1997년, TCP/IP 연결과 멀티 쓰레드 등의 고민을 해결하기 위해 Servlet 기술이 등장한다.
  • 그러나, Java 코드로 짜야 하기 때문에 HTML을 동적으로 생성하는 것이 굉장히 어렵다는 문제점이 있다.
• 1999년, Servlet의 문제를 해결하기 위해서 JSP가 등장한다.
  • JSP는 최종적으로 서블릿으로 변한다.
  • HTML 생성은 편리하지만, 비즈니스 로직까지 포함하면서 너무 많은 역할을 담당한다는 문제가 생겼다.
• 서블릿과 JSP를 조합하여 MVC 패턴을 사용
  • MVC 패턴은 모델, 뷰, 컨트롤러로 역할을 나누어 개발한다.
  • 핵심은 비즈니스 로직과 화면을 렌더링하는 부분을 분리하여, 관심사를 나누는 것이다.
• 2000년대 초부터 MVC 프레임워크의 등장
  • MVC 패턴 자동화, 복잡한 웹 기술을 편리하게 사용할 수 있는 다양한 기능 지원
  • 스트럿츠, 웹워크, 스프링 MVC

현재의 기술

• 애노테이션 기반의 스프링 MVC의 등장
  • @Controller
  • MVC 프레임워크는 스프링 프레임워크와 사용하려면 통합에 대한 고민이 필요했다.
  • 스프링 MVC는 스프링이 제공하기 때문에 통합에 대한 고민이 필요 없다.
• 스프링 부트의 등장
  • 과거에는 서버에 WAS를 직접 설치하고 WAR 파일을 만들어서 설치한 WAS에 배포했다.
  • 스프링 부트는 빌드 결과(Jar)에 WAS 서버를 포함함으로써 빌드와 배포를 단순화했다.

최신 기술

• 스프링 웹 기술이 다음 두 가지로 분화를 한다.
• Web Servlet - Spring MVC
• Web Reactive - Spring WebFlux

Spring WebFlux

• 완전한 비동기 non-blocking 처리
• 최소 Thread로 최대 성능
  • Thread의 개수를 CPU의 코어(혹은 +1)에 딱 맞춤으로써 Thread를 계속 돌아갈 수 있도록 한다.
  • Thread Context-switching 비용이 거의 들지 않으므로 효율화된다.
• 함수형 스타일로 개발한다.
  • 동시처리 코드 효율화
• 서블릿 기술을 사용하지 않는다.

다만, 다음과 같은 단점이 있다.

• 웹 플럭스는 기술적 난이도가 매우 높다.
• 아직 RDB 지원이 부족하다.
• 일반 MVC의 Thread 모델도 충분히 빠르다.
• 실무에서 아직 많이 사용하지 않는다.

자바 뷰 템플릿 역사

View Template이란

• HTML을 편리하게 사용하는 뷰 기능을 말한다.
• 주로 HTML을 백엔드에서 동적으로 생성하는 것을 말한다.

View Template의 종류

• JSP
  • 속도가 느리다.
  • 기능이 부족하다.
• 프리마커(Freemarker), 벨로시티(Velocity)
  • JSP의 속도 문제를 해결했다.
  • 다양한 기능을 제공한다.
  • HTML 파일을 열었을 때 JSP 코드가 다 보인다.
• 타임리프(Thymeleaf)
  • 내추럴 템플릿: HTML의 모양을 유지하면서 뷰 템플릿 기능을 적용할 수 있다.
  • 스프링 MVC와 강력한 기능 통합
  • 최선의 선택, 단 성능은 프리마커, 벨로시티가 더 빠름

Reference

인프런 강의

스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술 | 김영한 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

소수 구하기

• 소수(Prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.
  • 1과 자기 자신 외의 약수가 존재하지 않는 수
• 코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.

에라토스테네스의 체 원리

• 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체 원리가 있다.

  1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

  2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.

     이때, 처음으로 선택된 숫자는 소수이기 때문에 지우지 않는다.

  3. 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수를 출력한다.

• 에라토스테네스의 체는 이중 for문을 사용하지만, 시간복잡도는 일반적으로 $O(Nlog(logN))$이다.

  • 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.

구현 코드

• N이상 M이하의 범위에서 소수 찾기
  1. 크기가 N+1인 배열을 선언한 후 값은 각각의 인덱스 값으로 채운다.
  2. 1은 소수가 아니므로 삭제한다.
  3. 2부터 N의 제곱근까지 값을 탐색한다. 값이 인덱스 값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경한다.
  4. 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력한다.

💡 N의 제곱근까지만 탐색하는 이유

N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다.

만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다는 뜻이다.

따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

int[] A = new int[N+1];

for (int i = 2; i <= N; i++) {
    A[i] = i;
}

for (int i = 2; i <= Math.sqrt(N); i++) {
    if (A[i] == 0) continue;
    for (int j = i+i; j <= N; j=j+i) {
        A[j] = 0;
    }
}

for (int i = M; i <= N; i++) {
    if (A[i] != 0) {
        System.out.println(A[i]);
    }
}

오일러 피

• 오일러 피 함수(Euler's phi function) P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
  • 서로소는 공약수가 1 이외에 없는 수를 말한다.
  • 예를 들어, 2와 3이 서로소이다.
• 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만, 여기에선 코딩 테스트에 사용하기 위한 구현 부분만 알아보도록 한다.
• 코딩 테스트에 자주 나오지는 않는다.

핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i]=P[i]-P[i]/K 연산을 수행한다. (i는 K의 배수)
3. 배열의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성한다.

구현 코드

private static long Euler(Long N) {

    long res = N;

    // 2부터 N의 제곱근까지 반복
    for(long i=2; i <= Math.sqrt(N); i++){
        if(N%i == 0){
            res = res - res/i;
            while(N%i == 0) {
                N /= i;
            }
        }
    }

    if(N>1) {
        res = res - res/N;
    }

    return res;
}

유클리드 호제법

• 유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다.
• 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만, 유클리드 호제법은 좀 더 간단한 방법을 제시한다.

핵심 이론

• 먼저 MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문에, 이 연산을 이해하고 있어야 한다.
  • MOD 연산: 두 값을 나눈 나머지를 구하는 연산
  • ex) 10 MOD 4 = 2 → 10 % 4 = 2
• MOD 연산으로 다음과 같이 유클리드 호제법을 구현할 수 있다.
  1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
  2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
  3. 2번 과정을 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.
• 최대 공약수를 구하는 연산은 일반적으로 gcd로 정의한다.

구현

• 코딩 테스트에서는 보통 재귀함수로 구현한다.

public static void main(String[] args) throws Exception {

    BufferedReader br = 
        new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int result = gcd(N, M);
    System.out.println(result);
}

private static int gcd(int N, int M) throws IOException {
        int res = N % M;
    if (res == 0) return M;
    return gcd(M, res);
}

최소 공배수 구하기

• 최대 공약수의 함수를 기반으로 최소 공배수(LCM)를 구할 수 있다.
• 최소 공배수 = 두 수의 곱 / 최대 공약수

private static int lcm(int N, int M) throws IOException {
    return (N*M) / gcd(N, M);
}

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

• 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
• 다만, 이렇게 구한 선택지가 항상 최적의 해를 보장하는 것이 아니다.
  • 반례가 나올 수 있다.
  • 그리디 알고리즘으로 풀었을 때 최적의 해가 나올지 아닐지를 고민하며 문제를 풀자.

핵심 이론

그리디 알고리즘은 다음 3단계를 반복하면서 문제를 해결한다.

1. 해 선택
   • 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사
   • 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사
   • 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지를 검사한다.
   • 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.

동전 개수의 최솟값 구하기 (백준 11047)

문제 분석하기

• 전형적인 그리디 알고리즘 문제이다.
  • 반례없이 문제가 해결될 수 있도록 아래조건을 부여했다.
  • $1 ≤ A_i ≤ 1,000,000, A_1 = 1, i ≥ 2인 경우에 A_i는 A_{i-1}의 배수$
• 뒤의 동전 가격 $A_i$가 앞에 나오는 동전 가격 $A_{i-1}$의 배수가 된다는 조건을 부여했다.
• 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.

풀이

1. 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색한다.
2. 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신한다.
3. 과정 1~2를 나머지가 0이 될 때까지 반복한다.

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int K = sc.nextInt();
int A[] = new int[N];

for (int i = 0; i < N; i++) {
    A[i] = sc.nextInt();
}

int count = 0;
for (int i = N-1; i >= 0; i--) {
    if (A[i] <= K) {
        count += (K/A[i]);
        K = K % A[i];
    }

}

System.out.println(count);

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

깊이 우선 탐색 DFS

• 깊이 우선 탐색(DFS; depth-first search)은 그래프 완전 탐색 기법 중 하나이다.
• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
• 깊이 우선 탐색을 표로 정리하면 다음과 같다.
  • V: 노드 개수, E: 에지 개수

핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로, 노드 방문 여부를 체크할 배열이 필요하다.
• 그래프는 인접 리스트로 표현한다.
• DFS의 탐색 방식은 후입선출 특성을 가지므로 스택 혹은 스택 성질을 갖는 재귀 함수로 많이 구현한다.
  • 보통 재귀 함수를 많이 사용한다.

동작

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

   • 필요한 초기 작업은 다음과 같다.
     • 인접 리스트로 그래프 표현하기
     • 방문 배열 초기화하기 (방문 시 T, 미방문 시 F로 초기화)
     • 시작 노드 스택에 삽입하기 (시작점 삽입)

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

   • pop으로 노드를 꺼낸 후, 꺼낸 노드를 탐색 순서에 기입한다.
   • 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다.

3. 스택 자료구조에 값이 없을 때까지 반복하기

   • 스택 자료구조에 값이 없을 때까지 1~2번 과정을 반복한다.
   • 이때, 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.
   • 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴봐야 한다.

구현 코드

private static void mySource() throws IOException {

    ...

    boolean[] visited = new boolean[N];

    // 인접 리스트
    ArrayList<Integer>[] array = new ArrayList[N];
    for (int i = 0; i < array.length; i++) {
        array[i] = new ArrayList<Integer>();
    }

    for (int i = 0; i < M; i++) {
        int node = 노드;
        int next = node와 연결된 노드;

        // 방향 없는 그래프므로 양쪽 노드에 모두 연결
        array[node-1].add(next-1);
        array[next-1].add(node-1);
    }

    // 탐색 돌면서 연결 요소 카운팅
    int count = 0;
    for (int i = 0; i < array.length; i++) {
        // 방문한 적 없으면 탐색 시작
        if(!visited[i]) {
            count++;
            myDFS(visited, array, i);
        }
    }

    System.out.println(count);
}

private static void myDFS(boolean[] visited, ArrayList<Integer>[] array, int i) {
    // 방문한 적 있으면 탐색 종료
    if (visited[i]) {
        return;
    }

    // 방문했으므로 표시
    visited[i] = true;

    // 인접 노드 탐색
    for (int node : array[i]) {
        myDFS(visited, array, node);
    }
}

너비 우선 탐색 BFS

• 너비 우선 탐색(BFS; breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나이다.
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
• 깊이 우선 탐색을 표로 정리하면 다음과 같다.
  • V: 노드 개수, E: 에지 개수

핵심 이론

1. 시작할 노드를 정한 후 사용할 자료구조 초기화

   • 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.
   • 그래프는 인접 리스트로 표현한다.
   • DFS와의 차이점은 탐색을 위해 큐를 사용한다는 점이다.

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

   • 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
   • 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.
   • 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3. 큐 자료구조에 값이 없을 때까지 반복하기

   • 큐에 노드가 없을 때까지 1~2번 과정을 반복한다.

구현 코드

private static void BFS(int i, int j) {
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[] {i, j});
    while (!queue.isEmpty()) {
        int now[] = queue.poll();
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int x = now[0] + dx[k];
            int y = now[1] + dy[k];
            if (x >=0 && y>=0 && x<N && y<M) {
                if (A[x][y] != 0 && !visited[x][y]) {
                    visited[x][y] = true;
                    A[x][y] = A[now[0]][now[1]] + 1;
                    queue.add(new int[] {x, y});
                }
            }
        }
    }
}

이진 탐색 Binary Search

• 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

핵심 이론

• 이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.
  1. 현재 데이터셋의 중앙값(median)을 선택한다.
  2. 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
  3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
  4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

구현 코드

int start = 0;
int end = A.length -1;

while (start <= end) {
    int mid_index = (start + end) / 2;
    int mid_value = A[mid_index];

    if(mid_value > target) {
        end = mid_index-1;
    }
    else if (mid_value < target) {
        start = mid_index+1;
    }
    else {
        find = true;
    }
}

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

정렬 알고리즘

버블 정렬 (Bubble sort)

• 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.
• 간단하게 구현할 수 있지만, 시간 복잡도는 $O(n^2)$으로 다른 정렬 알고리즘보다 속도가 느린 편이다.
• Loop를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.
  • 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다.

오름차순으로 수 정렬하기

❓ N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램

for (int i = 0; i < N-1; i++) {
    for (int j = 0; j < N-1-i; j++) {
        // 인접한 두 데이터를 비교
        if(A[j] > A[j+1]) {
            int temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
}

선택 정렬 (Selection Sort)

• 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다.
• 구현 방법이 복잡하며 시간 복잡도가 $O(n^2)$ 으로 효율적이지 않아서 코딩 테스트에서는 많이 사용하지 않는다.

핵심 이론

• 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap한다.
  • 오름차순이면 최솟값을 찾고, 내림차순이면 최댓값을 찾는다.

• 선택 정렬 과정
  1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
  2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
  3. 가장 앞에 있는 데이터의 위치(index)를 변경해 남은 정렬 부분의 범위를 축소한다.
  4. 남은 정렬 부분이 없을 때까지 1~3번 과정을 반복한다.
• N-1번 반복을 돌면서 최솟값 혹은 최댓값을 구하기 위해 각각 N, N-1, N-2, … 1번의 비교 연산을 수행한다.
  • 약 $\frac{N^2 }{2}$ 인데, 상수는 제거되므로 시간복잡도는 $N^2$이다.

내림차순으로 자릿수 정렬하기

❓ N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램

// i : 정렬된 부분의 범위
for (int i = 0; i < N; i++) {
    // 최댓값의 인덱스
    int Max = i;
    // j : 남은 정렬 부분의 범위
    for (int j = i+1; j < N; j++) {
        // 최댓값의 인덱스 찾기
        if (A[j] > A[Max]) {
            Max = j;
        }
    }
    // 최댓값이면 swap
    if(A[i] < A[Max]) {
        int temp = A[i];
        A[i] = A[Max];
        A[Max] = temp;
    }
}

삽입 정렬 (Insertion Sort)

• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.
• 구현하기는 쉽지만 시간 복잡도는 $O(n^2)$이므로 코딩 테스트에서 많이 사용되지는 않는다.

핵심 이론

• 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 핵심이다.

• 삽입 정렬 수행 방식
  1. 현재 index에 있는 데이터 값을 선택한다.
  2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
  3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.
  4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다. → 정렬된 범위가 증가
  5. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.
• 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.
  • 탐색하는 시간을 $O(N)$에서 $O(logN)$으로 줄일 수 있다.
  • 하지만 shift 연산 때문에 결국 시간은 오래 걸리게 된다.

오름차순으로 수 정렬하기

❓ N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램

// temp : 정렬할 데이터, j : 정렬된 범위
int temp, j;
for (int i = 1; i < N; i++) {

    // 정렬할 데이터 선택
    temp = A[i];

    // 삽입 위치 탐색하면서 Shift 연산 수행
    for (j = i-1; j >= 0; j--) {
        if(A[j] > temp) {
            // 선택 데이터보다 클 경우 한 칸 뒤로 Shift
            A[j+1] = A[j];
        }
        else {
            // 선택 데이터보다 작을 경우 반복문 종료
            break;
        }
    }

    // 적절한 위치에 삽입
    A[j+1] = temp;
}

퀵 정렬 (Quick Sort)

• 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.
• 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미친다.
  • 평균 시간 복잡도는 $O(nlogn)$
  • 최악의 경우, 시간 복잡도는 $O(n^2)$
• 퀵 정렬의 시간 복잡도는 비교적 준수하므로 코딩 테스트에서 종종 으용한다.

핵심 이론

• pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 핵심이다.

출처: https://www.geeksforgeeks.org/quick-sort-in-c/

• 퀵 정렬 과정
  1. 데이터를 분할하는 pivot을 설정한다.
  2. pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리한다. 1). start가 가리키는 데이터 < pivot이 가리키는 데이터 -> start++ 2). end가 가리키는 데이터 > pivot이 가리키는 데이터 -> end-- 3). (start가 가리키는 데이터 > pivot이 가리키는 데이터) && (end가 가리키는 데이터 < pivot이 가리키는 데이터) -> start, end가 가리키는 데이터를 swap하고 start++, end-- 4). start와 end가 만날 때까지 (1~3) 과정을 반복 5). start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입
  3. 분리 집합에서 각각 다시 pivot을 선정한다.
  4. 분리 집합이 1개 이하기 될 때까지 과정 1~3을 반복한다.
• 재귀 함수의 형태로 직접 구현해보는 것을 추천한다.

오름차순으로 자릿수 정렬하기

// 위키백과의 퀵정렬 알고리즘
public void quickSort(int[] arr, int left, int right) {
    // base condition
    if (left >= right) {
        return;
    }
    int pivot = arr[right];

    int sortedIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap(arr, i, sortedIndex);
            sortedIndex++;
        }
    }
    swap(arr, sortedIndex, right);
    quickSort(arr, left, sortedIndex - 1);
    quickSort(arr, sortedIndex + 1, right);
}

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

병합 정렬 (Merge Sort)

• 분할 정복(divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.
• 안정적이며 시간 복잡도는 $O(nlogn)$이다.
• 코딩 테스트에서 이 이론을 이해하고 응용해서 푸는 문제가 종종 나온다.

핵심 이론

• 나눌 수 없을 만큼의 부분 그룹으로 분할한다.
• 부분 그룹들을 각각 병합하면서 정렬한다.
  • 정렬을 하면서 $N$만큼의 연산이 일어난다.
  • 병합-정렬 과정을 총 $logN$ 만큼 반복한다.
  • 따라서 시간 복잡도는 $NlogN$이다.

출처: https://en.wikipedia.org/wiki/Merge_sort

2개의 그룹을 병합하는 과정

• 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.
• 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
  • 각 포인터는 그룹 별로 하나씩 둔다.
  • 즉, 그룹에서 포인터를 두고 서로의 값을 비교하여 작은 것부터 배열에 담는다.
• 이 과정을 어떻게 응용할 수 있을지 생각할 것.
  • 예를 들어, 자동차 경주에서 몇 번 역전했는지를 확인한다면?

오름차순으로 자릿수 정렬하기

private static void mergeSort() {
    int A[] = new int[N];
    devide(A, 0, N);
}

private static void devide(int[] arr, int low, int high) {
    if (high - low < 2) {
        return;
    }

    int mid = (low + high) / 2;
    devide(arr, 0, mid);
    devide(arr, mid, high);
    merge(arr, low, mid, high);
}

private static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low];
    int t = 0, l = low, h = mid;

    // 왼쪽 배열과 오른쪽 배열 중 하나를 다 비울때까지 반복
    while (l < mid && h < high) {
        // 작은 값을 temp 배열에 우선해서 담기
        if (arr[l] < arr[h]) {
            temp[t++] = arr[l++];
        } else {
            temp[t++] = arr[h++];
        }
    }

    // 만약 왼쪽 배열이 남아있다면 담기
    while (l < mid) {
        temp[t++] = arr[l++];
    }

    // 만약 오른쪽 배열이 남아있다면 담기
    while (h < high) {
        temp[t++] = arr[h++];
    }

    // temp 배열을 원본 배열로 복사 (정렬 완료)
    for (int i = low; i < high; i++) {
        arr[i] = temp[i - low];
    }
}

기수 정렬 (Radix Sort)

• 값을 비교하지 않는 특이한 정렬이다.
• 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.
• 시간 복잡도는 $O(kn)$이다. (k=데이터의 자릿수)
  • 시간 복잡도가 가장 짧은 정렬이므로, 코딩 테스트에서 정렬해야 하는 데이터의 개수가 너무 많다면 기수 정렬 알고리즘을 활용해 보자.

핵심 이론

• 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표한다.
  • 큐가 10개인 이유는, 한 자릿수에 올 수 있는 값은 0~9까지이기 때문이다. 값을 표현하기 위해 10개의 큐를 사용한다.

출처: https://www.geeksforgeeks.org/c-program-for-radix-sort/

• 정렬 과정
  1. 대상 데이터가 주어졌을 때, 각 데이터의 일의 자릿수를 기준으로 큐에 (해당 데이터를) 넣는다.
  2. 큐에 넣은 데이터를 순차적으로 빼면 일의 자릿수를 기준으로 데이터를 정렬한 결과가 나온다.
  3. 일의 자리에서 정렬된 순서 기준(2번의 결과)으로 십의 자릿수를 기준으로 큐에 데이터를 저장한다.
  4. 큐에 넣은 데이터를 순차적으로 빼면 십의 자릿수를 기준으로 데이터를 정렬한 결과가 나온다.
  5. 위 과정을 자릿수(k)만큼 반복한다.

오름차순으로 자릿수 정렬하기

// 자릿수 (개수)
int MaxNumber = A[0];
for (int num : A){
    if (num > MaxNumber) {
        MaxNumber = num;
    }
}

// bucket 초기화
Queue<Integer>[] buckets = new Queue[10];
for (int i = 0; i < 10; i++) {
    buckets[i] = new LinkedList<>();
}

// 자릿수를 기준으로 정렬
for (int exp = 1; exp <= MaxNumber; exp *= 10) {

    // 버킷에 분류하여 저장
    for (int num : A) {
        int digit = (num / exp) % 10;
        buckets[digit].add(num);
    }

    // 버킷에서 꺼내기 (정렬)
    int index = 0;
    for (int digit = 0; digit < buckets.length; digit++) {
        while (!buckets[digit].isEmpty()) {
            A[index++] = buckets[digit].poll();
        }
    }
}

for (int i = 0; i < N; i++) {
    System.out.print(A[i] + " ");
}

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

스택과 큐

스택과 큐는 배열에서 발전된 형태의 자료구조이다. 스택과 큐는 구조는 비슷하지만 처리 방식이 다르다.

스택

• 스택은 삽입과 삭제 연산이 후입선출(LIFO, Last-in First-out)이 이뤄지는 자료구조이다.
• 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
• 스택은 깊이 우선 탐색(DFS, Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다.
  • 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

// Java의 스택
Stack<Integer> stack = new Stack<>();

스택 용어

위치

• top: 삽입과 삭제가 일어나는 위치 연산
• push : top 위치에 새로운 데이터를 삽입하는 연산
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

큐

• 삽입과 삭제 연산이 선입선출(FIFO, First-in First-out)로 이뤄지는 자료구조
• 스택과 다르게 먼저 들어온 데이터가 먼저 나가므로, 삽입과 삭제가 양방향에서 이뤄진다.
• 너비 우선 탐색(BFS, Breadth First Search)에서 자주 사용한다.

// Java의 큐
Queue<Integer> myQueue = new LinkedList<>();

큐 용어

• reer : 큐에서 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• add : reer 부분에 새로운 데이터를 삽입하는 연산
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

우선순위 큐

• 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
• 일반적으로 힙(Heap)을 이용해 구현하는데, 힙은 트리 종류 중 하나이므로 여기서는 개념만 알고 뒤에서 다룬다.

// Java의 우선순위 큐
PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) -> {
    int first_abs = Math.abs(o1);
    int second_abs = Math.abs(o2);

    if(first_abs == second_abs) {   // 절댓값이 같은 경우 음수 우선
        return o1 > o2 ? 1 : -1;
    }
    return first_abs - second_abs;  // 절댓값 작은 데이터 우선
});

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런