유제필의 개발 블로그

요약 수식 계산을 위한 트리 구조로 후위 변환 표기식으로 트리를 구축하고, 중위 표기식으로 변환하여 사용 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 ..

수 정렬하기 2 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 224808 64544 44872 30.458% 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 복사 5 5 4 3 2 1 예제 출력 1 복사 1 2 3 4 5 정답 #include #include #include using namespace std; int main() { ios::sync..

1312번: 소수 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 8432 2518 2252 35.276% 문제 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. 입력 첫 번째 줄에 A와 B(1 ≤ A, B ≤ 100,000), N(1 ≤ N ≤ 1,000,000)이 공백을 경계로 주어진다. 출력 A÷B를 했을 때, 소숫점 아래 N번째 수를 출력한다. 예제 입력 1 복사 25 7 5 예제 출력 1 복사 2 정답 #include using namespace std; int main() { int A, B, N, result; // A, ..

소수(Prime Number)란 소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다. 아래 표는 100 이하의 소수를 나타내는 표로, 1과 자기 자신 말고 약수가 존재하지 않는다. 총 3가지의 방법으로, 일반 반복문, 제곱근, 에라토스테네스의 체를 이용한 방법을 설명한다. 1. 모든 경우의 수를 전부 나누는 방법 O(n) 이 경우는 판단하는 수를 2부터 그 수까지 모두 나누는 방법이다. 모든 값을 하나하나 약수가 있는지 판단하는 알고리즘으로 구현은 쉽지만 시간 복잡도가 O(n)으로 가장 비효율적이다. bool PrimeNumber(int number) { for(int i = 2; i < number; i++) { // 1개라도 나누어 떨어지면 약수가 존재하므로 false if(n..

진법 변환 C++에서 각 진법 변환에 대한 예제이다. 10진수에서 2진수 변환 에제 코드 #include using namespace std; int ToBinary(int number); int main() { int n; cout > n; cout

요약 시간 복잡도 평균 : O(n / m) / 최악 : O(n) 검색하고자 하는 패턴의 마지막 문자부터 앞쪽으로 검사를 진행 일치하지 않는 문자가 있을 경우 Skip 표에 따라 패턴을 옮겨 가면서 검사 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 만들어야 함 문자열의 커서는 앞에서 뒤로, 패턴의 커서는 뒤에서 앞으로 역방향으로 검사 Boyer-Moore 알고리즘이란 Boyer-Moore 알고리즘이란 검색하고자 하는 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 고리즘이다. Booyer-Moore 법은 Brute-Froce나 KMP 보다 효율이 더 우수하기 때문에 널리 사용되는 문자열 검색 알고리즘이다. R.S ..