밤이 블로그

BOJ#2631 줄세우기 * 문제https://www.acmicpc.net/problem/2631 * 풀이일단 [4, 1, 2, 3, 5]인 경우의 문제를 손으로 풀어봅시다.거의 대부분 4를 3뒤로 옮겨서 한번만에 문제를 푸셨을 것입니다. 위 과정을 조금 더 상세하게 써보면 1. 수열에서 증가하는 가장 긴 부분 수열을 구하고 (이것들은 움직이지 않음)[4, 1, 2, 3, 5] 나머지 숫자를 적절한 자리로 이동시키면 옮겨지는 아이의 수를 최소로 하면서 줄을 세울 수 있습니다.[4, 1, 2, 3, 5] -> [1, 2, 3, 4, 5] 여기서 우리는 횟수만 구하면 되므로전체 길이 - LIS(Longest Increasing Subsequence) 길이 = 아이의 최소 이동 횟수 = 원하는 답 저는 LIS..

BOJ#2532 먹이사슬 (Chain) * 문제https://www.acmicpc.net/problem/2532 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2012 > 중등부 3번 * 풀이Tip #1) 공식 풀이는 한국정보올림피아드 홈페이지에서 볼 수 있습니다.Tip #2) 더블릿(http://www.dovelet.com)에서 채점하면 테스트케이스를 볼 수 있습니다.Tip #3) LIS 문제입니다. LIS 관련해서는 아래 문제들을 먼저 풀어보는 것을 추천드립니다.-가장 긴 증가하는 부분 수열 (https://www.acmicpc.net/problem/11053)-전깃줄 (https://www.acmicpc.net/problem/2565) 이 문제의 입력값 중 동물의 번호는 필요가 없습..

BOJ#2565 전깃줄 * 문제https://www.acmicpc.net/problem/2565 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2007 > 초등부 4번 * 풀이 문제 : 전깃줄이 교차하지 않기 위해 없애야 하는 전깃줄의 최소 개수를 구하시오. 문제에서 표시된 위 지문과 같이 전깃줄을 '제거'하는 관점에서 접근하게 되면 문제를 풀기 어려워지게 됩니다. 전깃줄을 하나씩 '제거'하면서 최소한 몇개를 제거해야 하는지 생각하는 것 보다,전깃줄을 하나씩 '추가'하면서 최대한 몇개까지 겹치지 않고 추가할 수 있는지 생각해 봅시다. * 전깃줄이 겹치지 않을 조건 : A를 기준으로 정렬했을 때, B가 순차적으로 나열되어 있으면 된다. 주어진 입력을 A 기준으로 정렬해보면 LIS의 형태가 ..

BOJ#11053 가장 긴 증가하는 부분 수열(LIS) * 문제https://www.acmicpc.net/problem/11053 * 풀이 유명한 문제인 Longest Increasing Subsequence (LIS)입니다.O(N^2) 방법과 O(N logN) 방법으로 풀어보았습니다. 기존에 워낙 설명이 잘 되어있어서 따로 포스팅 하지는 않겠습니다만,제가 공부할 때 참고했던 사이트 남겨드립니다. 1. LIS 이해 및 O(N^2) 풀이https://www.youtube.com/watch?v=CE2b_-XfVDk 위 동영상을 보시고 아래 저의 코드를 보시면 되겠습니다. * 나의 코드 // O(N^2) for (int i = 1; i < N; i++) { for (int j = 0; j < i; j++) {..