나의 발자취

문제 링크 https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/ 문제 접근 방법 투포인터의 응용 문제이다.tail으로부터 출발하면 투포인터 쓰지 않아도 되지 않나...생각했는데, 투포인터를 쓴대니까 right pointer로 삭제할 노드를 짚어내나? 라고 생각해서 접근했는데 이렇게는 도무지 투포인터 패턴으로 문제가 안풀리는거다. 일단 left pointer의 역할은 연결리스트 특성상 노드를 삭제하고 나면 삭제된 노드 이전 노드랑 연결하는 역할일거라 생각해서, left pointer는 루프가 끝났을 때 무조건 그 곳으로 가있어야할 것 같았고.. (즉, Nth Node - 1에 위치하고 있어야함) 그럼 left/right po..

문제 링크 https://leetcode.com/problems/3sum/description/    문제 접근 방법투포인터임. 무조건~ 근데 중복 값 처리가 은근 까다롭다. 1. 일단 처음은 배열을 정렬해서, 중복되는 값들을 처리하기 쉽게 하는데 이렇게 되면, 중복된 값들이 정렬된 배열에 서로 연속으로 놓여있기 때문에 스킵하기 편하고, 이 결과 유니크한 triplet을 답으로 확보할 수 있다. 2. 그다음은 순회를 할건데, 각 순회마다 "피벗"이 되는 nums[i]를 두고 그 오른쪽의 값들(추후 투포인터가 됨)이랑 비교를 계속 하는거다. 목표는 투포인터의 합이 -nums[i]가 되면 된다. 그래서 만약에 합이 너무 크면 right 포인터를 왼쪽으로, 작으면 left 포인터를 오른쪽으로 옮기면서 하면 되..

문제가 요구하는 것에 따라서 조금씩 다르다. LC에서는 파이썬의 리스트 인덱싱 기법을 이용해서 풀었고, class Solution: def isPalindrome(self, s: str) -> bool: phrase = [] for i in s: if i.isalnum(): phrase.append(i.lower()) return phrase == phrase[::-1]  다른데에서는 투포인터 이용해서 풀었다.def is_palindrome(s): left = 0 right = len(s)-1 while left

Two Pointers?리트코드 알고리즘 문제에서 정~말 많이 사용되는 유형으로, 보통 데이터 구조가 선형 구조이고, 데이터의 연산이 두 개의 포인터를 가지고 연속적으로 해야할 때 사용된다. 대표적인 유형으로는 Two Sum이 있다. ㅎ투 포인터 기법을 쓰는 이유는 뭣보다도 시공간 복잡도가 O(N)에 처리될 수 있는 장점때문이다.이 말고도 문자열이 palindrome인지 구분할때에도 쓸 수 있고, 더 많은 전형적인 유형들은 아래에서 다루어볼 것이다.  In Real-World Problems대학교에서는 알고리즘에 관하여 이렇게는 안알려주는 것 같은데, 이것이 왜 필요한 기법인지 납득이 가야지만 알고리즘을 잘 활용하는 나같은 유형의 경우 이걸 좀더 일찍 알았더라면~ 하는 아쉬움은 있다.따라서 무작정 '알고..

문제 링크https://leetcode.com/problems/increasing-triplet-subsequence/description/?envType=study-plan-v2&envId=leetcode-75 문제 접근 방법greedy 고민한 부분처음에는 루프 순회를 역으로 하려다가.. 아닌것같아서 바로 접었다.  코드class Solution: def increasingTriplet(self, nums: List[int]) -> bool: first = second = float('inf') # first와 second 초기화 for num in nums: if num

문제 링크 https://leetcode.com/problems/can-place-flowers/description/?envType=study-plan-v2&envId=leetcode-75 문제 접근 방법1) 점화식일단 0의 갯수와 꽃을 심는 개수의 상관관계를 파악하기 위해 패턴을 분석해보니 0이 3개가 연속으로 있을 때 1개까지 심을 수 있고, 0이 5개일 때 2개, 7개일 때 3개... 이런 식으로 되는 것 같았다.점화식을 세우고 이걸 활용하기로.  고민한 부분후. 조건 처리를 생각하느라 골치 아팠다.연속하는 애들을 어떻게 케이스를 나누어 처리할건지였는데,일단 0이면 꽃을 심을 수 있는 공간이니 consecitive_zeros에다가 1을 더해주고,그렇지 않은 경우(1인 경우)에는 consecitiv..

문제 링크https://leetcode.com/problems/reverse-vowels-of-a-string문제 접근 방법일단 주어진 예시를 가지고 어떻게 해야 효율적으로 모음을 바꿔서 리턴할 수 있을지 패턴을 분석해봤다. reverse가 들어간다는 것은, 가장자리에 있는 것들은 저들끼리 바뀌고, 안쪽에 있는 것들은 저들끼리 바뀌기 때문에-> swap 의 개념이 들어가지 않을까.. 하고-> swap이라면 각각 좌/우에서 포인터가 존재해서 점점 인덱스를 늘려/줄여가면서 가운데에서 만나면 연산 횟수가 효율적이라고 생각되었다. 고민한 부분1) 루프 순회 방법위의 패턴을 분석하기 전에는 루프 순회를 어떻게 할지 고민이 되었는데, 마지막 생각을 했던 부분에서 루프의 조건을 left  2) swap을 어떻게 처리..

문제 링크https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/description 문제 접근 방법난이도가 Easy라 별도로 활용해야하는 알고리즘은 없었다. 굳이 따지자면 그리디? 고민한 부분for 루프의 인덱스가 되는(candy + extraCandy) element가 해당 리스트(candies)에서 최댓값인지 식별을 해야 하는데, 이 방법을 어떻게 해야 복잡도를 최소화하는지 고민이 되었다. 해결한 방법어차피 extraCandies를 더하는건 순차적이고, 더하게 되는 순간부터는 주어진 candies 리스트의 요소들과 비교하는 것이므로 처음부터 max값을 뽑아서 변수로 지정을 해놓는다. 주의사항리스트에 append로 문자열을 추가하..