순차적 자료구조

선형(linear) 자료구조, 순차적(sequential) 자료구조 많이 섞어서 표현하는데, 선형적이라는 표현은 알고리즘의 시간복잡도에서 주로 사용하고, 데이터의 배열과 엑세스 관점에서는 순차적이라는 표현이 더 적절하기에 본 글에서는 "순차적 자료구조"라고 표현함.

1. 배열(Array)

순차적 자료구조에서 가장 기본적인 자료구조이다. C언어에서 배열은 배열에 담을 값의 타입을 명시하며 오른쪽과 같은 형태로 표현된다. int A[4]={2,4,0,5};

따라서 동일한 타입의 변수를 연속적으로 저장할 수 있게 하는 것이 바로 C언어에서 정의하는 배열이다.

대표적인 특징이자 장점은 인덱스를 통해서 원하는 위치에 바로 접근이 가능(random access)하다는 것. 즉 인덱스로 요소에 빈번히 엑세스해야 하는 상황에서 유용한 구조이다.

그러나 배열 중간에 요소를 삽입하고자 하거나, 특히 값을 삭제했을 때는 연속성을 지켜줘야 하기 때문에 추가적인 비용이 발생한다.

---

✋ 파이썬 list 관련 내용 정리하기

왜? 앞으로 자료구조를 파이썬으로 표현하기 위해 주로 사용되는 여러 연산을 확인하고 넘어가려 함.
|
파이썬의 리스트(list)는 배열처럼 인덱스를 통해서 상수 시간에 읽고 쓸 수 있는데 더 많은 연산을 제공한다. 리스트의 값들은 다른 곳에 저장되어 있고 그 값이 저장되어있는 곳의 주소가 실제 리스트의 인덱스에 들어가 있는 구조를 가진다.
L = [1,2,3,4]라는 리스트가 있을 때,
그래서 L[1]에 +1을 하면 원래 2가 3로 변하는 게 아니라 새로운 곳에 3이 생기고 L[1]이 그 3을 가리키게 된다. 즉, 주소값이 변하는 것.

기본 연산

앞으로 다양한 자료구조를 볼 텐데, 기본적으로 삽입, 삭제가 있고 추가적으로 검색이 있을 예정.
A = [1,2,3,4]

• A.append(5): 리스트 A라는 객체에 5를 가리키는 주소공간을 하나 더 붙여라. → [1,2,3,4,5]
• A.pop(): A 맨뒤의 값을 지우고 리턴. 그럼 현재의 상황에서는 5를 가리키는 연결이 끊기고 4번 인덱스에는 아무 것도 들어가지 않은 상태가 된다.
• A.pop(1): A[1]인 2를 제거하고 리턴. 여기서는 뒤에 있는 다른 애들이 한 칸씩 앞으로 밀리는 연산이 들어간다. (시간복잡도 증가)
• 이 외에도 insert, remove, index, count등 다양한 연산이 있다.

Dynamic array

파이썬 리스트에는 이런 연산 외에 특별한 특징이 있는데, 자신의 용량을 자동으로 조절한다.
사실 그게 뭔 대수인가 생각할 수 있겠지만, C에서는 malloc을 통해서 새로운 집을 만들어주고 이사를 시키는 과정이 필요하다.

class

또 파이썬은 객체지향 언어이기 때문에 클래스 개념이 존재한다. 앞으로 자료구조를 구현할 때 클래스를 선언하면서 구현해 나갈 예정이다.

---

2. 스택(Stack)

스택은 마지막으로 들어간 게 가장 먼저 나오는(Last in First out), 입구가 하나인 주머니라고 생각하면 된다. 교수님은 말미잘로 설명하시던..

스택에서 값을 삽입하는 과정을 push, 값을 삭제하는 과정을 pop이라고 한다.

스택 클래스를 만들면서 직접 그 구현이 어떤지 확인할 수 있다.

🤔 '그냥 리스트 사용하면 안 됨?'
사실,,,리스트를 스택으로 사용할 수 있긴 하다. append()하고, pop()만 해주면 되거든. 근데 워낙에 제공하는 연산이 많기 때문에 자료구조 각각의 특성을 구체화하기 위해서 클래스로 선언해서 직접 만들어보려고 한다.

아래는 스택 클래스이다.

class Stack:
    def __init__(self):
        self.items = [] # 데이터 저장을 위한 공간

    def push(self, val): #O(1)
        self.items.append(val)

    def pop(self): #O(1)
        try:
            return self.items.pop()
        except IndexError:
            print("빈 스택!")
            return None 

    def top(self): #O(1)
        try:
            return self.items[-1]
        except IndexError:
            print("빈 스택!")
            return None 

    def __len__(self): #O(1)
        return len(self.items)

