본문 바로가기
반응형

개발/Algorithm

 (98)
[리트코드] Reverse Linked List(python) 리트코드, Reverse Linked List_연결 리스트 뒤집기 TL;DR 연결 리스트(Linked List) 문제를 해결할 수 있는지 문제 분석 1. 주어진 연결 리스트를 뒤집은 리스트를 반환하라. 입출력 형태 - 입력으로 주어진 연결 리스트를 뒤집은 연결 리스트를 반환하면 된다. 풀이 class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head: return None slow, rev = head, None while slow: rev, rev.next, slow = slow, rev, slow.next return rev - https://firsteast.tistory.com/35 에서 러너(Runner) 기법을 활..
[리트코드] Merge Two Sorted Lists(python) 리트코드, Merge Two Sorted Lists_정렬된 두 개의 리스트 병합 TL;DR 연결 리스트(Linked list)를 문제 조건에 맞게 구현할 수 있는지 문제 분석 1. 두 개의 정렬된 리스트를 병합하고, 정렬된 리스트의 형태로 반환한다. 2. 반환되는 리스트는 주어진 두 개의 함께 리스트를 엮어(splicing) 만들어야 한다. - 1 : 해결해야 하는 문제에 대해서 말하고 있다. - 2 : 반환 조건에 대해서 말하고 있다. 별도의 연결 리스트를 선언하지 않고, 두 개의 연결 리스트를 하나의 정렬된 연결 리스트로 만들어야 한다. 입출력 형태 - 예시에는 배열처럼 주어졌지만 실제로는 연결 리스트로 구현되어 있다. - 두 개의 연결 리스트를 예시 1과 같이 오름차순으로 정렬된 하나의 연결 리스트..
[리트코드] Merge Sorted Array(python) 리트코드, Merge Sorted Array_정렬된 배열 병합 TL;DR 배열을 문제에 제시된 조건에 맞게 해결할 수 있는지 문제 분석 1. m과 n의 유효한 원소를 갖고 있는 비내림차순으로 정렬된 정수 배열 nums1와 nums2 2. nums1과 nums2를 nums1에 비내림차순으로 정렬하여 합쳐야 한다. 3. 정렬된 답은 nums1에 저장되어야 한다. 4. nums1은 m + n길이를 갖고 있으며 첫 번째, m개 만큼이 정렬의 대상이 되는 정수들이다. 5. nums2는 n길이를 갖고 있으며, n이 0이라면 무시한다. - 비내림차순(non-decreasing order) : 오름차순과는 다른 개념이다. nums1과 nums2에서 같은 원소가 있을 때는 nums1의 원소가 nums2의 원소보다 앞서 ..
[리트코드] Plus One(python) 리트코드, Plus One_1 더하기 TL;DR 해결해야 하는 문제를 구현할 수 있는지 문제 분석 1. 비어 있지 않은 음수가 아닌 정수가 주어지는 10진수 숫자가 저장된 리스트로 구성된 수에 1을 더하라. 2. 가장 큰 자리수의 수가 가장 처음에 저장되고, 각 원소들은 단일 숫자를 포함하고 있다. 3. 0만 있는 경우를 제외하고는 가장 처음에 0이 오지 않는다고 가정한다. - 1 : 해결해야 하는 문제 조건에 대해 설명하고 있다. - 2 : 리스트의 가장 앞쪽부터 가장 큰 자릿수의 숫자를 나타낸다. 각 자릿수의 숫자는 10 미만의 정수이다. - 3 : 리스트이 [0]으로 주어지는 경우를 제외하고, 0이 리스트의 가장 앞, 즉 가장 큰 자릿수 위치에 오면 안된다. 입출력 형태 - digits : 10 미..
[리트코드] Palindrome Linked List(python) 리트코드, Palindrome Linked List_연결리스트 팰린드롬 TL;DR 연결 리스트(Linked List)를 활용하여 팰린드롬 문제를 해결할 수 있는지 문제 분석 1. 주어진 연결 리스트 head가 팰린드롬일 경우 true를 반환하여라. - 1 : 해결해야 하는 문제에 대해서 말하고 있다. 특이한 점은 연결 리스트로 자료형이 주어져 있다는 것이다. 입출력 형태 - 예시에서는 리스트 형태로 입력이 주어지지만, 입력은 연결 리스트 형태로 주어진다. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next - val에는 해당하는 노드의 값이 주어지고, next에는 연결된 다음 연결 리스트가 주어진다. -..
[프로그래머스] 피보나치 수(python) 프로그래머스, 피보나치 수 TL;DR 재귀(Recursive) 또는 동적 프로그래밍(Dynamic programming)을 활용할 수 있는지 문제 분석 1. 2 이상 n 이하의 주어진 입력에 따라 피보나치 코드를 완성하라. 2. 완성된 피보나치 수는 1234567로 나눈 나머지를 리턴해야 한다. - 1 : 해결해야 하는 문제 조건을 알려주고 있다. - 2 : 구한 피보나치 수를 1234567로 나눈 나머지로 구해야 한다. 입출력 형태 - 주어진 n번째 피보나치 수를 구하면 된다. - 문제 조건 2에 따라서 각 피보나치 수는 1234567로 나눈 나머지를 반환해야 한다. - 이 이유는 피보나치 수가 n에 따라서 점점 많이 커지기 때문에 표현할 수 있는 범위를 넘어갈 수 있기 때문이다. 풀이 def solu..
[리트코드] Best Time to Buy and Sell Stock(python) 리트코드, Best Time to Buy and Sell Stock_주식을 사고팔기 가장 좋을 때 TL;DR 주어진 배열을 순회하며 문제의 조건을 구현할 수 있는지 문제 분석 1. i번째 날 주어진 주식의 가격이 담긴 배열 prices가 주어진다. 2. 가장 주식이 쌀 때 구매하고 싶고, 미래에 가장 값이 비쌀 때 주식을 판매하고 싶다. 3. 그 때의 최대 수익을 반환하라. 만약 수익을 창출할 수 없다면 0을 반환하라. 입출력 형태 - 일 별 주식의 가격이 담긴 배열 prices가 주어진다. - 예시 1 : - 주식이 가장 저렴한 1일때 사서, 그 이후 미래에 가장 비쌀 때인 6일 때 팔면 최대 수익인 5를 얻을 수 있다. - 예시 2: - 어느 시점에 주식을 사던, 수익을 창출할 수 없다. 따라서 0을..
[리트코드] Product of Array Except Self(python) 리트코드, Product of Array Except Self_자기 자신을 제외한 배열 곱셈 TL;DR 문제 조건에 따라 배열을 활용하여 문제를 풀 수 있는지 문제 분석 1. 주어진 정수 배열 nums에서 각 원소를 제외한 나머지 원소들의 곱으로 이루어진 배열을 반환한다. 2. 숫자들은 32비트 정수로 한정된다. 3. 시간 복잡도가 O(n)이어야 하며, 나머지 연산을 활용하면 안된다. - 1 : 해결해야 하는 문제 조건에 대해서 말하고 있다. - 2 : 문제 자체적으로 값의 상-하한을 주고 있다. 파이썬에서는 크게 신경쓰지 않아도 된다. - 3 : 문제의 제약 조건을 말하고 있다. 이 부분이 굉장히 풀이를 하는데 어렵게 다가왔다. 입출력 형태 - nums : 정수 배열 nums가 주어진다. - 각 원소를..

티스토리툴바