전체 글

0. Array and List 배열은 뭐고 리스트는 뭘까? 그리고 배열이 있는데 리스트를 써야하는 이유는 무엇일까?  0.1 Array 배열은 선형적인 자료구조 중의 하나로 데이터를 일렬로 늘여 놓은 형태의 자료구조입니다. 어떤 언어를 배우던 가장 기본적으로 배우게 되는 메모리 공간 형태이며, 자료형(Data Type)이 둘 이상의 값을 저장할 수 없습니다.(다만, Python 제외)  0.2 List 리스트도 배열과 마찬가지로 선형적인 자료구조 중의 하나입니다.  하지만 배열과 달리 길이가 가변적입니다. 이를 동적할당(Dynamic allocation)이라고 합니다. 또한 배열과 달리 메모리 공간상에 연속적으로 나열되어 할당되지 않고 주소(reference) 를 통해 데이터들이 연결되어있는 형태입니다..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Binary Search Tree Definition Node contains key which can make us identify from other nodes There is one Root node(unless empty BST, but if there is Dummy data in Root, we do not have to take care of it Root node may have "two" child node(s) Each child is the root node of its subtree Each subtree is itself a BST The key values in left subtree are all smaller t..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. LinkedList LinkedList 는 Node 들로 구성되어있는 자료구조입니다. 노드는 저장요소들의 단위로 노드들을 포인터를 통해 서로 연결되어있습니다. 그래서 연결 리스트라 불립니다. 연결 리스트의 구조는 다음과 같습니다. 연결 리스트에는 head 라는 포인터를 통해 처음 요소를 가르킵니다. 또한 마지막 노드의 next 포인터는 null 값을 가르킴으로써 마지막 요소임을 나타냅니다. #include class Node{ public: Node(int data) : data{data}, next{NULL}{}; ~Node(){ std::cout data == x) return 1; else if((*l)->data < x){ *p = ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Definition of Equivalance Relation Given a set A, a Relation on A is any subset of AxA There is a Relation R which is a Relation on A. for example, A = {1,2,3,4} , R = {(1,3), (3,4), (1,1), (2,2)} We can write 1R3 to mean (1,3) ∈ R An extreme example There is a Relation '

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Queue and Stack 0.1 Queue Insert 와 Delete 만을 제공하는 자료구조 입니다. Queue 의 매우 주요한 특징으로는 FIFO(* First In First Out) 입니다. 앞서 봤던 Sorted Packed Array 같은 자료구조들과 달리 LinkedList 를 기반으로 합니다. LinkedList 의 특징을 통해 Queue 의 각 수행들은 매우 빠른 성능을 보입니다. 실제로 빨라야 하는 수행이기도 합니다. Queue 는 생각보다 많은 곳에 쓰이지는 않지만 알고있으면 유용한 순간들이 있습니다. 0.1.1 성능 Insert : O(1) Delete: O(1) 0.2 Stack Queue 와 마찬가지로 Inser..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 배열로 입력이 들어오고 하나 하나 찾아가는 느낌이 그래프와 BFS 로 풀면 되겠다고 생각했습니다. 토마토는 익은 토마토 주변 상하좌우로 안 익은 토마토들을 익게 만드는 것 또한 BFS 라고 생각했습니다. 여기에서 문제는 끝까지 탐색했을 때 모든 토마토가 안 익는 경우가 생기고 이를 어떻게 일반적인 경우와 구분할 것 인지 탐색이 끝까지 진행 되었을 때 며칠이 지났는지 어떻게 알 수 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 리스트를 만들어 요소들을 저장하고 각 명령에 맞게 리스트의 값들을 수정하는 문제입니다. 해당 문제에는 2 가지의 명령이 있습니다. R: 배열의 순서를 뒤집습니다. D: 가장 앞에 요소를 삭제합니다. 만약 배열에 요소가 없을 때, D 명령을 수행하려 하면 error 를 출력하고 아닐 경우는 결과 배열을 출력합니다. 특이한 점은 배열의 요소들을 입력해줄 때 [ ] 를 포함하여 입력해준다는 점 입니다. [ ] 처리를 잘 하는 것이 중요해보입니다. 또한 R 연..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. String Matching 긴 텍스트형식의 문자열에서 패턴을 찾아주는 것을 말합니다. 생각보다 실생활에 많이 쓰입니다. 워드에서 ctrl+F 를 통해 원하는 단어를 찾는 것웹 페이지에서 원하는 검색어를 갖는 페이지를 찾아주는 것생명공학에서 DNA 염기 서열 중 원하는 염기 서열을 찾아주는 것etc...String Matching 에 사용되는 용어들과 문제를 재정의 해보겠습니다. Text : Simple String of CharactersPattern : Simple String of Characters to findTo Do : Find where in the Text the Pattern is 0.1 알고리즘 알고리즘시간 공간Naive..