Bloooooooog

프로그래머스 코딩 테스트 연습 문제 - 광물 캐기 / JAVA 풀이 정리 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 광물을 5개 단위로 묶고, 묶음마다 대해 돌을 가장 효율적으로 캘 수 있는 곡괭이를 선택한다. 돌을 가장 많이 캘 수 있는 곡괭이부터 사용하여 광물을 캐고, 해당 곡괭이의 사용 횟수를 감소시킨다. 위 과정을 곡괭이 사용 횟수를 소진할 때까지 반복한다. (광물이 5개 단위인 이유 : 한 번 곡괭이를 사용하면 소진될 ..

동적 계획법(Dynamic Programming)이란? 큰 문제를 여러 개의 부분 문제로 나누어 이를 해결하고, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 문제해결방법이다. ■ 분할 · 정복(Divide & Conquer) 알고리즘이랑 비슷한데? 큰 문제를 여러 부분 문제로 나눈다는 점에서 분할 정복 알고리즘과 유사하다. 하지만, 이 두 방법 간에 가장 큰 차이점은 부분 문제의 중복 여부이다. 분할 · 정복 알고리즘은 부분 문제들 간에 중복이 없고 각각의 부분 문제는 독립적이지만, 동적 계획법에서 부분 문제 간에 중복이 존재하고, 해결한 부분 문제의 정답을 저장(Memoization)해 두었다 재활용해 문제를 해결한다. 동적 계획법의 사용 조건 1. 중복된 부분 문제 (Overlapping ..

이진 탐색(Binary Search)이란? 우리가 종종 하는 업다운(Up & Down) 게임과 매우 유사한 검색 알고리즘이다. 리스트의 중간값을 선택해, 그 값이 목푯값인지, 아니면 앞에 있는지, 뒤에 있는지를 판단하고 목푯값을 찾을 때까지 이를 반복하는 알고리즘이다. 이진 탐색의 장 · 단점 매 탐색마다 범위의 절반을 덜어낼 수 있어 속도가 빠르고, 알고리즘의 구현도 비교적 간편하다. 다만, 특성상 정렬된 데이터에만 적용할 수 있기 때문에 정렬 작업이 선행되어야 한다.