유제필의 개발 블로그

요약 수식 계산을 위한 트리 구조로 후위 변환 표기식으로 트리를 구축하고, 중위 표기식으로 변환하여 사용 1개의 연산자와 2개의 피연산자를 요구함 피 연산자는 잎 노드임 연산자는 뿌리 또는 가지 노드임 뒤에서부터 역순으로 계산이 되어야 함 뒤에서부터 1개씩 토큰을 확인해 연산자인지 피연산자인지 확인 수식 트리(Experssion Tree) 수식 트리란 이름 그대로 수식을 표현하는 트리이며, 수식 이진 트리라고도 한다. 하나의 연산자가 2개의 피연산자를 취한다는 가정 아래, 수식 트리는 일반적으로 2가지의 규칙을 가진다. 피연산자는 잎 노드이다. 연산자는 뿌리 노드 또는 가지 노드이다. 예를 들어 아래와 같은 수식이 있다. (1 * 2) + (7 - 8) 피연산자 1, 2, 7, 8은 모두 잎 노드이고, ..

요약 트리 구조에서 하나의 노드가 자식 노드를 2개까지 가질 수 있는 트리 구조 포화 이진 트리와 완전 이진 트리 구조로 나뉨 높이에 따라 높이 균형 트리와 완전 높이 균형 트리 구조로 나뉨 노드 방문 순서에 따라 전위 순회, 중위 순회로 나뉨 트리 소멸 시 잎 구조부터 제거해야 하며 후위 순회 방식으로 제거해야 이진 트리(Binary Tree) 이진 트리란 일반 트리와 개념은 같지만, 하나의 노드가 자식 노드를 2개까지만 가질 수 있다는 점이 다르다. 이진 트리라는 이름도 자식을 둘만 가진다는 의미에서 붙어진 이름이다. 아래 그림이 이진 트리의 구조를 개념적으로 표현한 그림이다. 이진 트리의 종류 이진 트리의 가장 중요한 부분은 노드의 최대 차수가 2라는 사실이다. 즉, 모든 이진 트리 노드의 자식 수..

트리(Tree)란 트리는 그 이름에서 알 수 있듯이 나무를 닮은 자료구조이다. 실생활에서 이러한 구조를 많이 사용하는데, 의사 결정 트리, 스킬 트리 등 여러 방면으로 많이 사용한다. 컴퓨터 과학에서도 활용도가 매우 높다. HTML, XML 문서를 다룰 때 사용하는 DOM, PC 폴더 구조, 운영체제 파일 시스템 등도 트리 구조로 이루어져 있다. 트리의 구성 요소 트리는 크게 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어져 있다. 뿌리, 가지, 잎은 모두 똑같은 노드이지만 트리에서 어디에 위치하는지에 따라 불리는 이름이 달라진다. 뿌리는 트리 자료구조의 가장 위에 있는 노드를 가리키고, 가지는 뿌리와 잎 사이에 있는 모든 노드를 말한다. 그리고 가지의 끝에 있는(마지막) 노..

이진 탐색 트리 요약 시간 복잡도 : O(log(n)) ~ O(n) 왼쪽 하위 트리는 루트보다 작은 값이 위치함 오른쪽 하위 트리는 루트보다 큰 값이 위치함 정렬되어 있는 트리 구조에서 빠른 탐색 속도를 보임 한쪽으로 편향되어 있는 트리 구조에서 비효율적임 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리란 트리 내부에 있는 노드의 값을 찾는 방법으로 아래와 같이 3가지의 조건을 만족하면 된다. 각 노드는 왼쪽 자식 노드보다 큼 각 노드는 오른쪽 자식보다 작음 같은 키 값을 갖는 노드는 없음 위 그림은 이진 탐색 트리를 구현한 예이다. 여기서 노드 5를 보면 왼쪽 하위 트리 노드(4, 1)은 모두 5보다 작다. (조건 1번에 해당) 그리고 오른쪽 하위 트리 노드(7, 6, 9)는 모두 ..

1181번: 단어 정렬 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 118771 49332 36826 40.113% 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 예제 입력 1 복사 13 but i wont hesitate no more no more it ..

