[이코테] 편집 거리 https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 문제 설명 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만..

2021. 2. 26.

알고리즘

[BOJ/백준] 1463번 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 n = int(input()) d = [0] * (n+1) d[0] = 0 d[1] = 0 for i in range(2,n+1): if n == 0 : continue #현재의 수에서 1을 빼는 경우 d[i] = d[i -1] +1 if i % 3 == 0: # 3으..

2020. 11. 26.

알고리즘

[이코테] 다이나믹 프로그래밍(Dynamic Programming) 중복되는 연산 줄이기 탑다운 보텀업 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. ex) 1 1 2 3 5 8 13 21 34 55 89... 수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. #재귀 함수를 이용한 피보나치 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1)+fibo(x-2) print(fibo(4)) 하지만 피보나치 수열의 코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 f(n)에 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이러한 문제는 다이나믹 프로..

2020. 11. 24.

알고리즘