CS/자료구조

CS/자료구조
[자료구조-4] 그래프(Graph)
그래프 그래프는 정점과 간선으로 이루어진 자료구조입니다. 용어 정점 : 노드(node)라고도 하며 정점에는 데이터가 저장됩니다. (0, 1, 2, 3) 간선 : 링크(arcs)라고도 하며 노드간의 관계를 나타냅니다. 인접 정점 : 간선에 의해 연결된 정점으로 위에서 (정점0과 정점 1은 인접 정점) 단순 경로 : 경로 중 반복되는 정점이 없는 것, 같은 간선을 지나가지 않는 경로 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (정점 0의 차수는 3) 진출 차수 : 방향 그래프에서 한 노드에서 외부로 향하는 간선의 수 진입 차수 : 방향 그래프에서 외부 노드에서 들어오는 간선의 수 그래프 구현 방법 그래프를 구현하는 방법에는 인접행렬와 인접리스트 방식이 있습니다. 인접행렬 방식 인접 행렬은 그..
→2021.11.05
CS/자료구조
[자료구조-3] 선형 리스트(ArrayList), 연결 리스트(LinkedList)
선형 리스트(ArrayList) 데이터를 순서대로 나열해 놓은 자료 구조 메모리에 연속으로 할당되기에 접근 속도가 매우 빠르다. 데이터 삽입, 삭제 시 데이터의 이동이 필요하기에 작업에 소요되는 시간이 길다. 연결 리스트 데이터를 연속적으로 배치시키지 않고 각 자료마다 노드의 포인터 부분을 이용하여 연결시킨 자료 구조 데이터 삽입, 삭제 시 매우 빠르게 처리가 가능하다. 포인터를 찾는 시간이 필요하여 데이터 접근 속도가 느리다. 선형 리스트와 연결 리스트 시간 복잡도 search add remove ArrayList O(1) O(n) O(n) LinkedList O(n) O(1) :맨 앞, 맨 뒤 O(n) : 중간 삽입 O(1) :맨 앞, 맨 뒤 O(n) : 중간 삽입
→2021.11.03
CS/자료구조
[자료구조-2] 스택(Stack), 큐(Queue)
스택 (Stack) 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out) 형식의 자료 구조 자료를 넣는 것을 '밀어넣는다' 하여 push(푸시)라고 한다. 자료를 꺼내는 것을 pop(팝)이라 한다. (※ 이때 꺼내지는 데이터는 마지막에 push한 데이터다) 실생활 예시 : 베스킨라빈스 아이스크림 (아이스크림 통의 마지막에 쌓은 아이스크림부터 먹을 수 있는 구조) 큐 (Queue) 큐는 데이터가 들어오는 위치는 가장 뒤(Back), 데이터가 나가는 위치(Front)는 가장 앞에 있다. FIFO(First In First Out) 형식의 자료구조 입력 : Enqueue or push (맨 뒤로 추가) 제거 : Dequeue or pop (맨 앞의 값을 꺼..
→2021.10.27
CS/자료구조
[자료구조-1] 변수, 배열
안녕하세요. 오늘은 변수(variable), 배열(array)에 대해 배워보려 합니다! 1. 변수 - 하나의 값을 저장할 수 있는 저장 공간 2. 배열 - 배열(array)은 같은 타입의 변수들로 이루어진 유한 집합 사전적 의미는 위와 같습니다. 하지만 위의 의미만 가지고는 바로 이해하기는 어렵겠죠? 변수 컴퓨터는 2진 기본 정보인 0과 1로 이루어져 있습니다. 그래서 컴퓨터의 자료 단위 중 최소 단위가 1bit입니다. 1bit는 0과 1을 표현하는 컴퓨터 메모리 단위 중 가장 작은 단위입니다. 마치 위와 같이 어떤 한 공간에 데이터가 있나(1) 혹은 없나(0)로 데이터를 표현합니다. 그렇다면 위에 말씀드렸듯이 최소 단위가 1bit라면 그 위에 단위들도 있겠지요? 데이터 단위는 아래와 같습니다. 1byt..
→2021.10.26

• 이전
• 1
• 다음