알루 코딩

해당 문제 'Count Nice Pairs in an Array'는 nums 라는에서 'nice pair'의 수를 찾는 문제입니다. 배열 안의 두 숫자 'i'와 'j' ('i' < 'j') 가 'nice pair'로 간주될 때, "nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])" 이 성립해야 합니다. 여기서 rev(x)는 숫자 x의 자릿수를 반전시킨 결과입니다. 문제의 핵심은 각 숫자와 그 숫자의 반전된 형태의 차이를 이용하는 것입니다. 이 차이가 동일한 숫자들의 쌍이 'nice pair'를 형성합니다. 우선 코드부터 살펴보겠습니다. class Solution(object): def countNicePairs(self, nums): mod = 10 ** 9 + 7 ..

문제 설명부터 해보도록 하겠습니다. digits 이라는 숫자 문자열을 입력값으로 받는데요, 각 숫자 키패드에 해당하는 알파벳 문자열로 만들 수 있는 모든 문자열의 리스트를 출력하는 문제입니다. 예시 1을 보면, digits은 "23"으로 주어졌고, 각 숫자인 "2"에는 "abc"의 알파벳이, "3"에는 "def"의 알파벳이 주어져있습니다. 때문에, "23"으로 만들 수 있는 알파벳 문자열은 "ad"부터 "cf"까지 총 9가지가 될 수 있는 것을 알 수 있습니다. 여기서 캐치해야 할 점은 만들 수 있는 알파벳 문자열의 길이는 digits의 길이와 같을 수 밖에 없다는 점입니다. 흡사 순열과 조합 문제로 이해될 수 있는데, 보통 알고리즘 문제에서는 combination을 사용하거나 product, permu..

문제의 로직은 간단했습니다. 주어진 배열 nums에서 마크되지 않은 최소값을 더해가며 총 합을 출력하면 되는 문제였습니다. 여기서 마크되지 않았다는 것은 문제에서 주어진 예시를 보면 잘 이해가 될 것입니다. 쉬운 문제라고 생각했지만, 처음에는 풀지 못했습니다. 제가 처음에 풀었던 코드는 아래와 같습니다. class Solution: def findScore(self, nums: List[int]) -> int: res = 0 mark = [0 for _ in range(len(nums))] tmp = nums[:] while len(tmp)!=1: res += min(tmp) target = tmp.index(min(tmp)) print("index:",target,"min value:",min(tmp)..

한 번 문제를 이해해봅시다. 입력값으로 주어진 asteroids 배열은 소행성 배열입니다. 이 소행성은 양수값을 가질 수도 있고, 음수값을 가질 수도 있습니다. 양수값을 가진 소행성은 오른쪽으로 움직이고, 음수값을 가진 소행성은 왼쪽으로 움직입니다. 모든 소행성은 크기에 관계없이 같은 속도로 움직이기 때문에, 추월, 정지 등의 사건이 발생하지 않습니다. 두 소행성이 충돌했을 때는, 소행성의 크기의 절댓값에 따라서 소행성이 사라집니다. 예를 들어, '2'의 소행성과 '-5'의 소행성이 충돌했다면, '-5'의 소행성이 더 절댓값이 크기 때문에 '2'의 소행성이 없어지고, '-5'의 소행성은 계속해서 움직였던 방향대로 지나갑니다. 이 때, 두 소행성의 크기의 절댓값이 같다면, 두 소행성이 충돌했을 때는 두 소..

많이들 접해보신 DP의 단골문제 동전문제입니다. 주어진 동전을 얼마든지 사용하면서 amount를 만들 수 있는 총 가짓수를 구하는 문제인데요, 이 외에도 가장 최소의 동전 개수만 사용해서 푸는 문제 등 동전에 관한 DP문제는 이제 거의 정형화된 알고리즘으로 자리잡았습니다. 그렇기 때문에, 해당 문제를 푸는 방향도 처음 본 문제라면, 접근이 어려울 수 있습니다. 특히, DP는 많은 유형을 풀어봄으로써 어느정도 유형화를 하는 것도 방법입니다. 이 문제에 대해서는 먼저, 메모제이션 기법을 사용해서 전형적인 DP로 풀어보도록 하겠습니다. 그럼, 이 문제에 대해 이해를 시각화해볼까요? 원리를 살펴보면 다음과 같은 테이블을 그릴 수 있습니다. 테이블의 열은 '(원)'을 뜻하며, 0원부터 amount(=5)원까지 테..