문제 www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 풀이 n = 1000이며, 시간 제한이 1초이므로 대략 O(n^2)시간의 알고리즘을 설계하면 해결할 수 있는 문제다. dp테이블은 입력으로 주어진 수열과 동일하게 초기화시킨다. i가 인덱스 0부터 n-1까지 순회하고, j는 인덱스 0부터 i-1까지 순회한다. 이 과정에서 수열[i]와 수열[j]를 비교하고, 수열[i]가 더 크다면 현재 dp[i]와 ..
문제 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 방향, 전진, 후진에 대한 정보를 딕셔너리에 담아둔다. 여기서 방향이라 함은 왼쪽으로 회전후에 어떠한 방향을 취하게 되는지에 대한 정보를 의미한다. e.g. 북(0) -> 서(3), 동(1) -> 북(0), 남(2) -> 동(1), 서(3) -> 남(2) 1번부터 진행할 지, 2번부터 진행할 지에 대한 여부는 함수의 매개변수로 전달한다. 4방향을 탐색(2-b)하면서 청소를 할 지(2-a) 결정한다...
문제 www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 풀이 소수와 관련된 문제는 앞서 풀어본 적이 있다. 이 문제는 주어진 짝수에 대해 골드바흐 파티션을 얼마나 빨리 구할 수 있는지가 관건이다. 골드바흐 파티션 함수는 두 개의 포인터로 구현할 수 있다. 각 포인터는 초기에 중간지점(mid)에 맞춰져있고, 소수를 가르킬 때까지 이동한다. 두 포인터가 소수를 가르키게 되면 검사를 하고 해당 소수의 합이 n인지 확인한다. 맞다면 골드바흐 파티션..
문제 www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 두 가지 방법으로 풀 수 있다. 1. 별을 9개의 공간으로 나눈뒤 1번 공간의 별이 5번 공간을 제외한 나머지 공간의 별에 똑같이 복사한다. 2. 1번 풀이에 비해 좀 더 직관적이며 속도가 빠르다. 공간을 1, 2, 3으로 나눈 후 재귀함수를 통해 구해진 별을 붙인다(append). 코드 1번 풀이 import sys sys.setrecursionlimit(10**6) de..
문제 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 입력부에서 가장 높은 지역의 높이(MAX)를 저장한다. 그 후 강수량을 1부터 MAX-1까지 정해서 DFS를 진행한다. 이때, 강수량보다 높은 지역에 한해서만 탐색을 진행하고, 탐색이 끝나면 비교를 통해 안전 영역의 최댓값을 구한다(비가 안 오는 경우도 존재하므로 최댓값은 1이상이다). 코드 import sys sys.setrecursionlimit(10**9) def dfs(y, x, r): visited..
