728x90 개발일기89 [알고리즘] DP? 다이나믹 프로그래밍 DP란 다이나믹 프로그래밍(Dynamic Programming) 또는 동적 계획법이라고 불리는 알고리즘이다. 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 해결할 때 사용한다. 저장? 한 번 계산한 문제는 다시 계산하지 않도록 예시로 피보나치 수열을 들 수 있다. 피보나치 수 의 점화식은 f(n) = f(n-1) + f(n-2) f(n-1)와 f(n-2)를 각각 따로 구하게 되면 f(n-2) 만큼 중복된 계산이 있을 것이다. 그래서 f(n-2)까지의 계산 결과를 저장한 후 f(n-1)를 구하기 위해 f(n-2), f(n-3)을 꺼내 계산하고 최종적으로 f(n)을 구하기 위해 f(n-1), f(n-2)을 꺼내 계산하는 것 DP는 2가지 방식으로 구현할 수 있다. Bottom-Up (반복문).. 2023. 7. 16. [프로그래머스] 개인정보 수집 유효기간 - 자바 split 함수 우선 오늘 날짜를 "." 기준으로 나눠주었다. split 함수의 인자는 정규표현식 (Regex) 패턴이다. 정규식에서 .은 임의의 한 글자를 나타낸다. "."으로 분할하면 모든 문자와 일치하므로 배열에 아무것도 남지 않게 된다. today.split("."); // 빈 배열 "." 문자 그 자체로 분할하려면 이스케이프 문자인 "\\."를 사용해야 한다. 또는 "[.]" 와 같이 대괄호로 감싸면 문자 그 자체로 인식한다. // "."으로 분리하기 둘 다 사용 가능 today.split("\\."); today.split("[.]"); 이것은 String 배열로 반환되는데 계산이 쉽도록 변환하여 int 배열에 넣어줄 것이다. // stream : 배열을 더 편리하게 가공하고 처리하도록 해주는.. 2023. 7. 12. [프로그래머스] 뒤에 있는 큰 수 찾기 - 자바 다른 사람들과 마찬가지로 for문 2개를 사용했더니 뒤에 4개는 시간초과로 실패ㅜ 문제의 핵심은 stack으로 접근..! numbers 배열의 뒤에서부터 접근하여 stack에 쌓고 해당 수와 비교하여 삭제하고 반복하면 된다. stack은 후입선출 방식으로 한쪽 끝에서만 데이터를 삽입하고 삭제 → 즉 뒤의 숫자들의 가까운 순으로 비교할 수 있음 peek() 최근에 추가된 맨 뒤에 있는 데이터를 반환 pop() 최근에 추가된 맨 뒤에 있는 데이터를 삭제 push() 데이터 추가 예시 1 numbers = [2, 3, 3, 5] answer = [ , , , ] stack = [ ] index = 3 numbers = [2, 3, 3, 5] stack이 비어있는지 확인(비어있음) → answer의 해당 배열에.. 2023. 7. 1. [프로그래머스] 귤 고르기 - 자바 크기가 여러개인 귤 중 k개 만큼의 귤을 골라야 하는데 크기가 서로 다른 종류의 수를 최소로 하고 싶다는 문제 처음에는 무슨 말인가.... 했는데 예시를 보면 이해가 잘 된다. k = 6 tangerine = [1, 3, 2, 5, 4, 5, 2, 3] 표로 정리해 보면 크기 개수 1 1 2 2 3 2 4 1 5 2 이 중 6개를 고르려면 개수가 2개인 2, 3, 5 크기를 고르면 될 것이다. 그래서 답이 3인 것 이것은 크기 보다 개수가 중요한 것~! 그래서 우선은 개수를 알기 위해 크기별 개수를 먼저 구해주었다. 로 저장할 HashMap을 만들어 준 후 tangerine 배열에서 가져온 귤 크기를 key로 검색한 value를 +1 해서 저장 (물론 없을 수도 있으니 없으면 0으로 검색) HashMap.. 2023. 6. 30. 이전 1 2 3 4 5 6 7 ··· 23 다음 728x90
