핀아의 저장소 ( •̀ ω •́ )✧

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉 1️⃣ 수식의 후위 표기법 (Postfix Notation) 우리가 일상에서 사용하는 수식의 표기법은, 중위 표기법 (infix notation) 이라고 부를 수 있다. 두 개의 피연산자 A 와 B 를 가지고 덧셈을 하는 수식을 표기하면 A + B 와 같이 되는데, 이 때 연산자인 + 가 두 피연산자의 사이에 (가운데에) 위치하기 때문에 중위 표기법이라고 부른다. 그렇다면 후위 표기법이란 무엇일까? 연산자를 두 피연산자의 뒤에 쓰는 방식이다. 따라서 앞의 예인 A + B 를 후위 표기법으로 표기하면 AB+ 가 된다. ✅ 중위 표현식 → 후위 표현식 1. 예시 A * B + C 2. 예시 A + B * C 3. 예시 ..

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉 마치 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조를 스택 (stack) 이라고 부른다. 이처럼 마지막에 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 스택을 다른 말로는 후입선출 (LIFO; last-in first-out) 자료 구조라고도 한다. 스택에 데이터 원소를 추가하는 (집어넣는) 동작을 푸시 (push) 연산이라고 하고, 마지막에 추가되었던 원소를 참조하고 삭제하는 (꺼내는) 동작을 팝 (pop) 연산이라고 한다. 스택은 이 두 연산을 제공하는 간단한 자료 구조인데, 여러 가지의 알..

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉 지금까지의 연결 리스트에서는 링크가 한 방향으로, 즉 앞에서 뒤로, 다시 말하면 먼저 오는 데이터 원소를 담은 노드로부터 그 뒤에 오는 데이터 원소를 담은 노드를 향하는 방향으로만 연결되어 있었다. 이번에는 새로운 연결 리스트로서 양방향 연결 리스트 (doubly linked list) 를 살펴보고자 한다. 말 그대로, 양방향 연결 리스트에서는 노드들이 앞/뒤로 연결되어 있다. 즉, 인접한 두 개의 노드들은 앞의 노드로부터 뒤의 노드가 연결되어 있을뿐만 아니라, 뒤의 노드로부터 앞의 노드도 연결되어 있다. 한 노드의 입장에서 보자면, 자신보다 앞에 오는 노드를 연결하는 링크와 자신보다 뒤에 오는 노드를 연결하는 링크..

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉 추상적 자료구조(Abstract Data Structures) Data ex) 정수, 문자열, 레코드.... A set of operations 삽입, 삭제, 순회... 정렬, 탐색... 데이터 원소들을 순서를 지어 늘어놓는다는 점에서 연결 리스트 (linked list) 는 선형 배열 (linear array) 과 비슷한 면이 있지만, 데이터 원소들을 늘어놓는 방식에서 이 두 가지는 큰 차이가 있다. 구체적으로는, 선형 배열이 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라고 한다면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다. 그렇다면, 선형 배열에 비해서 연결 리스트가 가지는 이점은 무엇일..

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉 물론, 간단한 알고리즘도 있고 복잡한 알고리즘도 있다. 하지만, 알고리즘의 "복잡도" (complexity) 라고 부르는 것은 문제 풀이의 방식이 얼마나 복잡하냐 단순하냐를 나타내는 말이 아니다. 알고리즘이 실행함에 있어, 문제의 크기 (일반적으로 데이터 원소의 개수를 뜻합니다) 가 커짐에 따라서 얼마나 큰 시간을 (또는 공간을) 요구하느냐를 뜻한다. 알고리즘의 시간 복잡도는 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 시간이 어떤 양상으로 증가하는가를 다룬다. 공간 복잡도는 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 기억 공간 (메모리) 의 필요가 어떤 양상으로 증가하는가를 다룬다. 알고리즘의 복잡..

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉 재귀 함수(Recursive Functions) 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것 ex) 이진 트리(binary trees) 알고리즘들 중에는, 재귀 알고리즘 (recursive algorithm) 이라고 불리는 것들이 있다. 이것은 알고리즘의 이름이 아니라 성질이다. 주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용해서, 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법이다. 예를 들면, 1 부터 n 까지 모든 자연수의 합을 구하는 문제 (sum(n))는, 1 부터 n - 1 까지의 모든 자연수의 합을 구하는 문제 (sum(n - 1))..