코딩 연습장

오랜만의 글 이네요. 백준 5549번 - 행성 탐사입니다. https://www.acmicpc.net/problem/5549 전형적인 구간합 문제 입니다. N x M 크기의 행성의 지도와, 조사 대상 영역 K개 각각의 양 끝 좌표가 주어집니다. 행성을 한 번 탐사하기 위해 걸리는 시간은 O(NM), 즉 모든 K에 대해 재탐사를 수행한다면 시간 복잡도는 O(KNM)이 됩니다. 따라서 탐사는 재탐사는 불가능합니다. 한 번의 탐사 결과를 기억해서 재활용합시다. 간단하게 (1, 1)부터 시작해서 (X, Y)까지 탐사 결과를 dp[ X ][ Y ]에 저장합니다. 이제 (X1, Y1)부터 (X2, Y2),까지의 탐사 결과는 구간합(prefix-sum)을 이용하여 쉽게 구할 수 있습니다. 위와 같이 N x M이 4구..

백준 1325번 - 효율적인 해킹입니다. https://www.acmicpc.net/problem/1325 학부 과제로 비슷한 유형의 문제를 풀어본 적이 있어 금방 해결하였습니다. 연결된 네트워크상에서 컴퓨터를 해킹할 수 있는 개수를 찾는 문제입니다. 예제 입력1을 그림으로 표현하면 이와 같습니다. 화살표는 신뢰받고있는 관계, 즉, 해킹할 수 있는 방향을 의미합니다. 이 경우에는 1 혹은 2를 해킹하면 네트워크 상의 모든 컴퓨터를 해킹할 수 있습니다. 간단하게 해결하기 위해 인접리스트를 사용합니다. 인접리스트는 그래프의 연결관계를 리스트로 표현한 것입니다. 인접 리스트는 주로 인접 행렬과 비교되는데, 노드가 N개, 간선이 E개라고 했을 때, 연결된 모든 노드를 방문하기 위해 인접 행렬은 행렬의 모든 값을..

백준 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칸 중에 가장 작은 값을 찾아서..