[SW 정글 21일차] 자료구조 복습하기

오늘은 시간이 조금 여유로워서 지난 날들에 했던 정렬, 큐, 스택, 힙 등을 복습하는 시간을 가졌다.

복습을 하면서 정리하지 못했거나 처음 해본 내용들을 기록해보려고 한다.

 

 

 

1. 스택으로 큐 구현, 큐로 스택 구현

오늘 알아본 것 중 하나는 스택으로 큐를 구현하고 큐로 스택을 구현하는 것이다.

이미 알다시피 스택은 입출력 구조가 FILO형식이고 큐는 FIFO형식이기 때문에 스택 2개로 큐를 구현하고 큐 2개로 스택을 구현해야한다.

 

먼저, 스택 2개로 큐를 구현해보는 것을 알아보자.

기본적인 원리는 스택 A, 스택 B가 있다면 스택 A는 데이터를 넣어주는 용도로 쓰이고 스택 B는 데이터를 빼주는 용도로 쓸 것이다.

그림을 보며 무슨 말인지 이해해보자.

일단은 데이터가 1, 2, 3 순서대로 스택 A에 push 되었다.

큐로 구현되기 위해서는 들어온 순서인 1, 2, 3 그대로 나와야 하기 때문에 추가적인 작업이 필요하다.

추가적인 작업으로 스택 A에서 데이터를 pop하여 스택 B에 push 시켜준다.

그러면 스택 B에 위 사진처럼 데이터가 쌓이게 되고 pop을 해주면 들어간 순서대로 나올 수가 있게 된다.

 

이제 원리를 알아봤으니 직접 코드로 구현해보자.

class Queue:

    def __init__(self):
        self._stack1 = []
        self._stack2 = []

    def __len__(self):
        return len(self._stack1) + len(self._stack2)

    def enQueue(self, data):
        self._stack1.append(data)

    def deQueue(self):
        if len(self._stack2) == 0:
            while len(self._stack1) != 0:
                self._stack2.append(self._stack1.pop())

        return self._stack2.pop()

 

 

다음으로 큐 2개로 스택을 구현해보는 것을 알아보자.

큐 2개로 스택을 구현하는 것은 스택 2개로 큐를 구현하는 것보다 생각을 더 해야한다.

단순히 큐A에서 큐B로 이동시켜서 큐B에서 pop해봤자 그냥 큐로 동작할 것이다.

그러면 어떻게 해야할까?

어떠한 데이터를 큐 A에 넣고자 할 때 큐 A에 데이터가 있다면 모든 데이터를 큐 B에 옮긴다.

그런 뒤, 저장하고자 하는 데이터를 큐 A에 넣어주고 다시 큐 B에 있는 데이터를 큐 A에 넣는 작업을 한다.

이 후에 pop을 하고자 한다면 그냥 큐 A에서 pop을 하면 FILO로 동작하게 된다.

그림으로 통해 더 자세히 알아보자.

위 그림처럼 큐 A에는 데이터 1, 2가 있고 데이터 3를 push하고자한다. (데이터 번호는 큐에 들어온 순서라고 생각하자.)

그러면 그냥 큐 A에 push한다면 pop했을 때 데이터 2번이 나오므로 스택의 FILO형식이 아니다.

그래서 아래의 그림과 같은 작업을 시행한다.

이러한 과정을 거치고 나면 큐A에서 pop을 하면 마치 스택처럼 FILO가 구현될 수 있는 것이다.

 

이제 원리를 알아봤으니 직접 코드로 구현해보자.

class Stack:

    def __init__(self):
        self._queue1 = []
        self._queue2 = []

    def __len__(self):
        return len(self._queue1)

    def push(self, data):
        if len(self._queue1) == 0:
            self._queue1.append(data)

        else:
            while len(self._queue1) != 0:
                self._queue2.append(self._queue1.pop(0))

            self._queue1.append(data)

            while len(self._queue2) != 0:
                self._queue1.append(self._queue2.pop(0))

    def pop(self):
        return self._queue1.pop(0)

 

 

 

 

2. 이진 트리가 완전 이진 트리인지 아닌지 판단하기

나는 13일차에 트리 구조와 이진 트리, 완전 이진 트리에 대해 공부하고 정리한 적이 있다.

https://straw961030.tistory.com/192

[SW 정글 13일차] 트리 구조와 이진 트리

완전 이진 트리를 복습하려고 다양한 블로그 글을 보던 중에 재밌는 제목이 눈에 보였다.

"이진 트리가 완전 이진 트리인지 확인하는 알고리즘"

여기서 말하는 완전 이진 트리 확인 조건은 다음과 같다.

1. 트리를 루트부터 탐색 중에 full node가 아닌 node를 만날 경우 그 이후에 탐색하게 되는 node들은 모두 leaf node여야 한다.

=> 여기서 full node는 왼쪽, 오른쪽 자식 노드가 비어있지 않는 상태를 말한다.

=> full node가 아니라면 해당 레벨이 마지막 레벨이거나 마지막 전 레벨일 것이다.

=> 그렇게 되면 다음 노드들은 완전 이진 트리라면 leaf node일 수 밖에 없다.

 

2. 왼쪽 자식 노드가 비어있다면, 오른쪽 자식 노드도 반드시 비어 있어야한다.

=> 완전 이진 트리는 왼쪽 자식 노드부터 채워지기 때문에 왼쪽 자식 노드가 없다면 오른쪽 자식 노드도 없어야한다.

 

---

[오늘의 나는 어땠을까?]

오늘은 일요일이만 평상 시와 똑같이 일찍 강의실에 나와 공부를 시작했다.

어제 야식을 먹고 자서 그런지 피로감이 확 느껴져 아침에 매우 피곤했다.

다시 잠을 자는데 1시간 정도 시간을 썼고 그제서야 몸이 정상상태로 돌아왔다.

점심을 먹은 뒤에는 2시에 그렙(프로그래머스) 코딩테스트를 응시했다.

알고리즘 문제 3문제 중 2.5솔을 했다. 솔직히 문제가 쉽다고 느껴졌는데 내가 그만큼 성장해서 쉽게 느껴진건지 모두가 쉽게 느끼는 건지는 알 수가 없다.

그냥 내가 그만큼 성장했다고 생각하며 앞으로 더 성장해나갈려고 한다.

마지막 문제는 내가 1주차 때 재귀함수로 풀었던 N-Queen문제를 응용하면 풀 수 있었지만 예외처리를 하지못하여 완벽히 풀지 못했다.

코테를 보고난 후 느낀 점은 코딩테스트를 위해서라면 많은 문제들을 풀어보는게 확실히 중요하다는 것이다.

내가 N-Queen 문제를 풀어보지 않았더라면 아마 3번째 문제는 손도 못댔을 것이다.

그래서 남은 알고리즘 주차에는 주어진 문제들 이외에 더 많은 문제들을 풀어볼 생각이다.

 

---

<참고 자료>

https://mhwan.tistory.com/56

https://medium.com/@dltkddud4403/%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EA%B0%80-%EC%99%84%EC%A0%84-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%B8%EC%A7%80-%ED%99%95%EC%9D%B8%ED%95%98%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-615ddc78f39c

https://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/