[자료구조 복습3] 연결리스트로 stack 구현하기
스택은 LIFO , "가장 늦게 들어간 요소가 가장 먼저나오는" 데이터 구조이다. 그럼 이 스택을 어떻게 구현할 수 있을까? 아마 첫번째로 떠오르는 것은 배열리스트 일 것이다. 동적으로 배열을 할당받는 방법도 있겠지만, '배열'의 형태로 구현할 경우 어쩔수없이 스택은 저장할 수 있는 자료에 있어서 한계가 있다. 이를 위해서는 '연결리스트'로 스택을 구현해주면 된다. 동적할당된 배열의 형태가 아니라, 연결리스트의 link 필드로, 동적 할당된 요소들을 계속해서 연결시켜주면, 우리는 길이의 제한 없이 스택을 이용할 수 있다. 먼저 소스코드에 구현된 세가지 클래스를 설명한 이미지이다. 이 코드는 세가지의 class로 나뉜다. 1) Node Class: 스택의 'Node'가 될 요소들의 데이터와 요소들을 이어줄..
[자료구조 복습2] Array List와 Linked List (단순, 원형,이중)
리스트에는 두가지 종류가 있다. 배열리스트와 연결리스트이다. 배열리스트는 말 그대로 '배열'을 이용하여 리스트를 구현한 것이고, 연결리스트는 포인터를 이용하여 리스트를 구현한 것이다. - 배열 리스트의 장점은 원하는 원소를 O(1) 시간으로 찾을 수 있다는 것이다. 하지만 단점은 원소의 개수가 제한되어 있다는 것, 삽입과 삭제가 까다롭다는 점이다. 아무리 탐색에서 O(1)로 효율적이더라도 , 삽입과 삭제에서 O(n)이 걸리므로 그다지 효율적이라 하지 못하겠다. 하지만 그럼에도 불구하고 배열리스트는 리스트 내의 변동 사항이 없고, 리스트의 크기가 클 때 사용하면 효율적일 것이다. 다음은 배열리스트 ADT를 C++로 구현한 것이다. 예외처리는 객체 참조자를 반환해야하는 함수에만 해주었다. 배열리스트 C++ ..
[자료구조 복습1] Array- 다항식 계산 , 희소행렬
자료구조를 처음 배운지 꽤 오래지났다. 그래서 그런지 몇몇 개념들은 희미해졌고 많이 까먹기도 했다. 그 동안 복습을 제대로 안한 문제도 있을 것이라 생각한다. 그래서 2020 상반기의 가장 큰 목표 중 하나를 자료구조 과목을 제대로 복습하는 것이다. 나는 처음 자료구조를 C언어 쓰여진 책으로 배웠지만, 그 책을 바탕으로 이제는 C++로 구현해보고자 한다. C++에 대한 이해도가 높지 않아 실수가 많기때문에 지적이나 조언은 언제나 환영이다! - 다항식 계산 #include using namespace std; #define MAX_ARR 101 int MAX(int a, int b) { if (a > b) return a; else return b; } class polynomial { //coef와 ex..
Git 기초지식 01 / branch의 기초
이 글은 생활코딩 GIT CLI 강의를 바탕으로 쓰여졌습니다. branch의 뜻은 '가지'이다. 즉, 같은 버전 아래에서 여러가지의 '가지'를 친다고 생각하면 된다. 예를들면 manual 이라는 파일을 생성했을 때 , apple, google, ms가 이 manual의 일부 내용을 공유한다고 하자. 하지만 당연히 apple에만 있는 내용이 있을 것이고, google에만 있는 내용이 있기마련이다. 그렇다고 apple manual 따로, google maunal 따로 ms manual 따로..이런식으로 할 순 없다. 너무 복잡하기 때문이다. 이를 위한 기능이 바로 'branch'이다. 특정 버전에서 가지처럼 갖가지 다른 내용들이 생성되는 것이다. 그리고, 각각의 가지들은 일부분을 공유하지만, 서로의 영역에 ..