자료구조

[자료구조] 그래프(Graph)

그래프?그래프는 정점(Vertext)의 집합과 간선(Edge)의 집합으로 이루어진 자료구조정점의 집합을 V, 간선의 집합을 E, 그래프를 G 라고 했을 때 G = (V,E)이다정점은 위치를 의미, 간선은 정점과 정점을 연결하는 선을 의미그래프 트리 그래프트리방향성방향 그래프 or 무방향 그래프방향 그래프순환성순환 및 비순환비순환루트 노드 존재 여부루트 노드가 없음루트 노드가 존재노드간 관계성부모와 자식 관계 없음부모와 자식 관계모델의 종류네트워크 모델계층 모델그래프 용어 그래프에만 쓰이는 몇 가지 기술 용어가 있다각 노드를 정점(Vertext)정점을 잇는 선도 그래프 용어로 간선이라 부른다간선으로 연결된 정점은 서로 인접하다(Adjacent)인접한 정점을 이웃 = neighbor모든 정점이 서로 연결된 ..

[자료구조] 완전탐색 (Exhaustive search)

완전탐색 (Exhaustive search) ⇒ 모든 가능한 경우의 수를 탐색 하여 최적의 결과를 찾는 방법 모든 알고리즘 문제에서 가장 중요한 것 → 정확한 답 → 가장 확실한 방법 및 컴퓨터의 빠른 연산속도를 활용하는 가장 좋은 접근 방법 문제를 처음 접하면 반드시 완전탐색으로 풀 수 있는가를 생각해 보자. 모든 문제에서 완전탐색으로 답을 내지 못 한 문제는 복잡도를 더 이상 줄일 수 없기 때문이다. 완전탐색 종류 알고리즘 종류 설명 장점 단점 브루트 포스 ‘모든 경우의 수를 탐색’하면서 원하는 결과를 얻는 알고리즘을 의미. 가능한 모든 경우를 다 검사하기 때문에 예상된 결과를 얻을 수 있음 경우의 수가 많을 경우 시간이 오래 걸림 비트마스크 ‘모든 경우의 수를 이진수로 표현‘하고 ‘비트 연산’을 통..

[자료구조] DFS (Depth-First Search)

깊이 우선 탐색 (DFS, Depth-First Search) DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 백트래킹에 사용하는 대표적인 탐색 알고리즘. 이진 트리 순회 알고리즘과 상당이 유사하다. BFS와 마찬가지로 어떤 정점을 방문했는지 반드시 기록한다. ⇒ 이렇게 하지 않으면 무한루프에 빠질 위험이 있다. 루트 노드 혹은 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 주로, 재귀함수 또는 Stack으로 구현할 수 있다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사. ..

[자료구조] BFS(Breadth-First Search)

그래프 탐색 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것. 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. SNS 예시로는 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다. → 방금 가입해 친구가 0명인 회원이 있다면 노드는 존재하지만 연결된 친구가 한 명도 없는 상태이다. 기초 그래프 구현 const friends = new Map([ ["Alice", ["Bob", "Diana", "Fred"]], ["Bob", ["Alice", "Cynthia", "Diana"]], ["Cynthia", ["Bob"]], ["Diana", ["Alice", "Bob", "Fred"]], ["Elise", ["Fred"]], ["Fr..

[자료구조] 정렬

정렬 알고리즘 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꿔 놓는 작업을 의미한다. 숫자 : 사전식 순서 또는 크기를 기준으로 나열 문자 : 사전식 순서에 따라 나열 정렬 방법 오름차순 (ascending) : 작은 것에서 큰 것 내림차순 (descending) : 큰 것에서 작은 것 단일 키 (single key) : 하나의 정렬 기준 복합 키 (multi key) : 두 개 이상의 정렬 기준 활용 파일 처리 데이터 베이스 전화번호부 정렬 관련 용어 집합(set) : 정렬할 데이터 셋 전체 원소(element) : 데이터 셋의 datum 부분 집합(subset) : 전체 데이터셋을 어떤 기준으로 분할한 일 부분 키(key) : 정렬의 기준이 되는 특정 값 비교(comparison) ..

[자료구조] 스택과 큐 Stack vs Queue

스택은 “쌓다”라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 위 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다. 또한, 스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근 가능하다. 새로 넣는 자료 혹은 삭제할 때도 top이 가르키는 가장 맨 위에서 진행된다. 용어 top(peek) : 가장 최근에 저장된 데이터 / 가장 먼저 삭제 될 데이터 push : 데이터를 삽입하는 것, 삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 된다 pop : 데이터를 삭제할 때 사용, 가장 최근에 저장된 데이타가 삭제된다 활용 예시 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다 역순..