자료구조 알고리즘 썸네일형 리스트형 <자료구조 알고리즘> 그래프 표현 2. adjacency Matrix (인접 행렬) 그래프가 무엇인지 모르시는 분들은 아래 글을 참고하길 바랍니다. https://jjoonleo.tistory.com/11 그래프 개념 그래프란? 정점(vertex)과 간선(edge)로 이루어진 자료구조이다. 수학에서 자주 보던 좌표평면에 그리는 그 그래프가 아니다. 쉽게 이해하기 위해서 정점을 마을 간선을 마을 사이를 잇는 길이라고 jjoonleo.tistory.com 그래프의 표현 방식 이번 글에서는 그래프의 표현 방식에 대해 알아 보도록 하겠다. 그래프는 배열이나 큐 스택과는 다르게 어떻게 구현해야 할지 바로 떠오르지는 않는 것 같다.(나만 그랬나??) 그래프의 표현 방식에는 3가지가 있다. 1. Adjacency List (인접 리스트) 2. Adjacency matrix (인접 행렬) 3. edg.. 더보기 <자료구조 알고리즘> 그래프 표현 1. adjacency List (인접 리스트) 그래프가 무엇인지 모르시는 분들은 아래 글을 참고하길 바란다. https://jjoonleo.tistory.com/11그래프의 표현 방식이번 글에서는 그래프의 표현 방식에 대해 알아 보도록 하겠다. 그래프는 배열이나 큐 스택과는 다르게 어떻게 구현해야 할지 바로 떠오르지는 않는 것 같다.(나만 그랬나??) 그래프의 표현 방식에는 3가지가 있다. 1. Adjacency List (인접 리스트) 2. Adjacency matrix (인접 행렬) 3. edge list (간선 리스트) 1. Adjacency Listadjacency list는 각 노드에 연결된 노드를 리스트로 저장한다. 위의 그래프를 adjacnecy list로 표현해 보자면 다음과 같을 것이다. 0: [ 1, 3 ] 1: [ ] 2: [ 0.. 더보기 <자료구조 알고리즘> 계획 및 보는 법 자료구조 알고리즘을 공부를 하는 중인데 정리해서 글을 적으면 훨씬 도움이 될 것 같아서 작성하는 블로그입니다. 잘못된 부분이 있다면 알려주시면 수정하도록 하겠습니다. 작성 하려고 계획 중인 주제들 - time complexity (시간복잡도) - master theorem (마스터 정리) - dynamic, static array(동적, 정적 배열) - stack(스택) - queue(큐) -priority queue(우선순위 큐) - dequeue(덱) - hash(해시) - greedy(탐욕법) - dynamic programming (동적계획법) - graph(개념, 표현, 탐색, 관련 알고리즘 등) - tree(트리) - segment tree(세그먼트 트리) - trie (트라이) 말 그래도 계.. 더보기 <자료구조 알고리즘> 그래프 개념 그래프란? 정점(vertex)과 간선(edge)로 이루어진 자료구조이다. 수학에서 자주 보던 좌표평면에 그리는 그 그래프가 아니다. 쉽게 이해하기 위해서 정점을 마을 간선을 마을 사이를 잇는 길이라고 생각해보자. 그러면 위 그림에서 0번 마을과 1번 마을, 0번과 2번, 1번과 2번, 2번과 3번 마을을 이어주는 길은 있지만 1번과 3번, 0번과 3번 마을을 이어주는 길은 없다고 볼 수 있을 것이다. 도로 외에도 지하철 노선도 등도 그래프로 나타낼 수 있다. 그래프 용어 ※ 용어는 가급적이면 영어를 외워두도록 하자. 정점(vertex) 노드(node) 점에는 데이터가 저장된다. 앞으로 이 글에서 정점이라고 할 때도 있고 노드라고 할 때도 있을텐데 같은 뜻이다. 간선(edge) 정점 사이의 관계를 나타낸 .. 더보기 <자료구조 알고리즘> 정렬 (선택정렬) 정렬이란? 선형 자료구조(배열 등)의 원소들을 특정한 순서(오름차순 내림차순등)로 나열하는 것을 이야기 한다. 정렬 자체가 목적일 때도 있겠지만 대부분 검색등의 다른 알고리즘의 전처리 과정으로 사용되는 경우가 많다. 정렬알고리즘 종류 Permutaion Sort, Selection Sort , Bubble Sort , Quick Sort , Insertion Sort , Merge Sort 등 굉장히 많은 종류의 정렬알고리즘이 있다. 각 알고리즘의 방식과 구현방법, 시간복잡도를 알아보도록 하자. 이 글에서는 오름차순을 기준으로 설명하도록 하겠다. 1. Permutation Sort 모든 경우를 다 확인해보는 정렬 알고리즘이다. 즉 n개의 원소로 만들 수 있는 서로 다른 순열들을 모두 만들면서 정렬이 되어.. 더보기 <자료구조 알고리즘> 배열 ※ 이 글은 배열을 처음 배우시는 분들을 위한 글이 아닙니다. 배열이란? 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조 그냥 맨날 쓰는 그 배열 맞다. 근데 이 배열에도 종류가 있다. 그리고 그 종류에 따라 각 연산을 하는데 걸리는 시간복잡도가 달라진다. 배열의 종류에 따라 다음 연산에 걸리는 시간복잡도를 계산해 볼 것이다. - 인덱스가 i인 원소 접근 - i번째에 값 삽입(insertion), 삭제(deletion) - 마지막에 값 삽입,삭제 - 처음에 값 삽입, 삭제 종류 다음과 같이 분류해 볼 수 있겠다. 1. static array 2. dynamic array 1. Static Array 말 그대로 정적인 배열이다. 즉 한번 할당되고 나면 크기와 길이를 바꿀 수 없는 배열이다. c.. 더보기 <자료구조 알고리즘> FFT를 이용한 다항식 곱셈 알고리즘 다항식 곱셈은 수학에서 아주 기본적으로 하는 연산 중에 하나이다. $$A(x) = 5x+2$$ $$B(x) = x^2+2x+3$$ 이 두식을 곱한 C(x)를 구한다고 하면 $$C(x) = (5x+2)(x^2+2x+3) \\ = 5x \times x^2 + 5x \times 2x+2\times x^2 + 5x \times 3+2 \times 2x + 2 \times 3 = 5x^3 + 14x^2 + 19x + 6$$ 이렇게 쉽게 계산할 수 있다. 하지만 컴퓨터로 짜려면 어떻게 해야 할까? 다항식을 나타내는 방법에는 대표적으로 coefficient representation과 value representation 이 있다. coefficient representation으로 위의 A(x)와 B(x)를 나타내.. 더보기 이전 1 2 다음
