본문 바로가기

분류 전체보기23

[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.
[체인지업] 7-8시즌 참여 후기 체인지업이 뭐냐면... 면접왕 이형님의 얼라이브커뮤니티에서 운영하는 취업 캠프다. 1대1 코칭인가 했지만, 취업 준비를 구조화하여 가이드라인으로 제공하는 취업 캠프였다. 추가로, 500여명이 넘는 사람들이 모여있어 자율적으로 4~5인 스터디를 구성할 수 있다. 하면서 바뀐 점 나의 경험을 전달하는 방법을 구체적으로 알게 되었다. 3C4P라는 어디에나 적용할 수 있는 구조화 방법부터, 이를 자소서와 면접까지 연결시키는 방법. 그리고 경신스(경제신문스크랩)를 시작으로 하루를 시작하는 아침 루틴까지 생겼다. 사람들과 스터디를 하면서도 나 혼자서는 발견하기 어려웠던 약점들을 찾을 수 있어서 도움이 많이 되었다. 일단 나가서 사람들 만나기라도 해야겠다는 생각으로 돌아다녔던 것이 좋게 돌아온 것 같다. 아쉬웠던 점.. 2023. 8. 19.
[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.

티스토리툴바