알고리즘

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 직관적으로, board를 순회하면서 각 skill의 크기에 맞게 값을 더해주면서 풀게되면 Worst case의 시간복잡도가 O(N*M*K) = 1,000 * 1,000 * 250,000 = 250,000,000,000 으로 효율성이 천장을 뚫어버리게 된다. 따라서 구간의 합을 쉽게 해주는 누적합을 떠올릴 수 있다. 누적합이란 말 그대로, 배열을 순회하면서 누적된 값을 해당 배열에 더해주..

평소같이 기계적으로 프로그래머스 코딩테스트를 풀다가.. 벽에 부딪혔다. 나와 같은 실수를 하는 사람들을 위해 글을 남겨보겠다. https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제는 평범한 DP문제였지만 생각해야 할 점은 집이 원형으로 이루어져 있기 때문에 이를 선형 자료구조인 vector로 다루기 때문에 이 점만 조심하면 된다. 따라서 까다로운 조건인 첫번째 집을 선택했을 때에 마지막 집을 포함하지 않아야 한다는 조건만 생각하면서 이를 ..