개구리의 개발 블로그 개구리의 개발 블로그

0. A stored-program computer stored program computer - 폰 노이만이 개발한 memory에 progrmas 저장하는 형태의 컴퓨터 program - set of instructions 1. Operating System is a software that manages a computer’s hardware. provides a basis for application progrmas acts as an intermediary(중개인) between the computer user and the computer hardware 2. What Operating Systems Do coputer system can be devided roughly into four co..

0. 시작하기에 앞서 데이터그램은 어떤 레이어의 PDU인가? 데이터그램을 전송 계층의 PDU라고 설명한 블로그를 많이 봤다. 전송 계층의 TCP, UDP 프로토콜의 차이가 패킷 교환 방식, 데이터그램 교환방식이기 때문이다. Computer Networking: A Top-down Approach 에서는 용어의 혼란을 줄이고자 TCP, UDP 패킷을 모두 세그먼트로 지칭하고 네트워크 계층의 패킷을 데이터그램이라고 표현한다. (p175) 구글에서 ‘datagram is’ 만 검색해도 같은 주제에 대한 질문이 가장 상위에 노출된다. https://stackoverflow.com/questions/11636405/definition-of-network-units-fragment-segment-packet-fra..

백준 15681번 트리와 쿼리 파이썬 문제 링크 - https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 반례를 찾는 것이 중요하다. 문제의 로직을 세울 수 있는 것만큼이나 중요한 것 같다. 쉬운 문제였지만 쉬운 반례를 찾지 못해 한참을 헤맸다. 1. 코드 #트리와 쿼리 (tree + dp ) 220503 #dp[node] = 1 이후에 #if len(tree[node]==1) : ret..

백준 3860번 할로윈 묘지 파이썬 문제 링크 - https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 정답률이 15퍼센트인 것을 모르고 문제를 풀기 시작했다. 문제를 번역하는 과정에서 중요한 내용들을 번역하지 않아서 이슈가 좀 있었던 것 같았다. 음수 사이클이 도착점에 도달하는 지 여부에 상관없이 존재하기만 한다면 Never을 출력해야 한다. 이 부분에서 많이들 오답을 받은 것 같다. 1. 풀이 시작점과 도착점이 고정되어 있다. 2차원 좌표에서 최단 거..

백준 1102번 발전소 파이썬 문제 링크 -https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 오랜만에 재밌는 DP 문제였다. 처음에는 문제를 보자마자 백트래킹으로 풀어야겠다고 생각했다. 그런데 생각해보면 A발전소를 고칠 수 있는 모든 발전소에 대한 경우를 탐색하기 때문에 가지치기가 불가능한 상황이다. 현재 상황에서 정상 작동하고 있는 모든 발전소가 A개이고 정상 작동하지 않는 모든 발전소가 B개라면 총 A*B개의 발전소를 고치는 조합이 존재한다..

백준 1182번 부분수열의 합 파이썬 문제 링크 - https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열은 연속할 필요 없이 주어진 수열에서 원소를 중복 없이 선택하면 된다. 즉, 주어진 수열의 순서가 바뀌어도 똑같은 답을 갖게 된다. 처음에는 백트래킹으로 시도했다. 전체 수열에서 원소를 선택하는 경우와 선택하지 않는 경우를 나누어 탐색한다. 하지만 DFS 도중에 가지치기 되는 경우가 없기 때문에 사실상 ..

백준 10282번 해킹 파이썬 문제 링크 - https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 간단한 다익스트라를 통해 해결 가능한 문제다. 방문 표시를 하며 다익스트라를 실행한 후 방문된 노드를 계산하는 작업을 따로 해주면 된다. 이 때 방문된 노드까지 가는 최단 시간 중 가장 큰 값을 갱신한다. 1. 풀이 의존성의 방향은 간선의 방향이다. 시작 노드는 1개로 지정되어 있다. 주어진 시작 노드에서 모든 노드에 대한 최단 경로를 구한다. 방문 표시된..

백준 1162번 도로포장 파이썬, 다익스트라 문제 링크 - https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 주어진 도로에서 최대 K개의 도로의 가중치를 0으로 만들 수 있다. 조합을 사용할까 고민했다. 다익스트라를 이용하여 dist배열을 2차원으로 만들고 도로의 가중치를 0으로 만든 횟수를 저장했다. 1. 풀이 heap에 현재까지 누적 가중치, 0으로 만든 도로의 수, 현재 노드를 넣어준다. 다음 노드를 방문..