본문 바로가기
반응형

SWE326

Edit Distance - 최소 편집 방법 추적하기 / DP 최소 편집 (Edit Distance) 문제에서 최소 편집 '횟수'를 구하는 것에서 확장하여 최소 편집 '방법'을 '추적'하는 문제이다. 문제 풀이 최소 편집 횟수를 구하는 table의 [r][c] 위치에서부터 [0][0]을 목적지로 가장 작은 숫자를 타고 올라가면 최적의 방법을 추적할 수 있다. Pseudo Code 1. 3개의 값(좌, 상, 대각선) 중, 가장 작은 값을 찾는다. (1) 가장 작은 값 = up 인 경우, DELETE 연산을 적용했다. (2) 가장 작은 값 = left 인 경우, INSERT 연산을 적용했다. (3) 가장 작은 값 = diagonal인 경우, 3-(1) 그 값이 현재값과 같은 경우, COPY를 적용했다. 3-(2) 그 값이 현재값과 다른 경우, SUBSTITUTE를 적용.. 2018. 10. 29.
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.
[Ubuntu&Windows] 모니터 화면 사이즈에 맞춰서 GUI 크기 설정하기 / full screen 설정 / 시작메뉴 하단 없애기 Java GUI 프로그램을 만들 때, 윈도우즈 OS상에서는 스크린 사이즈를 받아와서 크기 설정이 가능하다.코드. import java.awt.Dimension; // 헤더 private static Dimension dimen; // 전역변수로 선언 dimen = Toolkit.getDefaultToolkit().getScreenSize(); // 모니터 화면 사이즈 받음 setSize((int)dimen.width,(int)dimen.height); // 생성해준 프레임에서 사이즈를 모니터 화면에 맞게 설정해줬음. 결과 화면 그러나 결과사진에서 상단에 파란색으로 표시해놓은 것을 확인하면 title과 종료 버튼을 여전히 확인할 수 있다. 종료버튼과 하단의 시작메뉴 툴을 없애고 완전한 full screen.. 2018. 10. 28.
[성실코딩 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.
반응형

티스토리툴바