sm 기술 블로그

트리(Tree) 1개 이상의 유한한 개수의 노드의 집합이다. 루트 노드와 0개 이상의 겹치치 않는 하위 나무 구조들의 집합으로 이루어 졌다. node : 위 그림에서는 a,b,c,d,e,f 이다. edge : 노드를 이어주는 선이다. (정보들간의 관계를 나타냄) path : edge에 의해 연결된 node들의 집합 root node : 최상위 노드(위 그림에서는 A) parent(부모), children(자식), siblin(형제), grandparent(조부모), ancestor(조상) : 각 노드들의 관계 leaf : 자식이 없는 노드 subtree : 큰 트리에 속하는 작은 트리 차수 : 하위 subtree 개수 순회 전위 순위 (Preorder Traverse) : 뿌리를 먼저 방문 0 -> 1 ..

스택(Stack) - LIFO후입 선출(Last In First Out) 데이터를 차곡차곡 쌓아 올린 형태의 자료구조로 데이터가 순서대로 쌓인다. 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조(후입 선출) 삽입(push) | 삭제(pop) 큐(Queue) - FIFO선입 선출(First In First Out) 먼저 들어온 것이 먼저 나가는 선입 선출 구조 삽입(Enqueue) | 삭제(Dequeue)

문제 제기 String s = "(5 + 5)" 다음과 같이 공백과 괄호,숫자,사칙연산이 섞여있는 문자열이 들어왔다. 1. 공백제거 들어온 문자열이 공백을 지니고 있을 가능성이있다. 때문에 공백은 제거해주고, 순수하게 문자들이 문자열을 이룰 수 있도록 해준다. s=s.replace(" ",""); 2. 연산자를 이용하여 문자와 숫자 분리 String[] operands = s.split("[0-9]"); String[] numSt = s.split("[^0-9]"); 연산자 기호는 연산자 를 참고하자. operands(연산자) 안에는 ['(', '+', ')'] 값이 들어간다. 3. 숫자는 int로 변환해 준다. for(int i = 1; i < numSt.length;i++) { numInt[i-1] ..

브루트 포스(brute force) => 너비 우선 탐색(BFS, breadth first search) brute 무식한 force 힘이다. 완전탐색 알고리즘으로 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만을 가져온다. 완전탐색이기 때문에 예외없이 100%확률로 정답만을 출력한다. 문제해결 방법 주어진 문제를 선형 구조로 구조화 구조화된 문제공간을 적절한 방법으로 해를 구성할 때 까지 탐색 구성된 해를 정리한다. 예시 4자리 숫자로 된 핸드폰 암호는 0000~9999까지 총 1만개이다. 이를 하나씩 대입해가면서 핸드폰 암호를 확인하는 것이다. 단점 자원이 문제이다. 위의 예시에서 비밀번호가 한자리가 늘어날 때 마다 기하 급수적으로 차지하는 자원이 많아지며 복잡도가 증가한다.