코딩 연습장

백준 6603번 - 로또입니다. https://www.acmicpc.net/problem/1325 무난한 난이도의 문제입니다. 집합 S에서 6개의 숫자를 선택하는 문제입니다. 집합 S에서 추출할 수 있는 숫자를 찾아가면서 재귀호출 합니다. 이때 재귀의 깊이 = 추출한 숫자의 수 입니다. 집합 S에서 추출 가능여부를 확인하기 위해 S와 같은 크기의 추출 가능여부 확인용 bool 컨테이너, 출력하기 위해 추출 결과 6개를 담고 있는 추출 결과 컨테이너도 함께 넘겨줍니다. 집합 S 이외에는 반드시 복사하여 넘겨주어야합니다. 깊이가 깊어질 때마다 조합의 원소의 개수가 한 개씩 늘어납니다. 집합 S에서 마지막으로 추가한 원소보다 더 뒤에 있는 원소를 모두 추출하고(재귀호출) 마지막 깊이에서 완성된 조합을 출력하게..

백준 1596번 - 영식함수입니다. https://www.acmicpc.net/problem/1596 간단해 보이는 문제입니다. 아마도. 영식함수(N)의 결과가 7인 개수를 세는 문제입니다. 입력 9121에 대해서 이런 과정을 거쳐서 지문을 출력합니다. 붙어있는 두 자리의 차이(9와 1, 1과 2, 2와 1)로 이루어진 수열이 새로운 영식함수의 대상이 되고, 만약 한 자릿수만 남게 되면 이를 출력해줍니다. 7 18 29 70 81 92 예를 들어서 1부터 100 사이에 있는 행운의 수는 이처럼 6개입니다. 어떤 수 X에 대해서 영식함수를 거쳐서 지문이 7인 수 X의 개수를 세면 되는 간단한 문제입니다 라고 생각했으나. 입력 크기가 10억이니 시간 복잡도는 O(N) 미만으로 풀어야겠네요. 문제를 대충 골랐..

백준 1915번 - 가장 큰 정사각형입니다. https://www.acmicpc.net/problem/1915 알고리즘 스터디에서 풀었는데, 반례를 못 찾아서 상당히 고전했습니다. 0과 1로 구성된 n x m 사이즈의 배열중에서 1로만 이루어진 가장 큰 정사각형을 찾는 문제입니다. 예를 들어 위와 같은 배열이 주어졌다면 이 배열에서 가장 큰 크기의 정사각형의 크기는 3x3입니다. 주어진 배열을 탐색하면서 정사각형을 찾으면 되겠네요. 1x1 크기의 정사각형을 찾으려면 어떻게 해야 할까요? → 한 개의 1을 찾으면 됩니다. 그럼, 2x2 크기의 정사각형을 찾으려면 어떻게 해야 할까요? 2x2 크기의 빨간 사각형 안에 있는 모든 값이 1이면 됩니다. 간단하게 시각화 해봅시다. 4칸 중에 가장 작은 값을 찾아서..