dp

https://www.acmicpc.net/problem/2638간만에 만족스러운 풀이가 나와서 포스팅import sysfrom collections import dequeinput = sys.stdin.readline'''바깥공기부터 탐색만약 공기에 노출된 치즈를 발견할시 해당 치즈의 값을 +1 만약 그렇게 더한 치즈의 숫자가 2 이상일경우 melting cheese에 추가순회가 끝나면 melting cheese에 담겨있던 치즈를 다 녹인다.melting cheese를 탐색 queue에 append여기서 포인트는 melting count를 계속 유지해주며 작업 queue에 더해주는것같음필요한 자료형치즈 graphmelting count graph작업 queuemelting queuevisited'..

CSAPP 이기종 자료구조 (Heterogeneous) 이기종 자료구조란? 다른 여러가지의 데이터를 포함하고 있는 구조체(struct)와 공용체(Union)을 뜻한다. 구조체(struct) C 언어의 구조체(structure)는 다양한 데이터 타입의 멤버들을 하나로 묶어서 새로운 데이터 타입을 정의하는 데 사용. 자바의 class의 개념과 아주 약간 비슷함 구조체의 offset 각 구조체의 필드값에 따른 byte 용량으로 정한다. char = 1byte, long = 8byte... 공용체(union) 말 그대로 필드값의 가장 큰 Byte만큼만 메모리를 할당하고, 그 메모리를 모든 필드값들과 공유하며 사용함. 메모리를 효율적으로 사용할 수 있지만, 한번에 하나의 필드값밖에 할당할 수 없어 지금은 잘 사용..

알고리즘 Dynamic Programming DP란? 점화식을 사용해 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 큰 문제에 대입해서 푸는 방법 계산값을 재탕한다는 의미로 받아들였다. 알게모르게 알고리즘 문제를 풀이하며 여러번 사용했던 방법. DP를 사용하는 이유 난 이 이유를 백준의 피보나치를 풀이하며 찾았는데, 기존 피보나치의 경우 일반적인 재귀로 풀면 O(n²)이지만 dp로 값을 재탕하면 시간 복잡도를 O(n)으로 줄일 수 있다. 자세한 내용은 2748 피보나치수 2 문제를 풀어보면 바로 감이 잡힌다. 구현법 젓번째로는 Bottom-Up 방식으로 DP 테이블을 만들어 해당 테이블을 만족하는 점화식을 생성하고, 그 식을 바탕으로 반복문을 사용해 접근하는 방식이다. 해당 방식의 장점은 재..