Major/Data Structure & Algorithm

[Algorithm] DP

public class seq_Matrix { /* * 연쇄행렬 최소곱셈 알고리즘 * 두개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구함 * 복잡도 : O(n^3) * DP table의 칸의 개수 n*n = n^2 . * 한개의 칸을 채울 때 필요한 연산의 개수는? * 최악의 경우 DP[1][6]인 경우에 가장 많은 연산을 요구. * 한칸을 채울 때 최악의 경우 n번의 연산을 해야하므로 * O(n^3)의 시간복잡도 가진다. */ public static int minmult(int n, int d[], int P[][]){ int M[][] = new int[n+1][n+1]; for(int i = 0; i < n; i++) M[i][i] = 0; for(int diag = 0; diag < n; di..

DFS(Depth First Search)

- 인접 행렬을 이용한 DFS 구현 a[x][i] 값이 1인지(=연결된 간선이 있는지) 확인하면서 방문한 적이 없는 정점을 방문 해야함. void dfs(int x) { check[x] = true; for(int i = 1; i 인접 리스트에 이미 연결된 간선만 저장되어 있기 때문이다. void dfs_list(int x) { check[x] = true; for(int i = 0; i < a[x].length(); i++) { int y = [x][i]; if (check[y] == false) { dfs(y); } } } 배열 visited를 F로 초기화하고 공백 스택을 생성한다. 방문한 정점은 T로. (=visited) 정점 A에 아직 방문하지 않은 정점 B,C가 있으므로 스택에 A 집어넣고 오름..

Binary Tree

[자료구조] 트리 (Tree) (velog.io) [자료구조] 트리 (Tree) 사진의 출처 : 링크트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른 velog.io *이진 탐색 트리 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조. 1. 모든 원소는 서로 다른 유일한 키를 갖는다. 2. 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다. 3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다. 기본적으로 루트에서 탐색을 시작한다. 탐색할 키 값 x를 루트 노드의 키 값과 비교한다. - 3개..

후위식 연산

후위연산식은 컴퓨터가 계산하기에 훨씬 편한 연산식 형태이다. 피연산자를 스택에 push하고 연산자를 만나면 스택에서 두개의 피연산자를 꺼내서 계산하고 다시 스택에 push한다. 스택이 공백이 될 때까지 진행하고 결과를 출력한다. package stack_self; class StackNode { int data; StackNode link; } class LinkedStack02 implements Stack02{ private StackNode top; public boolean isEmpty() { return (top == null); } public void push (int item) { StackNode newNode = new StackNode(); newNode.data = item; ne..

Stack , 괄호검사(Valid Braces), Infix to Postfix algorithm

먼저 들어간 것이 나중에 나온다 - 후입선출(LIFO) ADT - pust, pop, pick void StackInt(Stack *pstack); - 스택 초기화 진행 - 스택 생성 후에 가장 먼저 호출되어야 하는 함수임. int isEmpty(Stack * pstack); - 스택이 비어있는 유무에 따라서 bool값(0or1) 리턴 void push(Stack * pstack, Data data) - 스택에 데이터 저장. Data pop(Stack * pstack); - 마지막에 저장된 요소 삭제, 삭제된 데이터는 반환- 이 함수의 호출을 위해서는 데이터가 하나 이상 꼭 존재해야함 Data Peek(Stack *pstack); - 마지막에 저장된 요소를 반환하나 삭제는 안함- 얘도 마찬가지로 데이터가..

review

원하는 형태의 이중 연결리스트 만들기. 일단 틀부터 짜자. class DoubleNode{ DoubleNode llink; DoubleNode rlink; private String data; public DoubleNode() { this.data = null; this.llink = null; this.rlink = null; } public DoubleNode(String data) { this.data = data; this.llink = null; this.rlink = null; } public String getData() { return this.data; } public void setData(String data) { this.data = data; } public DoubleNode ..