알루 코딩

문제 설명부터 해보도록 하겠습니다. 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)원까지 테..

해당 문제는 팰린드롬 문제입니다. '팰린드롬'이라는 것은 문자열을 앞에서 읽나 뒤에서 읽나 동일한 문자열 형태를 띄는 문자열을 말하는데요, 'a'라는 단일문자도 팰린드롬에 속하는 것을 유의하면 됩니다. 이 문제에서는 주어진 문자열 s 에 들어있는 팰린드롬 문자열이 총 몇개인지 파악하는 문제입니다. 첫번째 예시에서 문자열 s는 'abc'인데, 각 단일문자만이 팰린드롬이고, 그 외에는 팰린드롬이 아니기에 결과를 3을 리턴합니다. 두번째 예시에서 문자열 s는 'aaa'인데, 결과가 6이 나왔습니다. 먼저 각 위치에서 'a'가 단일문자로서 팰린드롬을 형성하고, 첫번째,두번째 문자로 이루어진 'aa'와 두번째, 세번째 문자로 이루어진 'aa'가 총 2개 있습니다. 마지막으로 'aaa'도 팰린드롬 문자열이기에 결과..