![]()
이 문제는 최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤, 최소 편집거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다. 점화식은 다음과 같다. 두 문자가 같은 경우: dp[i][j] = dp[i-1][j-1] 행과 열에 해당하는 문자가 서로 같다면 왼쪽 위에 해당하는 수를 그대로 대입 두 문자가 다른 경우: dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중에서 가장 작은 수에 1을 더해 대입 만약 문자열 A의 i번째 문자와 문자열 B의 j번째 문자가 같은 경우 - 두 문자가 같다면 연산이 필요하지 않으므로 dp[i-1][j-1]의..
못생긴 수 = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.....] 2, 3, 5만 인수로 가지는 합성수(1포함) 못생긴 수에 2, 3, 5를 곱한 수도 못생긴 수다. 2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대해 각각 '가장 작은 못생긴 수'부터 오름차순으로 하나씩 확인하면서, 각 배수를 곱한 값도 '못생긴 수'가 될 수 있도록 처리하면 된다. 풀이 코드 # 못생긴 수 n = int(input()) ugly = [0] * n # 못생긴 수를 담기 위한 테이블(1차원 dp 테이블) ugly[0] = 1 # 첫번째 못생긴 수는 1 # 2배, 3배, 5배를 위한 인덱스 i2 = i3 = i5 = 0 # 처음에 곱셈값을 초기화 next2, next3, next5 = 2, 3,..
18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 문제다. 점화식을 생각해내지 못해서 풀지 못했다. 풀이 코드 # 18353번: 병사 배치하기 n = int(input()) # 병사의 수 arr = list(map(int, input().split())) # 전투력 arr.reverse() dp = [1] * n # dp 테이블 # 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행 for i in range(1, len(arr)): for j in range(i): if arr[i] > arr[..
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net DP 문제다. 상담을 진행했을 때, 받을 수 있는 최대 이익을 출력하면 되는 문제. 처음에 그냥 떠오른 점화식은 다음과 같다. time와 price 리스트가 있을 때, dp[i+time[i]] = max(dp[i] + price[i], dp[i+time[i]) 이런 식으로 점화식을 만들어주면, 답이 나오는 것 같았다. 물론 돌려보니 실패했다. 반례를 찾다보니, 통과하지 못하는 반례르 발견했다. 4 3 1 1 100 2 100 1 1000 이 반례의 정답은 1100인데 1001이라는 잘못된 답을 뱉어냈다. dp테이블을 손수 직접 돌아보면서, 잘못된 점을 찾았고, 새로운 점화식을 만들었다. dp[i+ti..
1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 31번 문제와 거의 비슷한 문제. DP 테이블을 2차원 리스트로 설정해서 DP 테이블 갱신을 통해 최댓값을 구해주면 된다. 내 풀이 코드 # 1932번: 정수 삼각형 n = int(input()) # 삼각형의 크기 graph = [] # 삼각형을 이루고 있는 수를 저장하는 리스트 for _ in range(n): data = list(map(int, input().split())) graph.append(data) # dp 테이블 dp = [[0] * n for _ in range(n)] # 점화식을 통해 dp 테이블 갱신 for i..
DP 문제다. 이 문제의 경우, DP 테이블을 2차원 테이블로 만들어서 해결할 수 있다. 금광의 모든 위치에 대해, 1. 왼쪽 위에서 오는 경우 2. 왼쪽에서 오는 경우 3. 왼쪽 아래에서 오는 경우 이 3가지만 존재하므로, 3가지 중 가장 많은 금을 가지고 있는 경우를 테이블에 저장해 문제를 해결한다. 점화식은 다음과 같다. dp[i][j] = max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]) + graph[i][j] 단, 맨 위 혹은 맨 아래 금광인 경우, 배열의 범위를 벗어날 수 있으므로 조건문을 통해 다른 점화식을 적용해줬다. 내 풀이 코드 # 금광 t = int(input()) # 테스트 케이스 개수 def gold(): n, m = map(int, input().s..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이진 탐색 문제. 아무리 생각해봐도 어떻게 이진 탐색을 돌아야 될지 모르겠어서 풀이를 봤다. 풀이 코드 # 가사 검색 from bisect import bisect_left, bisect_right # 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수 def count_by_range(arr, left_value, right_value): right_index = bisect_right(arr, right_value) left_index = bisect_left(arr, le..
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제는 N개의 집 중에, C개의 공유기를 설치하는 문제다. 단, C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 해야 한다. 시간 제한이 2초이고, 집의 좌표는 최대 10억이다. 그러므로 O(N) 시간으로는 불가능할 것이고, O(logN) 시간으로 풀어야 하겠다는 생각이 들었다. 그렇다면 이진 탐색인데, 이진 탐색을 어떻게 돌아야 할까? 그래서 이렇게저렇게 생각을 ..
이진 탐색 문제다. 고정점이란, 수열의 원소중 그 값이 인덱스와 동일한 원소를 의미한다. 이 고정점을 찾는 코드를 구현하라. 단, 수열은 오름차순으로 주어지고, 시간복잡도는 O(logN)이다. 이진 탐색으로 구현하면 된다. 내 풀이 코드 # 고정점 찾기 def find_fix_point(array, start, end): if start > end: return None mid = (start + end) // 2 # 확인할 인덱스 if array[mid] == mid: return mid # 배열의 값이 0보다 작은 경우에는 그 왼쪽 값들은 볼 필요 없다. # 오른쪽 확인 if array[mid] < 0: return find_fix_point(array, mid + 1, end) # 확인할 인덱스의 ..
이 문제는 정렬된 배열에서 특정 수의 개수를 구하는 문제이다. 단 ,이 문제의 시간 복잡도는 O(logN)이다. O(N)이라면 그냥 for문을 돌면서 개수를 구하면 되지만, O(logN)이므로 이진탐색을 통해 구해야 한다. 다행히, 배열이 정렬되어 주어지므로, 따로 주어진 배열을 정렬할 필요 없이, 바로 이진탐색을 진행할 수 있다. 내 풀이 코드 # 정렬된 배열에서 특정 수의 개수 구하기 import sys from bisect import bisect_left, bisect_right input = sys.stdin.readline n, x = map(int, input().split()) arr = list(map(int, input().rstrip().split())) cnt = bisect_rig..
