[문제] https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net [문제 풀이] 별 찍기에서 처음으로 좌절을 느끼는 문제지만 실버 난이도의 분할 정복을 풀고 왔다면 겁먹을 것 없이 도전할 만한 문제이다. 1 2 3 4 5 6 7 8 9 로 만들어져 있는 주사위가 있다면 해당 주사위에서 5번을 제외하고 모두 별을 찍으면 된다. 그렇게 된다면 만일 크기가 9인 주사위의 경우에는 ********* * ** ** * *********..

[문제] https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [문제 풀이] 기존에 풀었던 가장 긴 증가하는 부분 수열에서 풀었던 방식을 이용해서 풀었다. DP를 이용해서 부분 수열의 가장 긴 길이가 몇인지를 파악한 후에 뒤에서 부터 O(n)을 이용해서 순서대로 해당 길이에 맞은게 있으면 그 길이로부터 1씩을 제거하면서 파악하였다. 입력을 해주면서 동시에 각 수의 길이..

[문제] https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [문제 풀이] 가장 긴 증가하는 부분 수열2 와 동일하게 생각하면 된다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include #define endl "\n" using namespace std; int main(){ int n; cin>>n;..

[문제] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net [문제 풀이] 가장 긴 증가하는 부분 수열 문제와 달리 단순히 dp 로 풀면 100만 X 100만 이 되기 때문에 시간 초과가 날 수밖에 없는 문제다. 해당 문제를 해결하기 위해서는 그래서 입력 부분에서 애초에 들어갈때 알고리즘적인 로직을 만들어줘야한다. 가장 긴 증가하는 부분 수열 문제에 lower bound를 접목시키자. 만약 10 20 30 25 50 60 이라는 배열이 있다고 치면..

[문제] https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net [문제 풀이] 어려워보이지만 생각보다 간단하게 맞출 수 있는 문제다. 문제에 낚이지 말고 해당 결과값을 만들기 위해서 뭐가 필요한지를 잘 생각하자! 만일 살짝 고민해봐도 모르겠다면 가장 긴 증가하는 부분 수열 해당 문제를 한번 보고 오자. 만일 보고 왔다면 아마도 감이 왔을것이다. 그래도 모르겠다면 이런식으로 생각해보자. 증가하는 부분 수열이라는 말은 반대로 말하면 해당 부분들을 제외하고 움직이..

[문제] https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [문제풀이] 유명한 백트래킹 응용문제 n 퀸인데 기존에 백트래킹을 많이 풀어봤다면 충분히 풀 수 있을만한 문제다. 체스판에서 N만큼 퀸이 존재하는 경우를 요구하는 문제인데 체스판에 퀸이 N만큼 존재할려면 모든 줄에 퀸이 1개씩은 존재해야 한다. 다만, 이미 방문했던 위치를 true나 false로 둘 경우 다시 원상복귀할때 원하지 않는 부분까지 반환을 해주는 경우가 생기기에 2중배열 visit을 int로 ..