데이터구조와 알고리즘 (12) 썸네일형 리스트형 데이터구조 - Queue 큐 데이터구조 - 트리 트리구조 나뭇가지가 가지를 치며 뻗어나가듯한 모양으로 데이터를 저장하는 방식 나무를 뒤집어 놓은 모양으로 데이터 구조가 저장된다 명칭 노드 (node) : 트리구조를 형성하는 요소 엣지 (edge) : 노드와 노드를 연결하는 선. 가지(branch) 루트 노드 (root node) : 최상위 노드 리프 노드 (leaf node) : 하위 노드(자식노드)가 없는 최하위 노드 트리 깊이 : 루트노드에서 리프노드까지 거쳐야하는 단계의 개수 트리구조 종류 이진트리 (binary tree) : 하위 노드 개수가 2개로 제한한 트리구조 N항트리 (N-ary tree / N-way tree) : 하위 노드 개수가 3개 이상인 트리구조 AVL 트리 (Adelson-Velskii and Landis' tree) 루트 노.. 알고리즘 - 검색(선형검색, 이진검색) 선형검색 구분 내용 특징 처음부터 순서대로 하나씩 찾는 방식 장점 작동방식과 구현이 단순하다 단점 -모든 데이터를 조사한다 -데이터 개수에 검색시간이 비례한다 -비효율적인 방식 ex.100만개의 대상 중에서 찾는 값이 100만번째에 있다면 100만번째에 이르러서야 찾을 수 있다 알고리즘 효율 구분 내용 최대 검색횟수 O(n) 평균 검색횟수 n/2회 이진검색 이진검색은 트리구조에 대해 알고 있으면 좋다. (☞데이터구조 - 트리) 이진검색은 다음과 같이 이루어진다. 만약 '6' 의 위치를 알고자 한다. 먼저 루트노드의 값과 비교하여 좌측인지 우측인지 확인한다. 예시의 경우 오름차순이므로 찾으려는 값 6은 루트노드의 값 5보다 우측에 위치한다. 좌측은 확인할 필요가 없다. 루트노드의 우측 자식노드의 값은 7이.. 알고리즘 - 알고리즘의 기초(빅오표기법) 효율적인 알고리즘이란 계산량 고려하기 시간계산량 --> 시간이 얼마나 적게 걸리는가 공간계산량 --> 기억용량(메모리)을 얼마나 적게 사용하는가 시간계산량과 공간계산량 둘다 최소로 하는 것은 무리가 있다. 일반적으로 시간계산량이 적도록 구성하면 공간계산량이 증가하고, 반대도 마찬가지이다. 이는 마치 효과성과 효율성을 모두 잡겠다는, 그럴듯하지만 실현불가능한 목표와 같다. 일반적으로 계산량 확인은 시간계산량을 고려하게 된다. 시간소요 줄이기 소요되는 시간은 cpu 성능에 따라 차이가 있을 수 있기 때문에 스텝의 개수로 판단한다 스텝은 수행되는 단계라고 보면 된다. 시간계산량은 계산에 걸리는 복잡한 정도를 따진다. 계산이 복잡해질수록 단계도 많아지고 각 단계를 처리하는데 걸리는 시간도 증가하게 될 것이다. .. 이전 1 2 3 다음
