♣ DP의 정의 https://jy-deeplearning.tistory.com/65 DP(Dynamic Programming, 백준 알고리즘 14501번) ♣ DP의 의미 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 일반적인 재귀 방식과 DP는 매우 유사함. 하지 jy-deeplearning.tistory.com 지난 포스팅 참고! ♣ 백준 알고리즘 1003번 문제 이해 DP와 재귀함수를 비교하기에 좋은 문제인 피보나치 수를 구하는 문제이다. C++ 함수로 짠 피보나치 함수로, 재귀함수를 이용하여 n번째 피보나치 수를 구하고 있다. 이 문제에서 요구하는 것은 n번재 피보나치 수를 구하는 것이 아니라, fibonacci..

♣ DP의 의미 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 일반적인 재귀 방식과 DP는 매우 유사함. 하지만 일반적인 재귀를 사용할 때 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있음. ♣ DP의 사용 조건 1. Overlapping Subproblems(겹치는 부분 문제가 존재) 2. Optimal Substructure(최적 부분 구조) - Overlapping Subproblems 동일한 작은 문제들이 반복하여 나타나는 경우에 DP를 사용할 수 있음. 즉, 부분 문제의 결과를 저장하여 중복으로 계산할 필요가 없어져야 함. - Optimal Substructure 부분 문제의 최적 결과 값을 ..

♣ 정의 매 선택에서 가장 최적인 답을 선택해서 적합한 결과를 만들자는 의미의 알고리즘 즉 각 부분에서의 최적의 답을 모두 모았을 때 종합적으로도 최적의 결과가 나오는 문제에 적절한 알고리즘. 그리디 알고리즘의 두 가지 특성을 가지는 문제를 푸는 데 적합한 방법임 : 탐욕선택속성, 최적부분구조 서울 - 대구 - 부산 경로로 갈 때 가장 짧게 갈 수 있는 경로를 찾는 문제를 예로 들 수 있음 서울 - 대구의 최적 거리는 200km이고 대구 - 부산의 최적 거리는 80km로 종합적으로 280km를 가는 것이 가장 짧은 경로 1. 탐욕선택속성 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 의미함. 위에서는 서울-대구로 가는 경로 중 가장 적합한 200km를 선택하는 최..

♣ 문제 ♣ 문제 해결 아이디어 여러 가지 숫자와 더하기, 빼기가 섞인 식에서 최솟값을 구하려면 빼기를 최대한 많이 해야 한다. 그러면 처음에 빼기가 나왔을 때 뒤에 더해지는 수들을 최대한 다 묶어서 빼야 한다. 예를 들어 55 - 50 + 40에서 빼기 뒤의 50과 40을 괄호로 묶으면 55 - (50+40)이 되어서 90이라는 큰 수를 뺄 수 있다. 다만 이미 앞에 빼기가 한 번 나와서 뒤의 숫자를 묶기 시작했는데 그 중 빼기가 또 한 번 나오면 그 빼기의 앞에서 괄호를 닫아야 한다. 예를 들어 50 - 5 + 10 + 20 - 30 + 20 이라면 처음에 빼기를 만났을 때 괄호를 열어서 묶기 시작하다가 두 번째 빼기를 만나면 두 번째 빼기 기호 앞에 괄호를 닫아줘야 한다. 그리고 새롭게 괄호를 열어..

♣ 문제 ♣ 문제 풀이 아이디어 이 문제는 리스트의 구간합을 구하는 문제이다. 반복문을 이용해서 특정 구간의 합을 구할 수도 있지만 시간이 오래 걸린다. 구간합 문제는 첫 번째 숫자부터 특정 숫자를 더한 값을 이용하여 해결할 수 있다 . 위의 예시의 경우 5 4 3 2 1 주어진 수를 하나씩 더해서 요소를 구성하면 0 5 9 12 14 15 이다. 첫 번째 숫자 0은 아무것도 더하지 않았을 때, 5는 첫 번째 수인 5만 더했을 때, 두 번째 수인 9는 5와 4를 더했을 때... 이런 식으로 구성된다. 0 = 수를 더하기 전 5 = 첫 번째 수 9 = 첫 번째 수 + 두 번째 수 12 = 첫 번째 수 + 두 번째 수 + 세 번째 수 14 = 첫 번째 수 + 두 번째 수 + 세 번째 수 + 네 번째 수 15..

♣ 팰린드롬: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 ex) 스위스, 기러기, 인도인 등 이미 팰린드롬이 뭔지 알고 있어서 얕봤다가 반례에 큰코 다쳤다. ♣ 팰린드롬의 조건 1. 각각의 문자들이 짝수 개수만큼 있거나 2. 홀수 개수인 문자가 있더라도 딱 한 가지만 있어야 한다. 즉 홀수 개수인 문자가 2개 이상이면 팰린드롬을 만들 수 없다 . ♣ 해결 단계 [주어진 문자열 확인 단계] 주어진 문자열을 받은 후 각 문자열이 몇 개씩 있는지를 딕셔너리로 만듦. 문자는 key값, 문자의 수는 value값으로 지정함 [팰린드롬이 될 수 없는 경우의 수 제거 단계] 딕셔너리의 value값을 values에 넣는다. odd는 value가 홀수인 값의 수를 의미함. 즉 주어진 input에 ..