졸업 신청 까먹은 덕에 청강할 수 있었던 자료구조 강의는 자바로 진행했었다. 같이 청강하고 있던 프로그래밍 연습에서 C를 다루고 있어서 겨우겨우 설명과 슈도 코드만 이해하는 정도로 따라갔다.
다른 분야(네떡, 운영체제 등)과 마찬가지로 정리하지 않았기 때문에 각 자료구조들이 어떻게 생겨먹었는지만 기억나고 전부 휘발되었던...😂

코테를 파이썬으로 푸는게 편해서 마찬가지로 자료구조도 파이썬으로 된 것을 찾고 있었는데 워낙 뭐가 없었다. 그런데 코로나 덕분이라고 해야할지…유튜브에 올라와있는 강의를 발견(아래에 링크)

이번에는 강의 정리하고, 바로 코드치러 갔다.
프로그래머스(Leetcode로 변경)에서 자료구조 문제를 찾아서 같이 풀었다.

+파이썬으로 풀다가 자바스크립트 공부할 겸 자바스크립트로 풀기로…

참고한 강의 링크: https://www.youtube.com/@ChanSuShin/playlists
참고 자료: 개인 자료(자바 자료구조)

영상 속 강의 내용은 아래와 같다.

자료구조, 알고리즘

자료구조? Data Structure라고 하듯이 데이터를 담는 구조를 의미한다. 그럼, 저장공간인 메모리가 있어야 하고, 그 저장된 데이터를 읽고, 쓰고, 삽입, 삭제, 탐색할 수 있어야 한다. 데이터, 메모리, 연산으로 구성된 구조를 자료구조라고 한다. 어렵게 가지 않고, 우리가 코딩을 하면서 선언하는 변수도 자료구조이다.

알고리즘? 그렇게 입력된 데이터(자료)를 가지고 문제를 푸는 논리적인 절차로 유한한 횟수의 연산을 반복하여 정답을 출력하는 것이다. 프로그래밍을 한다는 것은 하나 이상의 알고리즘 구조를 만들어 낸다는 것.

알고리즘 성능 측정과 비교

동일하게 작성한 알고리즘을 어디서 동작시키느냐에 따라서 다르다. 왜? 하드웨어와 소프트웨어 환경은 컴퓨터 마다 다르기 때문이고 동일한 머신이더라도 다양한 크기의 입력이 존재한다.

따라서 성능 측정을 위해서 가정을 하는거야.

동일한 환경 가정

1. Virtual machine

하드웨어와 소프트웨어에 영향을 받지 않는 독립적인 가상컴퓨터가 있다고 하자. 이 머신에서 가상의 언어(pseudo language)로 작성한 가상의 코드(pseudo code)를 실행시키는 것이다.

그럼 가상 컴퓨터 모델은 무엇인가? 현대적인 컴퓨터 모델을 제시한 사람이 폰노이만 교수라서 그 사람의 이름을 따 그 유명한 폰노이만 구조가 있다. 폰노이만 구조는 CPU, 메모리, 입출력 장치, 저장장치가 컴퓨터의 기본 구성 요소임을 설명한다.

(자세한 폰노이만 구조는 운영체제 글에서 설명)

2. Pseudo Language & Code

우리가 정의한 머신이 알아듣는 형태의 언어가 필요하다. 기본연산을 표현할 수 있고 제어문을 작성할 수 있으면 된다. 실제 프로그래밍 언어일 필요는 없음.

• 기본연산? 배정, 대입, 복사, 산술, 비교, 논리, 비트연산이 해당한다.

• 제어문? if문, for문, while문, 함수 정의, 호출, 리턴이 해당한다.

이런 슈도 랭기지로 작성한 코드가 슈도 코드(pseudo code)이다.

그럼 알고리즘이 동작할 환경은 동일한 환경이 되도록 가정했으니, 제한된 인풋이 아니라 다양한 인풋에 대해서 어떻게 성능을 측정할 수 있을 것인가에 대해 생각해봐야 한다.

3. 최악의 입력 가정

알고리즘 수행시간은 최악의 입력에 대한 기본연산 횟수로 정의한다. 다른 어떤 입력이 들어오든 간에 내가 작성한 알고리즘은 그 최악의 횟수 이내에서 이뤄진다.

결국, 프로그램이 잘 디자인 되었다고 하는 그 기준은 효율성이다. 컴퓨터에서 자원을 적게 사용하여 결과를 도출해 내는 것이 효율이라고 할 수 있는데 그럼 어떤 자원일까? 메모리를 더 적게 사용할 수 있겠지. 혹은 계산 시간이 적을 수 있는 것이고. 일반적으로 알고리즘의 효율성을 논할 때는 Running time에 관해서 말한다.

BigO notation

O(N)하도 많이 들어서 귀에 익숙해졌지만...

"너가 지금 작성한 코드 복잡도가 얼마쯤 돼?"

내가 작성한 알고리즘이 어디에 해당하냐고 하면 당황하는게 우선이던...(개인적인 감상입니다)

사실 Big O notation 외에도, 오메가(Ω)와 세타(Θ) 표기법도 있다. 오메가는 알고리즘 실행을 할때 하한(lower bound)을 표현한다. 즉 최선의 경우이자 복잡도계의 낙관론으로 가장 좋은 결과값을 의미한다. 앞서 최악의 가정으로 빅오를 봤었는데 이 빅오와 오메가가 같을 때 세타를 사용한다.

O(1), O(n), O(logn), O(nlogn), O(n²), O(2^N) 등으로 표현할 수 있는데 사실 직접 세보면서 익숙해지는게...

아래 그림은 참고한 강의에서 교수님이 직접 작성하신 식이다.

위에서 A는 임의의 배열이고 그 배열의 길이인 정수 n이 들어올 때 각각의 연산을 얼마나 수행해야 하는지를 빨간색으로 표현해두었다.

각 수행 횟수를 그래프로 그리면 이미지 하단의 그래프가 등장하게 된다. 결국 해당 그래프의 증가율을 결정하는 것은 표현식의 최고차항이 된다. (N을 무한으로 보냈을 경우 다른 요소들은 힘을 못씀) 이를 BigO notation으로 표기하게 되면

• T1(n) ➡️ O(n)
• T2(n) ➡️ O(n)
• T3(n) ➡️ O(n²)

그래서 BigO를 사용하게 되면 절대 이 시간보다 더 걸리진 않는다, 정도로 이해할 수 있고 이는 알고리즘의 시간복잡도를 표현하는 방법 중의 하나이다.

왜인지 매우 급한 마무리.