이런 스택의 특성을 활용해서 가장 많이 나오는 예제가 괄호 맞추기이다.

👇🏻 아래는 프로그래머스에 있는 스택/큐 문제 세트를 풀어본 코드.

괄호가 잔뜩 있는 문자열이 인풋으로 주어졌을 때 괄호 쌍이 정상적으로 존재하면 true, 그렇지 않으면 false가 리턴되는 문제였다.

괄호 맞추기 코드

def solution(s):
	st = []
	for i in s:
    if i == '(':
			st.append(i)

    else:
      try:
	      st.pop()
      except:
        return False

	return len(st) == 0

---

3. 큐(Queue)

선착순!
먼저 들어온 애가 먼저 나가는 FIFO(First in First out)구조를 가진다.

큐에서는 값 삽입을 enqueue, 값 삭제를 dequeue라고 한다. 큐에서는 어디까지 쌓였는지 확인도 해야 하고 다음에 나갈 인덱스도 알아야 한다.

스택에서 한 것처럼 클래스를 만들면 다음과 같다.

class Queue:
    def __init__(self):
        self.items = []
        self.front = 0

    def enqueue(self, val):
        self.items.append(val)

    def dequeue(self):
        if self.front == len(self.items):
            print("빈 큐!")
            return None
        else:
            x = self.items[self.front]
            self.front += 1 # 앞으로 가리키는 애를 이동시켜주는 방식
            
            if self.front > 0 and self.front == len(self.items):
                self.items = []
                self.front = 0
            return x

실제로는 있지만 없는 것처럼 표현할 수 있다.
선입선출의 특징으로 인해서 일반적으로 대기열을 큐라고 많이 표현한다.

큐는 무슨 문제가 있을까 싶어서 프로그래머스 문제를 푸는데...
사실 여기서부터 음…자바스크립트로 해볼까? 하는 생각이ㅋㅋㅋㅋㅋ

프로그래머스 프로세스 문제

문제: 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

function solution(p, lo) {
	const arr = p.map((el, index) => {
		return {index:index, prior:el};
		});

	const q = []
    
	while (arr.length > 0){
    	let fi = arr.shift();
    	let isHigherThanFi = arr.some(el => el.prior > fi.prior);
      
   		if (isHigherThanFi) {
       		arr.push(fi)
    	} else {
        	q.push(fi)
    	}
	}

	return q.findIndex(el => el.index === lo)+1;
}

파이썬으로 풀다가 '하, 나는 인덱스랑 우선순위가 같이 필요한데...' 고민 끝에 둘 다 사용할 수 있는 자바스크립트로 바꿔서 풀었다. 그런데 파이썬에 enumerate라는 연산이 있었음ㅎ

---

+ 디큐(Dequeue)

스택의 특징과 큐의 특징을 합한 것.

양쪽 끝으로 들어갈 수도 있고 삭제도 양쪽 끝에서 가능하다.
(파이썬에서 deque라는 클래스를 제공한다)

---

연산별 시간복잡도

자료구조	접근	검색	삽입	삭제	메모
배열	O(1)	O(n)	O(n)	O(n)	인덱싱된 데이터에는 효율적
스택	O(n)	O(n)	O(1)	O(1)	마지막 요소 연산에 효율적
큐	O(n)	O(n)	O(1)	O(1)	첫번째 요소 연산에 효율적
디큐	O(n)	O(n)	O(1)*	O(1)*	*양 끝(처음과 끝)에서 둘다 O(1)이다

---

프로그래머스 ➡️ Leetcode로 옮겼다.

원래 초보가 장비탓한다고.

이유를 가져다 붙이자면,

사실 코딩테스트 파이썬으로 푸는 게 훨씬 편하다.

파이썬을 Toy Language라고 하는 지인조차도,
"슬라이싱 때문에라도 코테풀땐 파이썬 씀ㅇㅇ"
라고 할 정도로.

• 근데 나는 자바스크립트 공부를 해야하고
• enumerate, any 이런 거 언제 어디서 쓰면 편할지 고민도 없이 튀어나올 정도로 파이썬 문법을 잘 알진 못하기에.

그래서 자바스크립트로 문제를 푸는데 "다른사람 풀이보기"를 클릭하면 그 커뮤니티 규모가 현저히 작은 것이 느껴진다. 더군다나 다른 사람의 풀이가 코드만 딱 나와있는게 대부분.

리트코드 바로가기: https://leetcode.com/

국내 사이트는 아니다. 해외 코딩 테스트 사이트인데 원조라고 할 수 있음.

고인물들 정말 천지, 그래서인지 각자 solution에 대한 해설이 거의 칼럼 급으로 자세히 달려있어서 공부하기에 프로그래머스보다 편하다.

---

나같은 몽충이에게 딱인 사이트.