시퀄라이즈(Sequelize)란 시퀄라이즈란 노드에서 MySQL 작업을 쉽게 할 수 있도록 도와주는 라이브러리이다. 시퀄라이즈는 ORM(Object-Reational Mapping)으로 분류된다. 여기서 ORM은 자바스크립트 객체와 데이터베이스의 릴레이션을 매핑해주는 도구이다. 시퀄라이즈의 가장 큰 장점은 자바스크립트 구문을 알아서 SQL로 바꿔주는 부분이다. SQL 언어를 직접 사용하지 않아도 자바스크립트만으로도 MySQL을 조작할 수 있다. 아래 예제에서는 users 테이블과 comments 테이블을 만들어 MySQL 데이터베이스에 저장하는 예제이다. 테이블 관계 정의하기 먼저 테이블 관계를 보면 일대다(1:N), 일대일(1:1), 다대다(N:N) 관계가 있다. 게시판을 예로 들때 아래와 같이 정의할..

CRUD(Create Read Update Delete)란 CRUD란 Create, Read, Update, Delete의 첫 글자를 모아 만든 두문자어이며 데이터베이스에서 많이 수행하는 4가지의 작업을 말한다. 이 예제에서는 testmysql 데이터베이스 내 users Table과 comments Table이 있다. mysql> SHOW TABLES; +---------------------+ | Tables_in_testmysql | +---------------------+ | comments | | users | +---------------------+ 2 rows in set (0.00 sec) mysql> DESC users; +------------+--------------+------+..

MySQL을 프롬프트와 Workbench로 실행하는 예제이다. 프롬프트로 하는 예제 데이터베이스 실행 먼저 MySQL을 프롬프트로 실행하는 방법이다. 프롬프트 실행 후 MySQL이 설치되어 있는 폴더 내 bin 폴더로 이동 후 MySQL을 실행한다. cd C:\Program Files\MySQL\MySQL Server 8.0\bin mysql -h localhost -u root -p Enter password: [비밀번호 입력] 입력 후 아래와 같은 문구가 나온다면 MySQL이 성공적으로 실행 되었다. 데이터베이스 생성하기 먼저 데이터베이스를 생성하기 위해 CREATE SCHEMA [데이터베이스 명]을 실행해야 한다. MySQL에서 데이터베이스와 스키마는 같은 개념으로, 데이터베이스를 생성하는 명령어이..

리눅스에서 기본으로 제공하는 텍스트 에디터다. 텍스트 에디터란 문자 기반으로 파일을 생성하고 수정할 수 있는 프로그램이다. ​ vi에디터는 UC 버클리의 BSD 유닉스용으로 개발되었지만, 거의 모든 유닉스에서 기본적으로 제공되고 있다. vi 에디터가 개발되었던 초기의 컴퓨터(ADM-3A)는 방향키가 없고 키 배치도 현재 컴퓨터와 달라서 지금 사용하기에는 불편하다. 그래서 리눅스에서는 기존의 vi를 보다 편하게 사용하도록 성능을 개선한 vim(vi improved)을 사용한다. ​ $vi [{파일명}+] $ vim [{파일명}+] ​ vi 에디터의 모드 vi 에디터는 크게 세 가지 모드를 가진다. 처음 실행하면 명령 모드로 실행된다. vi 에디터는 입출력 장치의 느린 속도 문제를 해결하기 위해 버퍼를 사용..

nano 에디터는 비교적 가볍고 사용하기 쉬운 텍스트 에디터로 vi 에디터에 비해 직관적이며 사용하기 쉽지만, 다양한 기능을 지원하지 않는 단점이 있다. nano 에디터는 문서의 내용을 구분하기 위해 색상 등을 기본적으로 제공한다. ​ $ nano [{파일명} +] ​ 명령어 설명 Ctrl + X 에디터 종료 Ctrl + K 현재 편집하고 있는 줄을 삭제하거나 잘라내기 Ctrl + U 잘라낸 자료 붙여넣기 Ctrl + ^ 블록 단위 복사, 블록 단위 해제 Ctrl + W 현재의 문서에서 원하는 내용에 대한 찾기 기능 Ctrl + G 도움말 출력 Ctrl + O 저장 및 덮어쓰기 Ctrl + R nano 내에서 다른 파일 열기 Ctrl + V Page Down (한 화면 앞으로 이동) Ctrl + Y Pa..