Java Day21

YDC·2025년 7월 21일

CS Java OSI 7layer TCP/IP 삽입정렬 자료구조

우테코8기

목록 보기

21/23

Day 20 복습

toUpperCase란?

모든 영문자를 대문자로 만드는 메소드

선택정렬

선택정렬은 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정함
한 셀씩 이동하면서 현재까지 가장 작은 값을 변수에 저장함 현재 변수값보다 작은 값이들어있는 셀을 만나면
변수가 새인덱스를 가르키도록 값을 대체함
처음엔 인덱스 0 이 최솟값으로 변수에 들어간 후 한번의 패스스루를 거쳐 인덱스0을 최솟값으로 만들고
인덱스1부터 다시 반복함

선택 정렬의 효율성

선택정렬은 비교와 교환 두 종류의 단계를 포함함 N개의 원소가 있을때
(N-1)+(N-2)+(N-3)…의 비교를 실행함
교환은 한 패스스루 당 최소 한 번 일어남 버블 정렬과 달리 최악의 시나리오에선 빠짐없이 교환을 한번 해야함
선택 정렬은 버블 정렬보다 단계수가 반정도 적음 즉 두배 정도 빠름

빅오는 상수를 무시함

선택 정렬은 버블 정렬의 반 즉 O(N^2/2)로 설명할 수 있지만 선 정렬은 빅오로 표현하면 똑같이 O(N^2)이다
빅 오 표기법은 지수가 아닌 수는 포함하지 않기 때문이다

빅오의 역할

빅오는 특정 시점부터 어느 유형이 다른 유형보다 속도가 빨라지는지 중요하지 않다
빅 오는 데이터가 많을때 한 알고리즘이 어떤 시점부터 빠르다는걸 보장하기 대문에
어떤 알고리즘을 서야하는지 대체로 알 수 있다

HTTPS

HyperTextTransferProtocol Secure
HTTP의 +보안(암호화)방식
서버와 클라이언트가 데이터를 주고받을때 누군가 훔쳐보지 못하게 암호화 해주는 통신 방식

브라우저가 서버에 접속
서버가 인증서(SSL/TLS)를 보냄
브라우저가 신뢰 가능한 인증서인지 검증
서로 암호화 키를 주고받음 (핸드셰이크)
이후부터는 모든 통신이 암호화됨

학습목표

백준

11718 그대로 출력하기
25083 새싹
킹, 퀸, 룩, 비숍, 나이트, 폰

CS

누구나 알고리즘 6강

백준

1.11719 그대로 출력하기

문제

입력 받은 대로 출력하는 프로그램을 작성하시오.

입력

입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않는다.

출력

입력받은 그대로 출력한다.

예제 입력

Hello
Baekjoon
Online Judge

예제 출력

Hello
Baekjoon
Online Judge

풀이

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

public class BOJ_11718_PrintAsIs {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = br.readLine()) != null) {
            System.out.println(line);
        }
    }
}

입력이 들어오지 않을때 자동으로 종료 되는 로직 구현

문제

아래 예제와 같이 새싹을 출력하시오.

입력

입력은 없다.

출력

새싹을 출력한다.

예제 출력 1

     ,r'"7

r-_ ,' ,/ \. ". L_r' ~\/
|
|

풀이

package string;

public class BOJ_25083_Sprout {
    public static void main(String[] args) {
        System.out.println("         ,r'\"7");
        System.out.println("r`-_   ,'  ,/");
        System.out.println(" \\. \". L_r'");
        System.out.println("   `~\\/");
        System.out.println("      |");
        System.out.println("      |");
    }
}

\출력이나 “출력하는 문제

문제

동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다.
체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다.
체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다.
동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다.

출력

첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.

예제 입력 1

0 1 2 2 2 7

예제 출력 1

1 0 0 0 0 1

예제 입력 2

2 1 2 1 2 1

예제 출력 2

-1 0 0 1 0 7

풀이

package string;
import java.util.Scanner;

public class BOJ_3003_Chess {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] chess = {1, 1, 2, 2, 2, 8};
for (int i = 0; i < 6; i++) {
int piece = sc.nextInt();
System.out.print(chess[i]-piece+" ");
}
}

}

배열을 가지고 연산을 하는 문제

CS

1.누구나 자료구조와 알고리즘 6강

삽입정렬을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는것에 장점을 확인함

삽입정렬

첫 번째 패스 스루일때 임시로 인덱스 1(두번째 셀의 값)을 삭제하고 임시 변수에 저장함
인덱스 1에 공백이 생기고 왼쪽에 있는 값과 비교 후 그 값이 임시 변수보다 크다면 오른쪽으로 시프트함
임시로 삭제한 값보다 더 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트가 끝남 배열이 완전히 정렬될 때까지 반복함

