230418_DB복습

안녕하세요. 보랏입니다. 

 

오늘은 네트워크 TCP/IP에 대한 기본적인 내용과 

탐욕 알고리즘에 대해 복습하겠습니다.

 

오늘도 복습 내용이 적은데

현재 딥러닝을 활용한 장고 홈페이지 구축을 진행중에 있는데

아직 설정 단계라서 향후에 전부되면 한 번에 정리하도록 하겠습니다.

 

복습 시작하겠습니다.

 

 

1. 네트워크 TCP/IP

 

DHCP

• TCP/IP가 제대로 작동하기 위해서 네트워크에 속한 각 호스트의 IP어드레스가 중복되지 않아야 하는데 이를 관리하는 프로토콜
• 동적으로 IP주소를 변경하는 프로토콜
• 이 방식을 사용하면 호스트가 네트워크에 연결될 때, IP어드레스와 서브넷 마스크 등의 정보가 자동으로 설정
• 신규 호스트는 네트워크의 모든 호스트에게 브로드캐스트 방식으로 DHCP발견 메시지를 보내고, 이 메시지를 받은 DHCP서버가 사용 가능한 IP어드레스를 알려주는 방식으로 자동 할당

 

IP어드레스 활용

• IP어드레스는 네트워크 부, 호스트 부(컴퓨터, 네트워크 장비 등)으로 구성 -> 192.168.1.(네트워크 부).100(호스트부)
• 어드레스 클래스 : 하나의 IP안에서 어디까지가 네트워크 부이고 어디까지가 호스트 부인지 미리 그 길이를 조정하여 결정한 것
• 서브넷 마스크 : 어드레스 클래스의 네트워크 부의 길이가 고정된 것과 다르게 서브넷 마스크는 이 길이를 비트 단위로 유연하게 늘려서 사용 가능
  • 서브넷 마스크를 이용하면 네트워크를 더 세분화하여 서브 네트워크(서브넷)을 구성 가능
  • 서브넷 마스크는 네트워크 부의 길이를 늘릴 수는 있지만 줄이지는 못하여 호스트 부가 긴 클래스, A나 B의 어드레스를 세분화할 때 사용하는 것이 일반적
• IP 어드레스 할당 방법
  • IP어드레스는 네트워크 상에서 호스트를 식별하기 위해 사용되는데, 전체 32비트 중 네트워크 부를 제외한 호스트 부 부문만 자유롭게 할당하여 사용 가능

ipconfig, ping, tracert, nslookup

• ipconfig : 사용 중인 컴퓨터의 ip어드레스 확인
• ping : 통신하려는 상대가 접속 가능한 상태인지 확인
• tracert : 목적지 컴퓨터까지 통신하면서 통과한 경로 확인
• nslookup : DNS서버에게 도메인명을 주고 ip어드레스를 물어보거나 거꾸로 ip어드레스를 주고 도메인명을 물어볼 때 사용

 

2. 탐욕 알고리즘(greedy algorithm)

 

탐욕 알고리즘

• 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 법
• 최적해를 구하는 데에 사용되는 근사적 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방법으로 진행하여 최종적인 해답에 도달

 

문제 해결방법

• 선택 절차 : 현재 상태에서의 최적의 해답을 선택
• 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

 

탐욕 알고리즘 조건

• 탐욕스런 선택 조건 : 이후의 선택에 영향을 주지 않는다는 것
• 최적 부분 구조 조건 : 문제에 대한 최적해가 부분문제에 대해서도 최적해라는 것
• 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점을 보유 → 근사 알고리즘으로 사용 가능

 

코딩테스트 문제 - 백준 (https://www.acmicpc.net/problem/11047)

11047번: 동전 0

문제

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

 

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 1출력

6

 

알고리즘

N, K = map(int, input().split())
A = [0] * N

for i in range(N) : 
	A[i] = int(input())
    
cnt = 0

for x in range(N-1, -1, -1) : 
	if A[x] <= K : 
    	cnt += int(K / A[x])
        K = K % A[x]
        
print(cnt)

 

이렇게 복습 마무리하겠습니다.

 

감사합니다.