wooing

문제https://softeer.ai/practice/7649 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 해결방법해당 문제는 DFS로 그래프 순환 및 LCS구현을 통해 해결할 수 있는 문제이다. DFS는 인접리스트를 순회하는 방법으로 쉽게 구현 가능하다. 그러나 LCS를 기본 LCS로 구현하면 O(N^3)의 시간복잡도를 가지기때문에 시간초과가 발생한다.우선 LCS의 일반적인 코드는 아래와 같다. for (int i = 1; i  위와같이 구현하게되면, 이미 구해진 LCS값을 매번 초기화하게되어 시간초과가 발생한다. 이를 해결하기위해 dp배열을 재활용하는 방식으로 LCS를 구한다. 재활용 하는 방법은 아래와 같다. 해당 방법으로 구현하면 O(N^2)로 시간초과를 해결할 수 있다..

문제https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai해결방법해당 문제는 DP문제로 점화식을 세우는것이 중요한 문제이다. 내가 생각한 점화식은 다음과 같다.현재 높이보다 낮은 칸들의 최대값 + 1문제를 풀고 다른 사람들의 풀이법을 보니 나와 조금 달랐다. 다른 사람들은 이 문제를 최장증가부분수열 해결 방법으로, dp[]에 해당 칸을 밟았을때와 안 밟았을때의 max값을 저장하는 방식으로 dp를 구현하였다. 그리고 내 해결방법의 오류나 단점을 생각해보면 다음과 같다.메모리 문제실제로 입력조건에 맞춰 int[100000001]로 배열을 선언하였더니 메모리초과가 발생하여 Map으로 변경하였다.시간복잡도다른 사람들의 풀이는 O(N)이지만..

문제https://softeer.ai/practice/11001 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 해결방법이 문제를 해결하기 위한 포인트는 배열 정렬하는 Comparator구현이다. 입력받은 값을 String[]로 저장하고, Arrays.sort메소드와 Comparator람다 함수를 직접 정의하여 쉽게 해결 가능하다.Comparator람다 함수 내부에는 다음과 같은 과정을 구현하면 된다. 소수점 기준으로 좌우 숫자 분리좌측 숫자 비교우측 숫자 유무 확인우측 숫자 비교이때 소수점 좌우 분리 과정에서 .split("")메소드 안의 정규식에 주의해야한다. 정규식에서 "."은 모든값을 의미하기때문에 원하는 결과를 얻을 수 없다. "."대신 "\\."으로 입력하여야한다.소스코드..

문제https://softeer.ai/practice/11002 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 해결방법해당 문제에서 중요한 부분은 2가지이다. 첫번째는 CPTI 지표 비교하는 방법, 두번째는 리스트 순회 방법을 고려해야한다. CPTI 비교하는방법CPTI는 2진법의 문자열로 입력된다. 2자리 이하로 지표가 다른 경우를 찾는것이므로 XOR연산과 비트 카운트를 통해 쉽게 해결이 가능하다.리스트 순회문제에서 주어진 조건에 따르면 O(NlogN)의 시간복잡도까지 가능하다. 그러므로 모든 경우를 조회하기 위해 N번씩 2중 반복문으로 해결할 수 없다. 그러므로 2중 반복문에서 반복 횟수를 줄이는 로직이 필요하다. 내가 해결한 방법은, 0..N까지의 이중 반복문을 사용했을때 같은..