(basic) recursive call,stack,queue, dfs,bfs ....

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

- (basic)linked list

- (basic)recursive call

- stack

- queue

- bfs,dfs

- backtracking

 

- (basic)linked list

 

A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

 

 

from : https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/

import java.util.*;
public class LinkedListExample {
     public static void main(String args[]) {

       /* Linked List Declaration */
       LinkedList<String> linkedlist = new LinkedList<String>();

       /*add(String Element) is used for adding 
        * the elements to the linked list*/
       linkedlist.add("Item1");
       linkedlist.add("Item5");
       linkedlist.add("Item3");
       linkedlist.add("Item6");
       linkedlist.add("Item2");

       /*Display Linked List Content*/
       System.out.println("Linked List Content: " +linkedlist);

       /*Add First and Last Element*/
       linkedlist.addFirst("First Item");
       linkedlist.addLast("Last Item");
       System.out.println("LinkedList Content after addition: " +linkedlist);

       /*This is how to get and set Values*/
       Object firstvar = linkedlist.get(0);
       System.out.println("First element: " +firstvar);
       linkedlist.set(0, "Changed first item");
       Object firstvar2 = linkedlist.get(0);
       System.out.println("First element after update by set method: " +firstvar2);

       /*Remove first and last element*/
       linkedlist.removeFirst();
       linkedlist.removeLast();
       System.out.println("LinkedList after deletion of first and last element: " +linkedlist);

       /* Add to a Position and remove from a position*/
       linkedlist.add(0, "Newly added item");
       linkedlist.remove(2);
       System.out.println("Final Content: " +linkedlist); 
     }
}

output: 

 

Linked List Content: [Item1, Item5, Item3, Item6, Item2]

LinkedList Content after addition: [First Item, Item1, Item5, Item3, Item6, Item2, Last Item] First element: First Item

First element after update by set method: Changed first item

LinkedList after deletion of first and last element: [Item1, Item5, Item3, Item6, Item2] Final Content: [Newly added item, Item1, Item3, Item6, Item2]

 

- (basic)recursive call

 

recursive call is like stack of computer engineering

 

output in order

class math{

    int printf(int a){

        //1부터 10까지 출력
        if( a > 0){
            System.out.print(a);
            return printf(a-1);
        }
        else{
            return 0;
        }
    }
}

/*
for(int = 10 ; i > 0 ; i--)
	System.out.print(i);
*/

 

 

Factorial

class math{

    
    int num=1;

    int factorial(int i){

        //1부터 10까지 출력
        if( i > 0){
            num*=i;
            return factorial(i-1);
        }
        else{
            System.out.println(num);
            return 0;
        }
    }
}

int main(){
	math.factorial(10);
}

/*
int num=1;
for(int i = 10 ; i > 0 ; i--){
	num*=i
}

*/


or

 int factorial(int i){

        //1부터 10까지 출력
        if( i != 1)
            return i*factorial(i-1);
        else
        	return 1;
        
        return 0;
    }

 

 

push : factorial(5) -> factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)

pop  : factorial(1) -> factorial(2) -> factorial(3) -> factorial(4) -> factorial(5)

 

 

Permutation

nPr = n! / (n-r)!

package GreedyAlgorithm;

import java.io.IOException;

/*
nPr = n! / (n-r)!
*/

class math_Permutation{

    int Permutation(int n,int r){
        math_factoral mf = new math_factoral();
        return mf.factorial(n)/mf.factorial(n-r);        
    }
  
}

public class _Permutation {
    public static void main(String[] args) throws IOException {
        math_Permutation mp = new math_Permutation();
        System.out.println(mp.Permutation(10,4));
        
    }
    
    
}

 

Combination

package GreedyAlgorithm;

import java.io.IOException;

/*
nPr = n! / (n-r)!
use recursive call


*/

class math_Combination{

    int Combination(int n,int r){
        math_factoral mf = new math_factoral();
        math_Permutation mp = new math_Permutation();
        return mp.Permutation(n, r)/mf.factorial(r);
    }
  
}

public class _Combination {
    public static void main(String[] args) throws IOException {
        math_Combination mp = new math_Combination();
        System.out.println(mp.Combination(10,4));
        

    }
    
    
}

 

 

 

 

 

- stack

 

= 택배 상하차,한쪽만 뚫려있는 터널

FILO ( First In Last Out) 로 먼저들어온것이 먼저나가는 알고리즘? 보다는 자료구조에 가까운 개념이다.

 

java.util.Stack class에서 꺼내쓸수있다.

import java.util.Stack;
public class Program {
	public static void main(String[] args){
		Stack stack = new Stack();
		stack.push(3); //3
		stack.push(2); //3, 2
		System.out.println(stack.pop()); //2를 출력, 스택에는 3
		stack.push(6); //3, 6
		stack.push(8); //3, 6, 8
		System.out.println(stack.peek()); // 최근값
		System.out.println(stack.search(6));// 출력 2
		while(stack.empty()==false){
			System.out.println(stack.pop());//순서대로 꺼내기 여기서는 8,6,3
		}
	}
}

 

 

- Queue

 

 = 은행창구,양쪽이 뚫려있는 터널

FIFO(First In First Out) : 먼저 들어온것이 먼저 나가는 알고리즘?은 아니고 자료구조

