akaSonny

본 문제는 에서 가져왔습니다. 문제 풀이 먼저, 두 개의 문자열을 비교하는 것이기 때문에 dp 테이블을 2차원으로 만들어야한다. dp[i][j] --> A의 i번째까지의 문자열을 B의 j번째까지의 문자열로 바꿀 때의 편집 거리 간단하게, 예시에 나오는 "cat" 과 "cut" 으로 dp 테이블을 만들면 다음과 같다. c u t c 0 1 2 a 1 1 2 t 2 2 1 (1, 1): "c"에서 "c"로 갈 때 필요한 연산 수 = 0 (1, 2): "c"에서 "cu"로 갈 때 필요한 연산 수 = 1 (1, 3): "c"에서 "cut"로 갈 때 필요한 연산 수 = 2 (2, 1): "ca"에서 "c"로 갈 때 필요한 연산 수 = 1 ... (3, 3): "cat"에서 "cut"로 갈 때 필요한 연산수 = 1..

본 문제는 에 수록되어 있습니다. 문제 풀이 일단 이 문제는 다이나믹 프로그래밍 챕터에 수록되어 있는 문제이다. 다이나믹 프로그래밍을 할 때 가장 먼저 생각해야되고 결국 핵심적인게 점화식을 구해야되는건데 ... 나의 머리는 잘 돌아가지 않는다 흑... 제일 먼저 못생긴 수를 저장할 dp테이블을 만든다. 못생긴 수는 2, 3, 5만을 약수로 가져야하므로 dp 테이블 내에 있는 숫자들에 계속해서 2, 3, 5를 곱해야되는 아이디어를 가지고 시작했다. 그리고 작은 수부터 dp 테이블에 저장해야 되는데.. 이 부분이 너무 어려웠다 ㅠㅠ 그래서 해설의 도움을 약간 (?) 받은 풀이 .. 사실 두 번째 푸는건데도 아직도 제자리걸음이다 에흉흉 ㅠㅠ dp = [0] * 1001 n = int(input()) dp[1]..

본문은 '이것이 코딩테스트다' 책(나동빈 저, 한빛미디어)을 참고하며 작성하였습니다. 파이썬 다익스트라 (Dijkstra) 알고리즘 (혹은 데이크스트라 알고리즘) : 그래프에서 한 정점에서 다른 여러 개의 정점들 간의 최단 경로를 찾는 알고리즘 (그리디 알고리즘으로도 분류된다. - 가장 비용이 적게 드는 정점을 선택해서 과정을 반복하기 때문) 이러한 그래프가 있을 때 1번에서 다른 정점으로 가는 최단 경로를 모두 구해보는 문제를 생각했을 때, 초기화 - 모든 거리를 무한대로 설정한다. (파이썬에서는 통상적으로 1e9 사용) --> 2 (무한) , 3 (무한), 4 (무한), 5 (무한), 6 (무한) 1번에서 갈 수 있는 정점들 확인 후 비용 계산 후 최소값으로 갱신 --> 2 (2) , 3 (5), 4..

위의 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 (7) 부터 시작하여 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 작성. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 오른쪽에 있는 것 중 하나만 선택 가능. 삼각형의 크기는 1 이상 500이하, 각 정수들의 범위는 0 이상 9999 이하 입력 조건 : 첫째 줄에 삼각형의 크기 n이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 조건 : 합이 최대가 되는 경로에 있는 수의 합 출력 이 부분 챕터를 푸는 중이라 그런지 문제 보자마자 푸는 방법을 깨달아서 뿌듯했당 .. ㅎㅋ 먼저, 계산한 값들을 저장할 새로운 배열을 만들어야 한..

피보나치 수열 : $a_{n+2} = a_{n+1} + a_n$, $a_1=1, a_2=1$ 1. 재귀함수 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) 원래는 피보나치 수열은 이렇게 재귀함수로 표현하는게 국룰인 줄 알았다,, 그런데 이렇게 하면 시간 복잡도가 $O(2^N)$으로 N이 늘어나면 연산량이 지수적으로 늘어난다. 따라서 연산량을 줄일 수 있는 다른 방법 필요 다음 소개할 코드는 메모이제이션 (Memoization) 기법을 사용한다. 한 번 구현한 결과를 메모리 공간에 메모해두고 호출하여, 반복된 연산을 피하는 방법 2. 재귀함수2 d = [0] * 100 def fibo(x): if x == 1 or x == 2..

코딩테스트 스터디를 하면서 이번에 공부하게 된 이진 탐색에 대해 정리하려고 한다. 개념 자체는 엄청 간단하고 bisect라는 모듈이 있기 때문에 직접 구현하지 않아도 된다. 하지만 나는 몰라서 직접 구현했지.. 후후... 아래의 개념 포스팅은 책을 참고하였습니다. (책 구매 링크) 1. 순차 탐색 말 그대로 우리가 찾고자 하는 대상을 앞에서부터 하나씩 순차적으로 확인하는 방법 시간만 충분하다면 무조건! 찾을 수 있음 우리가 알고 있는 for문, count 메서드 등이 여기에 해당 시간 복잡도는 O(N) , 즉 N이 엄청 커지면 엄청 오래 걸린다는 단점 .. 2. 이진 탐색 이진 탐색을 하기 위해서는 시작점, 끝점, 중간점이 필요 → 찾으려는 대상과 중간점을 비교해가며 탐색하는 방법 중간점과 비교하기 때문..