반응형 SWE/코테137 Edit Distance - 최소 편집 횟수 구하기 / DP 최소 편집 (Edit Distacne) 문제 개념 String s1, s2 가 주어졌을 때, s1을 s2로 변화시킬 때 필요한 최소 편집 횟수를 구하는 문제이다. s1에 적용할 수 있는 연산은 총 4가지가 있으며 아래와 같다. 1. COPY : s1의 값을 그대로 유지함. -> edit distance : 02. INSERT : s1의 한 위치에 문자를 하나 삽입한다. -> edit distance : 13. DELETE : s1의 문자 하나를 삭제한다. -> edit distance : 14. SUBSTITUTE : s1의 문자 하나를 다른 문자로 교체한다. -> edit distance : 1 예를 들어, s1 = "strong" s2 ="storm" 일 때의 edit distance는 3이다.COP.. 2018. 10. 29. [성실코딩 12일차] 백준 #15486 퇴사 2 / DP 14501 퇴사랑 같은 문제인데 퇴사하려는 일 N+1이 15 -> 1,500,000 으로 증가하였다. 시간 초과될까봐 너무 걱정했음 ㅜㅜ !시간 초과 걱정되서 수정한 부분! DP 1차원 배열 채울 때, 시간초과 날까봐 걱정되서 수정한 부분은 이전 코드에서는, DP[i] = i에 잡혀있는 상담을 했을 때의 최대금액 현재 코드에서는, DP[i] = i에 잡혀있는 상담을 했을 때의 최대금액과 DP[i+1~N] 중에 최대금액 차이점은 i에 잡혀있는 상담을 했을 때의 금액을 계산하고, 그 이후 날짜중 최대금액을 찾기위해 i+1~ N까지 검사했어야했지만 지금은 DP[i+1]에 값하고만 비교하면됨. 반복문을 한차례 없앨 수 있음 그리고 이전 코드에서의 정답은 DP를 다 채운 후에, DP에서 for문 돌아서 DP[i].. 2018. 10. 26. [성실코딩 12일차] 백준 #11052 카드 구매하기 / DP 예제 입력이 아래와 같을 때, 문제풀이 10 1 1 2 3 5 8 13 21 34 55 구현 코드 #include #include #include using namespace std; int n; // 카드 개수 int arr[1001]; vector DP; void populateDP() { // 첫번째 행 - 카드 1개 들어있는 카드팩 for (int j = 1; j 2018. 10. 26. [성실코딩 12일차] 백준 #10942 팰린드롬? / DP 문제는 쉬운데 정답률이 왜 낮은가 했더니 c++ 표준 입출력에 대한 시간초과 때문이었음! 입출력 속도향상 방법 1. cin, cout -> scanf, printf 사용하기 2. endl -> \n(개행문자) 사용하기 3. cin, cout을 사용하고 싶다면, 아래 적용하기! 대신 scanf, printf, puts, getchar, putchar 등 c의 입출력 방식을 공용해서 사용하지 못함. ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL): 문제풀이 방법1. 완전탐색 -> 처음에 생각한 방법. 당연히 시간 초과날 것 같음. 처음 주어지는 값은 SE가 될 때까지 두 수가 같아진다면 그 수는 팰린드롬이다. (수도코드) while(arr.. 2018. 10. 26. 이전 1 ··· 19 20 21 22 23 24 25 ··· 35 다음 반응형