새치기 불가, 

 

java.util.Queue에 있다.

import java.util.Queue;
import java.util.LinkedList;
public class Program {
	public static void main(String[] args){
		Queue<String> q = new LinkedList<String>();
		q.offer("강감찬"); //"강감찬"
		q.offer("홍길동"); //"강감찬","홍길동"
		System.out.println(q.peek());//"강감찬" 참조
		//여전히 "강감찬","홍길동"
		
		System.out.println(q.poll());//"강감찬" 꺼냄, 현재 "홍길동"
		q.offer("이순신"); //"홍길동", "이순신"
		q.offer("김구"); //"홍길동", "이순신", "김구"
		while(q.isEmpty()==false){
			System.out.println(q.poll());
			//"홍길동", "이순신", "김구" 순으로 꺼냄
		}		
	}

 

 

- bfs,dfs

 

bfs

 

 

O(v+e)

= 맹목적인 탐색

미로찾기 같은거 할때 많이 사용된다. 최단거리를 보장하고자할때!!

 

loop,{

큐에서 노드를 하나꺼내고 꺼낸 노드의 자식노드들을 넣고 꺼낸 노드는 출력합니다.

}

 

BFS는 자체로서는 큰 의미가 없고 다른 알고리즘에 들어가서 작동될때 큰 의미가 있다고 보면된다.

5

BFS는 큐로 만들수있다.

우선 BFS는 그래프를 다음과 같이 탐색하는데

 

 

이런식으로 탐색한다고 정했을때 1,2,3,4,5,6 순으로 들어갔을때

queue------------

이안에 들어간다고 가정

-------------------

 

1)

1

2) 1빼고

2 3

3) 2 빼고

3 4 5

4) 3 빼고

4 5 6

 

4 빼고 5 빼고 6빼면 queue는 비어지고 종료

 

//그래프는 트리가 아니다. 시작점이 어디든상관없다.
//그래프는 부모,자식관계 개념이 없다. 인접한노드가 무엇인지만 알수있다.
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int number = 7;
int c[7];
vector<int> a[8];

void bfs(int start){
    queue<int> q;
    q.push(start);
    c[start] = true;
    while(!q.empty()){
    	int x = q.front();
        q.pop();
        printf("%d ", x);
        for(int i = 0; i < a[x].size(); i++){
        	int y = a[x][i];
            if(!c[y]){
            	q.push(y);
                c[y] = true;
            }
        }
    }
}

int main(void){
    a[1].push_back(2);
    a[2].push_back(1);
    
    a[1].push_back(3);
    ..
    ..
    .. // 하나의 간선마다 전부 연결
    
    bfs(1); // 출력 : 1 2 3 4 5 6 7
 
}

 

 

dfs

 

= 맹목적으로 BFS 와 다르게 stack이 사용됨, 왼쪽벽에 손집고 계속 따라가보는거(미로)

 

근데 컴퓨터는 기본적으로 stack으로 돌아가기에 재귀만 사용하면 알아서 작동함

 

loop,{

스택에서 노드를 하나꺼내고 꺼낸 노드의 자식노드들을 넣고 꺼낸 노드는 출력합니다.

}

1. 스택의 최상단 노드를 확인

2. 최상단 노드에게 방문하지 않는 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리하고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다

 

1,2,3,4,5,6의 그래프가 있을때 

 

방문순서 : 1 - 2 - 3 - 6 - 4 - 5

 

재귀함수를 사용하면 그것이 DFS와 동일하게 작동한다고 보면된다.

 

DFS 또한 그 자체로는 의미가 없음

 

 

//그래프는 트리가 아니다. 시작점이 어디든상관없다.
//그래프는 부모,자식관계 개념이 없다. 인접한노드가 무엇인지만 알수있다.
#include <iostream>
#include <vector>
using namespace std;

int number = 7;
int c[7];
vector<int> a[8];

void dfs(int x){
	if(c[x]) return;
    c[x] = true;
    cout << x << ' ';
    for(int i = 0 ; i < a[x].size(); i++) {
    	int y = a[x][i];
        dfs(y);
    {
}

int main(void){
	push_back............
    
    dfs(1); // 출력 : 1 2 3 6 7 4 5

}

 

 

- backtracking

 

어떤 노드의 유망성을 점검후 유망하지 않으면 부모노드로 돌아가고 다른노드를 검사하는것!!

== 스택을 사용하고 스택에 넣기전에 유망성을 검사하여 없으면 안넣는다.

== 쉽게말해 백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만 살펴보는것이다.

 

dfs와 bfs를 보면은 단순히 탐색하는 순서를 나열하는것인데 어떻게 이것을 활용하여 backtracking하는지 의문이 갈수있다.

 

쉽게말해서 재귀함수를 사용해서 dfs탐색을 하는데 처음시작부터 깊게 들어가면서

어느지점을 깊게 들어가고 어느지점을 깊게 들어가지 않을지를 결정하는것이다.

 

모든지점을 dfs로 탐색은 가능하지만 너무 많은 시간이 소요되기 때문에 백트래킹을 사용하는것이다.

 

이름이 백트래킹인것은 이것이 마치 뒤로 돌아가서 다시 추적하는것과 같은 형태여서 그런것이라고 생가갛ㄴ다.

되추적을 의도하고 만든것인지는 나도 모른다.