곧죽어도 콛잉

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 1) 빈도수를 저장해야하므로 맵 자료구조를 사용한다. 이때, 맵 자료구조를 하나 더 사용하여 나온 순서도 저장한다. 2) 저장된 맵 자료구조를 정렬해야하므로 vector에 저장해준다. 3) 빈도수 정렬의 규칙에 따라 cmp 함수를 설정하고 sort를 진행한다. 4) vector를 출력한다. 우선 해당 수 : 빈도 수 가 필요하다는 것은 바로 알아차렸을 것이다. 그렇다면 바로 써줘야하는 자료구조는 바로 map이다!!! map을 이용하면 매우..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1) 재귀함수 q(x, y, n)를 설정한다. - 종료조건 : n==1 이 되면 x,y에 해당하는 숫자를 push_back 해준다. - 반복 : x, y부터 x+n,y+n까지 탐색을 시작한다. 만약 x,y에 해당하는 숫자와 다른 숫자가 나온다면, q를 호출하여 4번을 재귀적으로 돌린다. 추가로, 여는 괄호 '(' 를 push_back 해준다. 4번의 재귀가 끝난다면, 닫는 괄호 ')'..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 1) psum이라는 누적합 배열을 만든다. 2) 누적합 배열을 이용해 각 K일씩의 합을 구한다. 3) 동시에, max 함수로 최대값을 구한다. 문제를 읽으면 이해하는 건 어렵지 않다. 하지만 이걸 그냥 문제 나온 그대로 코딩하면 백퍼센트 오버플로우 혹은 타임 아웃이다.. 이 문제는 누적합을 이용하는 문제이다. psum[n]이라는 배열을 1일차부터 n일차까지의 합이라고 해보자, 그렇다면..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 새로운 주제인 백트래킹이다. 재귀를 응용해서 경우의 수를 찾을 수 있다. 문제를 읽어보면 부분집합들의 합을 찾아내야한다. 주어진 1) 수열의 부분집합을 찾고 2)그 부분집합의 합을 구해내는 것이 핵심이다. 그러나 대게 막연할 것이다. 따라서 다음과 같이 그림으로 도식화해보자. 그림을 보며 생각해보자. 위의 그림은 제시된 수열이 {1,2,3}일때를 가정했다. 우선..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 이것 역시 앞의 문제들과 유사하게 풀면된다. 반복되는 모양을 캐치해서 이를 어떻게 구현할지가 키포인트 같다! 나는 단순하게 2차원 배열을 통해 모양이 시작되는 각 좌표를 재귀함수가 호출될때마다 넘겨주었다. 위의 패턴들의 느낌을 봐보자. 사각형을 9개의 사각형으로 나눠야할 거 같지 않은가? 근데 또 각각의 사각형은 또 9개의 사각형을 나눠지고 ... 이게 계속해서 반복된다..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 앞서한 종이의 개수와 논리와 완전히 똑같다! 이건 BOJ 1760 종이의 개수보다 훨씬 쉬운문제다! 1) 하나의 숫자로(0, 1) 채워져있는지 확인하고, 1-1) 만약 채워졌다면, 그 숫자를 확인한 후 개수를 세준다. 1-2) 만약 안채워졌다면, 사각형을 4등분한 후 각 사각형마다 다시 1) 과정을 반복한다. 토씨하나 틀리지 않다... 실제로 코드도 논리도 거의 똑같다...