Algorithm/개념정리
-
[추가] 복잡도Algorithm/개념정리 2021. 7. 9. 10:58
복잡도?! 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도 시간복잡도 + 공간복잡도 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 → 알고리즘을 위해 필요한 연산 횟수 측정 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 → 알고리즘을 위해 필요한 메모리의 양 측정 → 둘은 일종의 거래 관계가 성립함 → 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하는 등 → 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법을 '메모이제이션' 기법이라고 함 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도 알고리즘 문제 풀 때 단순히 '복잡도'는 시간 복잡도를 의미함 시간복잡도 표현 시 '빅오(Big-O) 표기법'을 사용함 →..
-
[DFS/BFS] 개념정리2 - 그래프, 인접행렬, 인접리스트Algorithm/개념정리 2021. 7. 4. 11:56
그래프 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)라고도 함 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접하다(Adjacent)'라고 표현함 그래프 표현 방식(2가지) 1. 인접행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 -> 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 /* * Adjacency Array(인접행렬) */ class ArrGraph{ private int[][] arrGraph; //2차원 배열 선언 //그래프 초기화 public ArrGraph(int graphSize) { //vertex가 1부터 시작할 때 this.arrGraph = new int[graphSize+1][graphSi..
-
[DFS/BFS] 개념정리1 - 탐색, 스택, 큐, 재귀함수Algorithm/개념정리 2021. 7. 1. 11:37
1. 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸 대표적 탐색 알고리즘 : BFS, DFS → 2가지 알고리즘의 원리를 제대로 이해해야 탐색 문제 유형을 풀 수 있음 → 2가지 알고리즘을 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 필요함 2. 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념으로 2가지 핵심적인 함수로 구성됨 + 언더플로우&오버플로우 삽입(push) : 데이터 삽입함 삭제(pop) : 데이터 삭제 2-1. 스택 in java Stack 클래스 List 컬랙션 클래스의 Vector 클래스를 상속받아, 스택 메모리 구조의 클래스를 제공함 스택 ..