모든 경험을 소중하게

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 14002번 문제 '가장 긴 증가하는 부분 수열 4' 이다. 이 문제는 LIS 로 알려진 유명한 문제이다. 이 문제를 풀기 위해 이용한 알고리즘은 DP 이다. 물론, 2중 for 문을 이용해서 전체를 계속 순회해도 문제를 풀 수 있다. 특히 이 문제에서는 크기가 1000 이므로, O(n^2) 이다. 따라서 충분히 시간 내에 풀 수 있다. 하지만 DP 를 이용한다면, O(n) 으로 계산 할 수 있다. DP 문제는 다들 많이 풀어보는 유형이라 방법은 알고 있겠지만, 모르는 분들에게 도움이 되고자 설명한다. dp 배열을 수열 길이만큼 잡은 후, 0 으로 초기화 해준다. 여기서 C 언어를 사용하고 있다면, 전역변수로 선언하면 0..

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 14502번 문제 연구소 이다. 우선 시간 제한이 2초이므로, 그렇게 빡빡하지는 않다고 생각할 수 있었다. 문제를 마저 더 읽어보자. 새로 세울 수 있는 벽은 꼭 3개이다. 벽이 세워질 수 있는 곳은 0 값을 가지고 있는 좌표들뿐이다. 그렇다면, 어떻게 3개를 선택해야 가장 많은 0 을 남길 수 있을까? 문제를 마저 더 읽어보자. 우선, 벽을 세운 후, 2인 점들을 queue 에 넣은 후, BFS 를 돌아야 안전 영역 ( 0 ) 의 크기가 몇일지 알 수 있는 것 같다. 따라서, 모든 벽 3개를 다 세워봐야만 안전 영역의 크기를 알 수 있다고 판단이 든다. 그렇다면, 0 을 가진 좌표 중 3개를 선택해야 하므로, 0의 갯수..