삽입정렬의 효율성

삽입정렬에 포함된 단계는 삭제 비교 시프트 삽입 네종류가 있음

비교는 공백 왼쪽에 있는 값과 삭제된 값을 비교할 때마다 일어남
배열이 역순으로 되있는 최악의 경우 각 패스스루마다 모든 수를 비교해야함
1+2+3+…+N-1번의 비교가 일어남
원소가 N개인 배열일 때 대략 N^2/2번의 비교가 일어남

시프트는 값을 한 셀 오른쪽으로 옮길때마다 일어남
최악의 경우 비교가 일어날 때마다 시프트를 해야하므로 비교 횟수만큼 시프트가 일어남 N^2/2

따라서 최악의 경우 비교와시프트의 단계수는 N^2번

삭제하고 다시 삽입하는 작업은 패스스루당 한번 씩 일어남 따라서 N-1 두개 2N-2

모든 단계를 다합치면 N^2+2N-2

하지만 빅오에는 상수를 무시하는 중요한 규칙이 있기에 O(N^2+N)으로 단순화 시킬 수 있고
또한 빅오 표기법에서는 가장 높은 차수의 N만 고려하기에
O(N^2)이됨

버블 정렬은 N^2이고 선택 정렬은 N^2/2이고 삽입 정렬은 N^2+2N-2이기때문에
버블 정렬이나 삽입 정렬은 선택 정렬보다 두배 느리다고 생각할 수 있으나 그렇게 간단하지 않음

평균 시나리오

최악의 시나리오의 경우 선택 정렬이 삽입정렬보다 빠른게 맞으나 평균시나리오도 중요하게 고려해야함
최선과 최악의 시나리오는 상대적으로 드물게 발생함 실제로는 평균 시나리오가 일어남
최선의 시나리오에서 삽입 정렬은 패스스루 한번당 비교만 하며 시프트는 일어나지 않는다
최악과 최선의 반으로 평균을 내면 데이터의 반을 비교하고 반을 시프트 한다
삽입정렬이 최악에서 N^2단계가 걸린다면 평균에선 N^2/2가 걸린다 하지만 빅오에선 똑같이 N^2이다
위같이 시나리오에 따라 성능이 크게 좌우 된다

최선의 평균 최악의 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것만큼이나

사용자 요구에 맞는 최적의 알고리즘을 고르는 핵심 기술임

2.OSI7Layer & TCP/IP 4Layer

OSI 7 계층이란?

OSI 7 계층은 네트워크 통신이 일어나는 과정을 7단계로 나눈 국제 표준화 기구(ISO)에서 정의한 네트워크 표준 모델

1계층 - 물리계층(Physical Layer)

주로 전기적, 기계적, 기능적인 특성을 이용해서 통신 케이블로 데이터를 전송하는 물리적인 장비
단지 데이터 전기적인 신호(0,1)로 변환해서 주고받는 기능만 할 뿐
이 계층에서 사용되는 통신 단위 : 비트(Bit)이며 이것은 1과 0으로 나타내어지는, 즉 전기적으로 On, Off 상태
장비 : 통신 케이블, 리피터, 허브 등

2계층 - 데이터 링크계층(DataLink Layer)

물리계층을 통해 송수신되는 정보의 오류와 흐름을 관리하여 안전한통신의 흐름을 관리
프레임에 물리적 주소(MAC address)를 부여하고 에러검출, 재전송, 흐름제어를 수행
이 계층에서 전송되는 단위 : 프레임(Frame)
장비 : 브리지, 스위치, 이더넷 등(여기서 MAC주소를 사용)
-> 브릿지나 스위치를 통해 맥주소를 가지고 물리계층에서 받은 정보를 전달함.

3계층 - 네트워크 계층(Network Layer)

데이터를 목적지까지 가장 안전하고 빠르게 전달
라우터(Router)를 통해 경로를 선택하고 주소를 정하고(IP) 경로(Route)에 따라 패킷을 전달 > IP 헤더 붙음
이 계층에서 전송되는 단위 : 패킷(Packet)
장비 : 라우터

4계층 - 전송 계층(Transport Layer)

port 번호, 전송방식(TCP/UDP) 결정 > TCP 헤더 붙음
- TCP : 신뢰성, 연결지향적
- UDP : 비신뢰성, 비연결성, 실시간
두 지점간의 신뢰성 있는 데이터를 주고 받게 해주는 역할
신호를 분산하고 다시 합치는 과정을 통해서 에러와 경로를 제어

5계층 - 세션 계층(Session Layer)

주 지점간의 프로세스 및 통신하는 호스트 간의 연결 유지
TCP/IP 세션 체결, 포트번호를 기반으로 통신 세션 구성
API, Socket

