Total
회장뽑기 (플로이드 워셜)
분석 [1389] 케빈 베이컨의 6단계 법칙 (플로이드-워셜) 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루 karla.tistory.com 풀이 """ 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있 다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다. 또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구..
플로이드 워셜 알고리즘
분석 [11403] 경로 찾기 (플로이드-워셜) 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 최단거리를 구하 karla.tistory.com 풀이 """ N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값 첫 번째 줄에는 도시의 수N(N
OSI 7 Layer 계층별 프로토콜
[TCP/IP] OSI 7계층, TCP/IP 4계층 1. OSI 7계층 1) 물리 계층 1계층 Physical Layer 시스템의 전기적, 물리적 표현을 나타낸다. 단지 데이터 전달 역할만을 하고, 알고리즘이나 오류 제어 기능은 존재하지 않는다. 허브, 케이블, 라우터, karla.tistory.com 1. Application Layer 1) FTP (File Transfer Protocol) 파일 전송 프로토콜 2) VSFTP (Very Secure File Transfer Protocol) VSFTP는 보안 부분을 특히 강조한 데몬으로 Redhat,Suse,Open-BSD에서 기본 FTP로 채택하고 있다. 보안, 빠른 퍼포먼스, 안정성을 주요 특징으로 소개하고 있다. ③SNMP (Simple Net..
[TCP/IP] OSI 7계층, TCP/IP 4계층
1. OSI 7계층 OSI(Open System Interconnection) 7계층은 국제표준화기구(ISO)에서 개발한 모델로, 네트워크 프로토콜 디자인과 데이터 통신을 계층으로 나눠 표준화한 것이다. 이렇게 계층을 나눈 이유는, 통신이 일어나는 과정을 단계별로 서술할 수 있으며, 특정 계층에서 문제가 발생할 시 해당 계층만 핸들하면 되기 때문이다. 1) 물리 계층 1계층 Physical Layer 시스템의 전기적, 물리적 표현을 나타낸다. 단지 데이터 전달 역할만을 하고, 알고리즘이나 오류 제어 기능은 존재하지 않는다. 허브, 케이블, 라우터, 전원 스위치 전선, 전파, 광섬유, 동축케이블, 모뎀(Modem), CSU 등이있다. 신호로 변환하여 전송하는 계층 전송 단위는 Bit를 사용한다. 2) 데이..
[12865] 평범한 배낭 (냅색 알고리즘)
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 분석 가방에 최대 Mkg 까지 담을 수 있을 때, dp[i][j] = 가방에 담은 물건의 무게 합이 i일 때, 처음 j개의 물건 중 담을 수 있는 최대 가치 ( 1 < i
가방 문제 (냅색 알고리즘)
""" 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치 한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다. 가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다. 첫 번째 줄은 보석 종류의 개수, 가방에 담을 수 있는 무게의 한계값 두 번째 줄부터 각 보석의 무게와 가치 4 11 5 12 3 8 6 14 4 8 """ import sys input=sys.stdin.readline n,m=map(int, input().split()) d=[0]*(m+1..
알리바바와 40인의 도둑 (Bottom-Up, Top-Down)
bottom up """ 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1,1)격자에서 (N,N)까지 가는데 드는 에너지의 최소량 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 3 2 5 2 3 4 6 5 2 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. 5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 ..
최대 선 연결하기
분석 최대 부분 증가수열 분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 karla.tistory.com 풀이 """ 왼쪽의 번호와 오른쪽의 번호, 같은 번호끼리 선으로 연결 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열 오른쪽의 번호 정보가 위부터 아래 순서 서로 선이 겹치지 않고 최대 몇 개의 선 연결? 자연수 N(1