문제로 풀어보는 알고리즘 : 시작하기

오른쪽으로 배열 회전하기

배열 arr[]에서 위치 s, t 사이로 1만큼 오른쪽으로 회전시켜보자.

단, arr[t]의 경우, arr[s]로 복사하면 된다.

풀이 순서

  1. i = t : 뒤부터 탐색을 시작하자.
  2. arr[i] = arr[i - 1] : 1 만큼 왼쪽으로 이동.
  3. arr[s] 에 이르선 arr[s - 1] 이 더 이상 없는 문제가 있음.
  4. 사전에 arr[t]last 에 저장하여 arr[s] 에 대입한다.

코드 풀이

void right_rotate(int arr[], int s, int t)
{
    int i, last;
    last = arr[t];
    for (i = t; i > s; i--)
        arr[i] = arr[i - 1];
    arr[s] = last;
}

어떻게 k 만큼 이동하면 좋을까

1만큼 이동하는 함수를 k 번 반복하면 되지만 이 방법은 O(n^k), (n은 s , t 사이의 거리)로 느린 문제가 있다.

Python 풀이

def k_right_rotate(arr: int, s: int, t: int, k: int):
    last = []
    for i in range(t, t - k, -1):
        last.append(arr[i])
    for i in range(t, t - k - 1, -1):
        arr[i] = arr[i - k]
    for i, atom in enumerate(reversed(last)):
        arr[s + i] = atom
    return arr

arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(k_right_rotate(arr, 2, 6, 2))

C 풀이

int k_right_rotate(int arr[], int s, int t, int k)
{
    int i, last[k];
    int move_last = t - k;
    for (i = t; i > move_last; i--)
        last[t - i] = arr[i];
    for (i = t; i > move_last - 1; i--)
        arr[i] = arr[i - k];
    for (i = 0; i < k; i++)
        arr[s + i] = last[k - 1 - i];
    return arr;
}

실행 시간은 n + k 이다.

스택 2개로 큐 구현하기

스택 2개를 활용하여 큐를 구현해보자.

풀이 순서

  1. 큐 객체를 처음 생성할 때 스택 2개 in_stack, out_stack 를 만든다.
  2. 큐에 값이 들어갈때는 in_stack의 끝에 넣는다.
  3. 큐에 값이 나갈때는 모든 in_stack의 값을 out_stack 로 옮겨 stack2 을 뺴내면 된다.

in_stack에서 out_stack으로 값이 옮겨지는 과정을 활용하면 자연스럽게 큐가 구현된다.

풀이

Python 풀이

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, value):
		self.elements.append(value)

	def pop(self):
		if self.size() > 0: # 우선순위 pop > None
			return self.elements.pop()
		else:
			return None

	def size(self):
		return len(self.elements)

class Queue:
	def __init__(self):
		self.inbox = Stack()
		self.outbox = Stack()

	def enqueue(self, value):
		self.inbox.push(value)

	def dequeue(self):
		if self.outbox.size() is 0:
			while not self.inbox.size() is 0:
				pop = self.inbox.pop()
				self.outbox.push(pop)
		return self.outbox.pop()