문제https://school.programmers.co.kr/learn/courses/30/lessons/42897#qna 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이다이나믹 프로그래밍 풀이접근법나는 보통 DP 문제를 풀 때 각 원소에서 선택할 수 있는 최선의 값을 고르는 점화식을 생각한다.이 문제도 동일한 방식으로 접근했고, i번째 집을 털 경우와 털지 않는 경우 두 가지 중 최대값을 선택하는 점화식을 생각했다. 처음 생각한 점화식은 다음과 같다.DP[i] = Math.max(DP[i-1], DP[i-2] + money[i]) DP[i-1]의 경우..

문제https://www.acmicpc.net/problem/3020 풀이누적합을 활용한 풀이접근법N이 최대 200,000, H가 최대 500,000으로 들어오는 것을 조심해야 한다.단순히 O(NH)로 풀게 될 경우 시간초과가 발생하기 때문에 완전탐색 쪽으로는 생각하지 않았다. 그러면 어떻게 각 구간에 대해 효율적으로 탐색할 수 있을까? 처음에 떠올랐던 건 각 구간 별로 입력을 받을 때마다 갱신하면 되지 않을까였다.N개의 입력에서 갱신하는 방법에 대해 생각한 결과 각 구간 별로 누적합 원리를 활용해서 종유석 | 석순 각각에 대해 카운팅 해준 다음, 누적합을 구하는 방식으로 풀이했다.결과에 대해서는 i구간에 대해 종유석[i] + 석순[i]의 합이 개똥벌레가 부숴야하는 장애물의 개수이며, 최소값을 구한 후 ..

문제https://www.acmicpc.net/problem/1339 풀이자료구조를 활용한 그리디 풀이첫번째 접근법 (오답)다음과 같은 우선순위를 통해서 알파벳에 대한 값을 메겼습니다.자리수가 높은 알파벳 우선같은 자리수라면 개수에 따라서반례2ABBB----wrong : 186ans : 188해당 접근으로는 바로 뒷자리수에 나오는 알파벳에 따라 잘못된 결과가 측정될 수 있었습니다. 두번째 접근법그렇다면 위와 같은 반례에 대해서 어떻게 풀이를 해야할까요?처음에는 단순히 바로 뒤에 나오는 각각의 자리수에 대해서 알파벳의 개수를 측정하고, 비교하려 했는데요. 이렇게 될 경우 로직이 굉장히 복잡해지고 어떻게 코드를 작성해야할지 모르겠더라구요.코드를 아예 지우고 다시 생각을 해본 결과 다음과 같은 로직을 생각할 ..

Intro코드트리 조별과제를 진행한지 저에겐 2주차가 되는 시점이네요!이번 주차에는 평소 해야지 해야지... 하고 생각만 하던 정렬 알고리즘에 대해 학습을 진행했습니다.보다시피 코드트리에는 정렬 알고리즘 학습 커리큘럼이 잘 구성이 되어있고, 이미지 및 영상 참고자료도 보기 편하게 제공이 되어 원활하게 학습할 수 있었습니다. 또한 각각의 알고리즘 동작 방식과 시간, 공간 복잡도를 중점으로 학습하였습니다. Bubble Sort(버블 정렬)거품 정렬은 가장 단순한 정렬 알고리즘입니다. 기본적인 아이디어는 간단합니다. 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환해줍니다. 이런 절차를 정렬이 될 때 까지..