728x90 반응형 Programming/LeetCode3 LeetCode 1137. N-th tribonacci number 이 문제는 피보나치 수열을 약간 변형한 tribonacci 수열에서 N번째 수를 찾는 것이다. 피보나치 수열은 정의도 간결하고 솔루션도 간단해 동적 프로그래밍(dynamic programming, DP)을 공부하기 좋은 기본 예제이다. 또한, 이 문제는 DP의 적용 효과를 뚜렷하게 보여주는 문제이기도 하다. 두 가지 방법으로 코딩을 해보았다. solution 1: brute force 첫 번째 방법은 brute force로 N번째 수를 결정하는 뒤의 세 개의 수를 중복해서 찾는다. 직관적이고 tribonacci 수열의 정의에 충실하지만 아주 비효율적이다. 이 방법으로 leetcode에서 서밋을 한다면 Time Limited Error를 낸다. 문제를 처음 대할때는 레퍼런스로 삼기위해 공부차 한 번 시도해.. 2020. 11. 20. LeetCode: 1128. Number of Equivalent Dominoes 문제 주어진 배열에서 도미노 쌍(domino pair)의 개수를 알아내는 문제이다. 도미노 쌍은 두 배열이 [a, b], [c, d] 주어졌을 때, a==c & b==d || b==c & a == d를 만족하는 것을 말한다. 즉, 두 원소가 그대로 혹은 뒤집어 같으면 도미노쌍으로 정의한다. 주의할 점은 같은 원소를 비교할 수 없다. 따라서 중복 카운팅 없이 도미노쌍을 찾아야 한다. Solution 1 (Brute force) - Time Limited Error 모든 경우의 수를 탐색해보는 brute force 방법으로 먼저 코딩해 볼 수 있다. 간단한 문제이고 이중 for문으로 짜볼 수 있다. class Solution: def numEquivDominoPairs(self, dominoes: List[.. 2020. 11. 17. LeetCode: 1122. Relative Sort Array 문제 이 문제는 비교적 간단하다. 좋아요도 많다. 이것은 문제가 모호함이 없이 명쾌하다는 것이다. 문제를 요약하자면 다음과 같다. arr1, arr2 두개의 배열이 있다. arr1을 arr2의 기준으로 sorting하는 것이다. arr2의 모든 원소는 arr1에 포함되어있다. 하지만 arr1에는 arr2에 없는 원소도 있다. 이때, 이 원소들은 오름차순으로 sorting 된 arr1의 뒤에 붙이는 것이다. 위의 예제를 보면 이해가 된다. 이 문제에서 주의 할 점은 arr1에 같은 원소가 복수개로 주어질 수 있다는 것이다. 이것들은 sorting될 때 나란히 놓이게 되는 것이다. 세가지 방법으로 코딩을 해봤다. 목표는 효율성을 증가시켜 런타임을 줄이는 것이다. solution 1 (Runtime: 40ms.. 2020. 11. 16. 이전 1 다음 728x90 반응형
