문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 DP를 활용한 완전탐색 첫번째 접근법 (BFS) 각 격자별로 BFS를 수행하면서 DP 메모이제이션을 수행. 다음 탐색좌표에 대한 최장길이 DP값이 있다면 해당 부분문제 해를 이용하여 현재 최장길이를 구하는 식으로 풀이. 두번째 접근법 (DFS) 첫번째 접근에서 메모리초과가 발생하여 DFS로 변경 로직자체는 동일 각 좌표마다 DFS를 수행하면서 다음 나아가는 좌표에 대해 메모이..

Concept 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 Feature 배낭 문제에는 두 가지 유형이 존재 Fractional Knapsack : 물건을 쪼갤 수 있음. 무게나 가치가 소수점 단위로 나뉠 수 있는 문제. 0-1 Knapsack : 물건을 쪼갤 수 없음. 무게나 가치가 무조건 정수타입을 가지는 문제. Implement Brute-Force 가장 기본적인 풀이방법으로써 N개의 물건에 대해 가능할 수 있는 모든 조합을 만들어 보는 접근법. 시간복잡도는 O(2^N)으로 많이 느리다고 볼 수 있다. Dynamic Programming DP의 핵심은 메모이제이..

현재 진행하고 있는 C#기반 메신저 프로젝트에서 소켓 프로그래밍을 사용할 기회가 생겨 정리하게 되었습니다. 우선 이 프로젝트의 목적은 비동기 소켓통신을 통하여 채팅중계서버를 구현하고, 같은 로컬에 있는 각각의 클라이언트에서 채팅을 주고받을 수 있도록 하는 것에 있습니다. 일단 한눈에 예제를 확인할 수 있게 콘솔앱으로 작성하였고, 아래는 서버 측 소스코드입니다. static void Main(string[] args) { //서버측의 소켓을 생성, 클라이언트와 통신할 연결방식 및 프로토콜 타입을 선언 Socket server = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp); //모든 네트워크의 클라이언트의 연결을 받..