개발, 프로그래밍8 [BOJ 9252] LCS 2 (Java) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 생각한 접근법 DP문제는 정확한 점화식을 두고, 어느 값을 메모리에 저장하는지가 핵심이라 생각했다. 그래서 이번 문제는, 1번 문자열을 두고, 2번 문자열의 문자들을 하나씩 확인하면서 LCS를 기록/갱신해야 겠다고 생각했다. 따라서 2가지 값을 저장하기로 했다. int 배열 lcsLen: 1번 문자열의 i번째 문자를 마지막 문자로 가지는 LCS(이하 Part LPS라 명명)의 최대 길이. String 배열 lcs:.. 2023. 8. 24. [BOJ 2098] 외판원 순회 (Java) 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 생각한 접근법 처음에는 완전탐색으로 시간복잡도 O(N!)을 확인하고, DP로 접근해야 할 것 같다는 막연한 생각만 있었다. 1시간정도 고민 후 TPS 알고리즘에 대해 찾아봤다. 이후 DPS에 DP를 섞으면 가능하다는 것을 알았다. 또한 방문했다는 변수를 boolean 배열이 아닌 비트마스크로 처리하는 방법을 배워 적용했다. 점화식은 아래와 같다. cost[현재위치][현재상태] = min{ cost[다음위치][다음상태] + W.. 2023. 8. 21. [BOJ 5582] 공통 부분 문자열 (Java) 문제 확인하기: 더보기 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABR.. 2023. 8. 14. 프론트엔드 테스트와 종류 테코톡 영상을 보고 정리한 내용이다. 프론트엔드 테스트란? 프론트엔드 테스트는 UI 혹은 GUI가 의도대로 작동하는지 확인하는 과정이다. 버튼을 눌렀을 때 의도한 이벤트가 올바르게 발생하는지, 입력란에 문자를 입력하는 제한사항이 적절한지 등을 확인할 수 있다. 이러한 테스트는 반복적이고 심지어는 복잡한데, 컴퓨터가 이런건 사람보다 잘하므로 유용하다고 할 수 있다. 테스트를 볼 때 "이런 기능을 테스트한다" 라고 생각하기 보다는, "이런 기능이 필요하다"라는 개념으로 생각하는 것이 좋다. 맨날 콘솔로그 찍고 출력하면서 번거롭게 디버깅하는 것보다, 테스팅을 활용하는 것이 더욱 편하고 좋을 것 같다. 프론트엔드 테스트 종류 (7가지) 대략 7가지 종류의 테스트가 존재한다. 1) 정적 테스트 (Static te.. 2023. 7. 17. 이전 1 2 다음
