오뚝이개발자

문제 https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 리트코드 풀이를 하다가 굉장히 재미있는 문제가 있어 가져와봤다. 문제는 간단하다. 리스트와 타겟이 주어지면 그 리스트의 3개의 원소의 합이 타겟과 같아지는 그룹을 return하는 문제다. 여기서 포인트는 단순히 3중 for문으로 구현하면 시간초과가 난다는 것이다. 다른 방법을 고안해야 하는데 그 풀이가 굉장히 흥미롭다. tw..

문제 https://leetcode.com/problems/integer-to-roman/ Integer to Roman - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 2가지 방법으로 풀이했다. 첫 번째 방법은 좀 naive한 풀이이고, 두 번째 방법은 변환의 규칙을 파악한 풀이이다. SOL 1) 문제에서 주어진 조건이 num의 범위가 [1,3999]이므로 이 범위 안에서만 변환을 생각하면 된다. 예컨대, 256을 변환하려면 200+50+6으로 분..

nums=[1,2,1], target=3일 때, nums에서 원소의 합이 target인 부분집합은 몇 개일까? 답은 (1,2), (2,1)로 2개이다. 그렇다면 이를 구하기 위한 알고리즘은 무엇일까? 이러한 문제를 counting subsets with given sum이라 한다. 다른 문제에도 자주 이용되니 알아두자! 가능한 모든 경우를 파악해보면 된다. 그런데 이 때, 각 숫자는 합에 포함되거나 안되거나 둘 중 하나의 선택지를 갖는다. 그림으로 나타내면 아래와 같다. 이를 풀기 위해선 dp를 사용하면 된다. 위와 같이 dp를 모두 채운 뒤 dp[-1][-1]이 답이 된다. 관련 문제 leetcode.com/problems/target-sum/ Target Sum - LeetCode Level up y..