Hello, Freakin world!

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망�� www.acmicpc.net 문제 풀이 얼리 어답터(EA)를 이용해 모든 아이디어를 퍼트리기 위해서는 다음의 규칙이 필요합니다. 1. 현재 노드가 EA인 경우 - 자식 노드가 EA인 경우 - 자식 노드가 EA가 아닌 경우 2. 현재 노드가 EA가 아닌 경우 - 모든 자식 노드가 EA여야 한다. 위의 규칙을 적용해 트리 구조에서 재귀를 이용해 해결할 수 있습니다. 재귀를 이용해 구현할 때, 리프노드에서의 종결 조건과 맞물려서 최소값..

www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 한달 전인가? 너무 어려워서 패스했던 문제였습니다. 그런데 지금은 풀리네요. 풀이가 보였습니다. (오오... 성장해버렸구나) 저는 DP와 비트마스킹을 이용해 풀었습니다. DP 문제를 풀 때 역시 가장 중요한 건 부분 문제를 정의하는 겁니다. arrageStudent(i, previousRowStatus) : 0 ~ i번째 영역에서 이전 행의 상태가 previousRowStatus 일 때 배치할 수 있는 최대 학생 수 위처럼 정..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 바로 전에 LIS 문제를 풀었음에도 한참 헤맸습니다. 기존 LIS 로직을 그대로 쓰려면 입력 배열을 정렬할 필요가 있습니다. 정렬을 하지 않으려면 따로 처리를 해줘야 하는데 이 부분을 간과했네요. 정렬이 필요한 이유는 전깃줄이 꼬이는 조건과 관계가 있습니다. 줄 a,b가 있다고 할 때 줄이 꼬이지 않는 조건은 다음과 같습니다. - a.start b...

www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 이 문제를 계기로 다시 종만북을 펼쳐서 DP를 다시 공부했는데, 새로운 깨달음을 얻을 수 있었습니다. 지금까지 DP 문제를 풀 때, 어떤 유형는 메모이제이션을 이용해 풀어야 되고 어떤 문제는 점화식을 찾아서 바텀업으로 풀어야 된다는 식으로 문제를 분류했었는데 그럴 필요가 없었습니다. 이때까지 바텀업 방식의 풀이를 이용했지만 약간은 불편했습니다. 뭔가 직관적이지 않다라는 느낌을 지울 수 없었기 때문입니다. 그럼에도 ..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP 문제를 계속 풀고 있는데, 패턴이 참 다양하다는 생각이 듭니다. 그리고 꽤 재밌네요 ㅋㅋㅋ 핵심 아이디어는 위처럼 (i,j) 위치의 값이 1일 때 위, 왼쪽 위, 왼쪽 위치의 요소도 1이면 정사각형 만들어 진다에서 출발합니다. 나머지는 저 위의 아이디어를 기반으로 점화식을 작성하면 됩니다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이때까지 DP와는 성격이 조금 다른 문제였다. 이전까지는 단순히 완전 탐색의 바텀업 버전이었지만 이 문제는 재귀를 이용한 탑다운 방식에 cache배열을 추가하면서 해결할 수 있다. 이 문제에서 가장 중요한 한 문장이 있다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는..

www.acmicpc.net/problem/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 이 글의 초점은 문제 풀이에 있지 않다. 그러므로 바로 본론으로 들어가겠다. 이 문제의 점화식은 다음과 같다. 아직 몇 문제 풀어보진 않았지만 지금까지 풀어본 DP 문제들은 '완전 탐색의 바텀-업 버전'이었다. 이런 문제들은 완전 탐색을 바텀업으로 구현하기 위해 점화식을 세울 필요가 있다. 이 점화식도 그냥 하늘에서 떨어지는게 아니라 완전 탐색의..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 재귀를 이용한 완전 탐색도 통과할 수 있습니다. 입력이 최대 15이므로 2^15가 32768이기 때문에 충분히 통과할 수 있습니다. dp와 완전탐색 각각의 방식이 이 문제에서는 별다른 속도 차이를 보이지 않았습니다. 문제가 단순해서인지 결국 DP를 이용해 푼 방식이 재귀를 이용한 완전탐색을 그저 for문으로 바꾼 것일 뿐이었는데 DP의 정의에 대해 다시 한번 생각해보게 되네요. DP라는게 그저 for문을 이용한 바텀업 방식의 완전탐색일 뿐인 아니지 않나? 라는 생각이 들었습니다. DP의 최적 부분 구조를 찾는데 항상 애를 먹었는데, ..