자료구조5

• 

  [CS] 자료구조/알고리즘 관련(작성중...) 정렬 알고리즘 시간/공간 복잡도 Array vs LinkedList Array은 메모리상에 순서대로 데이터 저장 => 캐시의 지역성으로 인해 상대적으로 빠른 탐색 수행 인덱스로 조회할 수 있음 => 인덱스 조회 성능 높음 LinkedList는 다음 데이터의 위치에 대한 포인터를 가지고 있음 중간에 데이터를 삽입, 삭제하는 것이 용이 List vs Set List는 중복된 데이터를 저장하고 순서를 유지하는 선형 자료구조 Set은 중복되지 않은 데이터를 저장하고 순서 유지X, 선형 자료구조 Hash Function, Hash Table 해시 함수(특정 알고리즘)를 통해 key값을 해쉬 코드(작은 범위의 숫자)로 변환한다. key 값 과 해쉬 코드가 1:1 매칭이 되는 경우는 해쉬를 사용하는 의미가 없어짐, .. TIL/TIL 2022. 9. 26.

• 

  210624 그래프(Graph) 그래프(Graph) : 연결되어 있는 개체간의 관계를 표현하는 자료 구조 트리도 그래프의 일종이라고 볼 수 있다. 그래프의 용어 그래프는 ( V , E ) 으로 표시됨 V는 정점(vertices)들의 집합 E는 간선(edge)들의 집합 정점과 간선은 모두 관련되는 데이터를 가질 수 있음 ( ex - 정점은 도시의 이름 간선은 도로의 길이 등 ) 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in - degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out - degree) : 방향 그래프에서 외부로 향하는 간선의 수 단순 경로(simple path) : 경로 중에서 .. 미가공 필기(알고리즘) 2021. 6. 24.

• 

  210624 트리(Tree) 트리(Tree) : 계층적인 구조, 노드들로 구성됨, 노드들이 부모 자식 관계 가짐 트리의 용어 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자식들로 이루어진 트리 단말노드(terminal node) : 자식이 없는 노드 비단말노드(non-terminal node) : 적어도 하나의 자식을 가지는 노드 레벨(level) : 트리의 각층의 번호 높이(height) : 트리의 최대 레벨 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 이진 트리(binary tree) : 모든 노드가 2개의 서브 트리를 가지고 있는 트리 노드에는 최대 2개까지의 자식 노드 존재 모든 노드의 차수 2개 이하가 되어 구현하기 편리 노.. 미가공 필기(알고리즘) 2021. 6. 24.

• 

  210624 스택(Stack) 과 큐(Queue) 스택(Stack) : 접시를 쌓듯이 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 top의 위치에서만 원소를 삽입/삭제하기 때문에 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이며 마지막에 삽입한 원소가 가장 먼저 삭제된다. 그래서 후입선출(LIFO , Last In First Out) 구조라고 함 스택의 연산으로는 대표적으로 삽입 연산 : push 삭제 연산 : pop 이 존재하고 조회하는 peek 등 존재함 스택을 응용하는 예시로 시스템 스택이 있음 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로 스택을 이용하여 수행순서 관리하는 것. 실행 순서를 복기하면, 프로그램이 실행을 시작하면 메인 함수가 실행되.. 미가공 필기(알고리즘) 2021. 6. 24.

• 

  210623 알고리즘 자료구조란? 컴퓨터에서 어떤 문제를 해결하기 위해 자료의 특성에 따라서 자료를 분류하여 구성하고 저장해 놓은 것 자료구조의 형태 단순 구조 - 정수, 실수, 문자, 문자열 선형 구조 - 순차 리스트, 연결 리스트, 스택, 큐, 덱 비선형 구조 - 트리, 그래프 파일 구조 - 순차 파일, 색인 파일, 직접 파일 알고리즘이란? 알고리즘은 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술한 명세서 알고리즘의 표현 방법 자연어를 이용한 서술적 표현방법 순서도를 이용한 도식화 표현방법 프로그래밍 언어를 이용한 구체화 방법 가상코드를 이용한 추상화 방법 알고리즘과 프로그램의 차이는? 알고리즘은 어떤한 문제에 대한 해결 방법, 프로그래밍 언어, 컴파일러, 시스템에 비의존적 프로그램은 알고리즘을 구현하여 문제를.. 미가공 필기(알고리즘) 2021. 6. 23.