6계층 - 표현 계층(Presentation Layer)

전송하는 데이터의 표현방식을 결정(ex. 데이터변환, 압축, 암호화 등)
파일인코딩, 명령어를 포장, 압축, 암호화
JPEG, MPEG, GIF, ASCII 등

7계층 - 응용 계층(Application Layer)

최종 목적지로, 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행(ex. explore, chrome 등)
HTTP, FTP, SMTP, POP3, IMAP, Telnet 등과 같은 프로토콜이 있다.

TCP/IP 4계층이란?

OSI 7계층 보다 먼저 나온 규격이나 현재 더 많이 활용 된다

1계층 - 네트워크 액세스 계층(Network Access Layer)

OSI 7계층의 물리계층(1)과 데이터 링크 계층(2)에 해당
TCP/IP 패킷을 네트워크 매체로 전달하는 것과 네트워크 매체에서 TCP/IP 패킷을 받아들이는 과정을 담당
에러 검출 기능(Detecting errors), 패킷의 프레임화(Fraimg packets)
네트워크 접근 방법, 프레임 포맷, 매체에 대해 독립적으로 동작하도록 설계.
물리적인 주소로 MAC을 사용
LAN, 패킷망, 등에 사용됨

2계층 - 인터넷 계층(Internet Layer)

OSI 7계층의 네트워크 계층(3)에 해당
어드레싱(addressing), 패키징(packaging), 라우팅(routing) 기능을 제공
네트워크상 최종 목적지까지 정확하게 연결되도록 연결성을 제공하게 됨.
프로토콜 종류 – IP, ARP, RARP

3계층 - 전송 계층(Transport Layer)

OSI 7계층의 전송 계층(4)에 해당
IP와 Port를 이용하여 프로세스와 통신
애플리케이션 계층의 세션과 데이터그램(datagram) 통신서비스 제공
통신 노드 간의 연결을 제어하고, 신뢰성 있는 데이터 전송을 담당한다.
프로토콜 종류 – TCP, UDP

4계층 - 응용 계층(Application Layer)

OSI 7계층의 세션 계층(5), 표현 계층(6), 응용 계층(7)에 해당한다.
프로그램(브라우저)가 직접 인터액트하는 레이어. 데이터를 처음으로 받는곳
다른 계층의 서비스에 접근할 수 있게 하는 애플리케이션을 제공
애플리케이션들이 데이터를 교환하기 위해 사용하는 프로토콜을 정의
HTTP, SMTP등의 프로토콜을 가진다.
TCP/UDP 기반의 응용 프로그램을 구현할 때 사용한다.
프로토콜 종류 – FTP, HTTP, SSH

OSI는 개념 모델, TCP/IP는 실제 구현 모델
OSI는 이론적으로 완벽하게 쪼개놓은 것

리뷰

거의 2주만에 돌아왔습니다 동미참 예비군과 휴식을 가지고 오늘은 몸풀기로 가볍게 해봤습니다
내일 부터는 Spring을 들어갈예정입니다 오랜만에 공부를하니 공부가 잘 되는거 같기도하고
너무 나태하게 살았나라는 생각도 들기도 합니다 내일부터는 더 열심히 하겠습니다

YDC

초심자

이전 포스트

Java Day20

다음 포스트

Java Day21

우테코8기

Day 20 복습

toUpperCase란?

선택정렬

선택 정렬의 효율성

빅오는 상수를 무시함

빅오의 역할

HTTPS

학습목표

백준

CS

백준

1.11719 그대로 출력하기

문제

입력

출력

예제 입력

예제 출력

풀이

문제

입력

출력

예제 출력 1

풀이

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이

}

CS

1.누구나 자료구조와 알고리즘 6강

삽입정렬을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는것에 장점을 확인함

삽입정렬

삽입정렬의 효율성

평균 시나리오

최선의 평균 최악의 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것만큼이나

2.OSI7Layer & TCP/IP 4Layer

OSI 7 계층이란?

1계층 - 물리계층(Physical Layer)

2계층 - 데이터 링크계층(DataLink Layer)

3계층 - 네트워크 계층(Network Layer)

4계층 - 전송 계층(Transport Layer)

5계층 - 세션 계층(Session Layer)

6계층 - 표현 계층(Presentation Layer)

7계층 - 응용 계층(Application Layer)

TCP/IP 4계층이란?

1계층 - 네트워크 액세스 계층(Network Access Layer)

2계층 - 인터넷 계층(Internet Layer)

3계층 - 전송 계층(Transport Layer)

4계층 - 응용 계층(Application Layer)

리뷰

Java Day20

Java Day 22

0개의 댓글