전체 글 (19) 썸네일형 리스트형 [ 백준 12865번 평범한 배낭 ] Python 코드 (DP) 1. 문제 백준 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 2. 풀이 Dynamic Programming의 대표적인 문제이다. 원래라면 모든 부분집합을 다 확인해야 하기에 O(2**N)의 시간 복자도를 가지지만, DP를 활용함으로써 시간복잡도를 O(NM)으로 개선시켰다. 다만 여기서 M은 N에 대해 독립적인 값이기 때문에, M이 매우 커진다면 시간복잡도 또한 매우 커진다. DP문제의 쟁점은 늘 그렇듯 어떻게 prob.. 0. Pre-Learning 미즈구치 카츠야, 『모두의 네트워크』, 이승룡 역, 길벗(2022), 1장 ~ 2장 Ch1. 네트워크 첫걸음 1. 네트워크의 구조 1.1. 컴퓨터 네트워크란? 컴퓨터 네트워크 정의 ==분산되어 있는 컴퓨터를 통신망으로 연결하여 자원을 공유할 수 있게한 것.== 컴퓨터 간 연결은 광케이블과 같은 유선, 혹은 와이파이와 같은 무선 매체를 통해 이뤄진다. 인터넷 정의 TCP/IP프로토콜 기반의 컴퓨터 네트워크 1.2. 패킷이란? 패킷 정의 네트워크를 통해 전송되는 데이터의 작은 형식화된 조각 패킷의 필요성 큰 데이터를 그대로 보낼 경우, 네트워크의 대역폭[^1]을 많이 점유해서 다른 데이터의 흐름을 막을 수 있다. 따라서 데이터를 작은 크기의 패킷으로 분할하여 전송할 필요성이 대두되었다. 단, 데이터를 수신한.. [ SWEA 14510번 나무 높이 ] Python 코드 (Greedy) 1. 문제 SWEA 14501번 나무 높이 2. 풀이 완전탐색 기반으로 풀이할 방법이 생각나지도 않을 뿐더러, 설사 어떻게 생각해낸다 하더라도 경우의 수가 너무많다. 따라서 Greedy로 풀어야한다. 이름부터 사악한 Greedy 알고리즘이란, 지역적인 최적값 선택의 연속이 글로벌한 최적값으로 이루어진다는 것인데 실제 문제를 풀어보면, 그냥 알아서 잘 짜야한다. 나는 흡사 IQ 테스트같다고 생각한다. 따라서 Greedy한 알고리즘을 만들 때 가장 중요한 것은 코드가 너무 많은 if문으로 case를 나누지 말아야한다. 그러면 일단 Greedy하지 않을 뿐더러, 무엇보다 우리가 푸는 문제가 누군가에 의해 만들어졌다는 것을 고려할 때, 코드가 지저분하게 케이스를 나누고 있다면 접근방식이 잘못 되었을 가능성이 농.. 이전 1 ··· 3 4 5 6 7 다음
