전체 글252 ch10-1-2(leetcode 641). 원형 데크 디자인 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 641번 ( https://leetcode.com/problems/design-circular-deque/ ) 처음 문제를 풀었을 때는 원형 데크를 리스트를 통해서 구현했다. 하지만 문제에서는 원형 데크를 '이중 연결 리스트(doublely linked list)'를 통해서 구현하라고 명시했으므로 다시 풀어보자. 이중 연결 리스트는 단일 연결 리스트(singly linked list)와 조금 다르다. 단일 연결 리스트는 포인터가 한 개로, 자신의 오른쪽에 있는 노드만 가리킬 수 있고 역방향으로는 조회할 수 없다. 반면 이중 연결 리스트는 포인터가 left, right 총 2개가 있기 때문에 자신의 왼쪽 및 오른쪽 노드를 가리키고.. 2023. 1. 12. ch10-1-1(leetcode 641). 원형 데크 디자인(풀이X) * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * * 해당 포스트는 641번 문제에 대한 정답 풀이를 포함하고 있지 않으며 공부하다 참고용으로 작성된 포스트입니다. * leetcode 641번 ( https://leetcode.com/problems/design-circular-deque/ ) 데크는 큐의 일종이지만 큐와 달리 양쪽에서 원소를 조회, 삭제, 추가할 수 있다. 데크 역시 큐와 스택처럼 ADT이며 연결 리스트, 이중 연결 리스트, 배열 등 다양한 자료형으로 구현할 수 있다. 이번 문제는 그냥 데크가 아닌 원형 데크를 연결 리스트를 사용해서 구현하는 문제이다. 이전에 원형 큐를 구현하던 것처럼, 미리 고정된 크기의 공간을 할당한 뒤 포인터를 이동하는 방식으로 구현하면 된다. 다만 데.. 2023. 1. 12. ch9-6(leetcode 622). 원형 큐 디자인 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 622번 ( https://leetcode.com/problems/design-circular-queue/ ) 풀이방법 1. (오답노트) (문제를 잘못 이해하고 풀었던 풀이다.) 코드는 다음과 같다. class MyCircularQueue(object): def __init__(self, k): self.size = k self.queue = [] def enQueue(self, value): if len(self.queue) == self.size: return False self.queue.append(value) return True def deQueue(self): if len(self.queue) == 0: return.. 2023. 1. 11. ch9-5(leetcode 232). 스택을 이용한 큐 구현 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 232번 ( https://leetcode.com/problems/implement-queue-using-stacks/ ) 풀이방법 1. 교재를 보지 않고 시도했던 방법이다. 이전 문제와 비슷하게, 스택에서 사용할 수 있는 메소드만 사용해서 큐를 구현하는 문제이다. 이전의 큐는 원소를 빼낼 때는 앞에서, 원소를 넣을 때는 뒤에서 넣었다(FIFO). 반면 스택은 원소를 넣는 것과 빼는 작업이 모두 맨 뒤에서 일어난다(LIFO). 그래서 스택을 큐로 구현할 때처럼 큐의 앞에서 원소를 뺀 다음에 큐의 맨 뒤에 넣는 방식으로, 공간을 안 사용하고 풀 수는 없다. 스택에서 원소를 하나 빼서 하나를 다시 넣는다고 해서 스택의 값이 변하지 .. 2023. 1. 11. ch9-4(leetcode 225). 큐를 이용한 스택 구현 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 225번 ( https://leetcode.com/problems/implement-stack-using-queues/description/ ) 풀이방법. 보통 큐나 스택은 배열이나 연결 리스트(linked-list)로 많이 구현하는데, 이 문제는 특이하게 스택을 큐로 구현하는 문제였다. 큐와 스택은 배열이나 연결 리스트처럼 실제로 구현된 자료구조 형태가 아닌 추상적인 자료구조(ADT, abstract data types)이다. 그래서 실제 사용할 때는 다른 자료구조를 이용하여 구현한다. 파이썬에는 스택의 push()와 pop(), 큐의 enqueue(), dequeue() 메소드가 모두 구현된 데크(deque) 자료형이 있다... 2023. 1. 11. ch9-3(leetcode 739). 일일 온도 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 739번 ( https://leetcode.com/problems/daily-temperatures/description/ ) 풀이 방법 1. 스택을 사용한다. 결과로는 각 i번째 날 이후로 따뜻해지기 위해 기다려야 하는 일 수를 리턴해야 하므로, 스택 및 결과에는 인덱스 정보를 저장하는 것이 좋겠다. 우선 큰 틀에서 for loop를 사용해서 temperatures의 전체 요소를 순회할 수 있도록 한다. 각 시행의 값(i번째 날의 인덱스와 온도)을 가지고, 우선 스택에 값이 있는지를 확인한다. 파이썬에서는 for문으로 리스트의 인덱스와 값을 동시에 순회하고 싶을 때 enumerate()를 사용할 수 있다. for index, .. 2023. 1. 10. 이전 1 ··· 29 30 31 32 33 34 35 ··· 42 다음
