C언어 기초 문법 C는 아주 오래되고 전통적인 순수 텍스트 기반의 언어이다. 다음 창의 언어를 이해해보자. #include int main(void) { printf("hello, world\n"); } int main(void){} '시작한다'의 의미. 앞으로 작성할 코드 모두는 이 int main(void) { }의 중괄호 사이에 작성하게 된다. printf(); 스크래치의 “‘say” 블록과 같은 역할 문자열을 적을 때에는 언제나 텍스트를 " " 쌍따옴표로 감싼다. 일상에서 문장의 끝에 마침표(.)를 붙이는 것 처럼 C에서는 세미콜론(;)을 붙여야 한다. \n 줄바꿈. 키보드의 enter와 같은 기능 #include “stdio.h”라는 이름의 파일을 찾아서 “printf” 함수에 접근할 수 있도록..

CS50 Sandbox * CS50 강좌내 실습에서 사용되는 CS50 Sandbox : https://sandbox.cs50.io CS50 Sandbox Temporary programming environments for students and teachers. sandbox.cs50.io CS50 Sandbox에서 파일 생성하기 1. 왼쪽 상단에 있는 + 버튼을 클릭 2. 파일이름을 입력하고 Create File을 클릭 이 때 C의 확장자인 .c를 꼭 끝에 적어주어야 한다. 3. 왼쪽에 필요한 코드를 작성한다. 4. clang 파일이름.c 를 실행 실행이 되었다면 아래처럼 왼쪽에 a.out이 생성됨 보이지 않으면 → 폴더모양의 아이콘 클릭 5. 결과 파일 이름을 실행하면 아래에 결과 값이 출력됨 컴파..

Bit vs Byte Bit 비트 정보를 저장하고 연산을 수행하기 위해 컴퓨터가 쓰는 측정 단위 이진 숫자라는 뜻을 가진 “binary digit”의 줄임말 0과 1, 두 가지 값만 가질 수 있는 측정 단위 디지털 데이터를 여러 비트들로 나타냄으로써 두 가지 값만을 가지고도 많은 양의 정보를 저장할 수 있다. 또한 컴퓨터는 저장되어 있는 데이터를 수정하기 위해 비트에 수학적 연산을 수행할 수 있다. Byte 바이트. 비트열의 일종 비트 한 개는 많은 양의 데이터를 나타내기에 부족 → 여러 숫자 조합을 컴퓨터에 나타내기 위해 나온 것이 비트열 바이트(byte) : 여덟 개의 비트가 모여 만들어진 것 하나의 바이트에 여덟 개의 비트가 있기 때문에 2^8 = 256 개의 서로 다른 바이트가 존재할 수 있다. ..

DFS와 BFS 자료구조로 개념을 익혔다 해도 코딩테스트 문제 풀이에 적용하는 것이 처음에는 쉽지 않은데, 계속 풀다 보니 전형적인 풀이 패턴을 발견할 수 있었다. 따라서 기본적인 BFS, DFS 구현 코드를 정리해보고자 한다. 📌 결국 DFS, BFS의 기본 작동 원리는 탐색 시작 노드 방문+방문 처리 → 인접 노드 방문+방문 처리이다. (*방문 처리를 하는 이유 : 같은 노드를 중복해서 방문하지 않기 위함) 📌 단, LIFO(Last-In First-Out)인 stack과 stack memory를 활용하는 recursion(재귀) ↔ FIFO(First-In First-Out)인 queue의 특성이 각기 다른 알고리즘으로 귀결된다고 이해하면 쉽겠다. 개념 DFS란? Depth-First Search ..

Red Black Tree 레드 블랙 트리 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을때 Θ(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. 모든 노드가 빨간색 혹은 검은색인 이진 탐색 트리 모든 속성은 Extended Binary Search Tree*를 기반으로 한다 : 각 Null 포인터는 외부 노드(External node)로 바뀜 Black child(외부 노드 포함)에 대한 포인터는 검은..

이진검색트리는 저장과 검색에 평균 Θ(log n)시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 **균형잡힌 이진검색트리(Balanced Binary Search Tree)**이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 AVL트리와 레드블랙트리다. AVL Tree Adelson-Velsky and Landis Tree 극단적으로는 n개의 노드가 크기 순으로 일렬로 늘어뜨려져 높이 또한 n이 되는 경우도 이진 탐색 트리에 해당된다. 결과적으로 이진 탐색 트리의 계산복잡성은 O(n)이 되는데, 이것으로는 탐색 속도가 O(..

💡 이진 탐색 트리는 이름에서 알 수 있듯이, 삽입이나 삭제보다는 탐색에 주 목적을 둔 자료구조이다. Search Tree 탐색 트리 skip lists와 hash table들과 같거나 그 이상의 성능을 가짐 사전을 구현하는 데에 이상적인 구조 순차적 또는 등급별 데이터 접근에 이상적 💡 빈출! 이진 트리와 이진 탐색 트리의 차이점 - 이진 트리 : 노드의 최대 Branch가 2인 트리 - 이진 탐색 트리 : 이진 트리에 추가적인 조건이 있는 트리 ⇒ 조건 : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음. Binary Search Tree 이진 탐색 트리 이진 탐색 트리는 트리가 비어있지 않은 경우 다음과 같은 속성을 만족한다. 모든 노드 x에 대하여,오른쪽 서..

Threaded Binary Tree의 특징 트리의 노드는 순서대로 채워진다. 트리의 다른 노드에 대한 thread라는 포인터로 null 링크를 변경한다 자식 노드와 연결되지 않는 링크는 중위 선행자 (Inorder Predecessor) 또는 중위 후행자 (Inoder Successor)와 연결된다. 중위 선행자 또는 중위 후행자가 없는 노드의 링크는 가상의 노드 head를 가리킨다. 장점 : 트리 전체의 모든 링크를 활용한다. 중위 순회의 편의성이 증대된다. Thread의 이용 ptr -> leftChild = null인 경우, ptr → left_child를 ptr의 중위 선행자를 가리키도록 변경 중위 선행자(Inorder Predecessor): 해당 노드 바로 앞에 나온 노드 ptr -> rig..