public void bestRadixSort(int[] data) {

    int digit = 0;
    for (int i = 0i < data.lengthi++) {
        int length = String.valueOf(data[i]).length();
        if (length > digit) {
            digit = length;
        }
    }

    for (int i = 0i < digiti++) {

        int[] digitData = new int[data.length];

        for (int j = 0j < data.lengthj++) {
            int idx = (int) ((data[j] % Math.pow(10i + 1)) / Math.pow(10i));
            digitData[j] = idx;
        }

        data = countingSort(digitDatadata10);
    }
}

public int[] countingSort(int[] data, int[] originalData, int k) {
    int count[] = new int[k];
    for (int i = 0i < data.lengthi++)
        count[data[i]]++;
    for (int i = 1i < ki++)
        count[i] += count[i - 1];
    int sorted[] = new int[data.length];
    for (int i = data.length 1i >= 0i--) {
        sorted[--count[data[i]]] = originalData[i];
        //sorted[--count[data[i]]] = data[i];
    }
    return sorted;
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

Sort(countingSort, radixSort)  (0) 2017.02.24
다익스트라(Dijkstra Algorithm)  (0) 2017.02.24
DFS(미로찾기)  (0) 2017.02.24
이진트리(BinaryTree)  (0) 2017.02.24
quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24



class GraphDijkstra {

    final int INFINITY 60000;

    private int[][] adjMat;
    private Vertex[] vertices;
    private int[] distance;

    private int numVertices;

    public GraphDijkstra(int max) {
        adjMat new int[max][max];
        vertices new Vertex[max];
        distance new int[max];

        numVertices 0;

        for (int i = 0i < maxi++) {
            distance[i] = INFINITY;
            for (int j = 0j < maxj++)
                adjMat[i][j] = INFINITY;
        }
    }

    public void addVertex(Vertex v) {
        v.setId(numVertices);
        vertices[numVertices] = v;
        numVertices += 1;
    }

    public void addEdge(Vertex srcVertex dst, int w) {
        adjMat[src.getId()][dst.getId()] = w;
        adjMat[dst.getId()][src.getId()] = w;
    }

    public Vertex getMinVertex() {
        Vertex v = null;
        int temDistance = INFINITY;

        for (int i = 0i < numVerticesi++) {
            //고정되어 있지 않은 꼭지점 중에서 가장 작은 가중치로 연결된 Vertex을 찾는다
            if (!vertices[i].isFixed() && distance[i] < temDistance) {
                temDistance = distance[i];
                v = vertices[i];
            }
        }
        return v;
    }

    public void updateDistance(Vertex v) {
        int tmpDistance;
        for (int i = 0i < numVerticesi++) {
            if (adjMat[v.getId()][i] < INFINITY) {
                //자기와 연결된 꼭지점에 대해서 자기를 지나는 경로의 거리를 계산
                tmpDistance = distance[v.getId()] + adjMat[v.getId()][i];
                if (tmpDistance < distance[i]) {
                    //거리가 더 짧은 경우 정보를 갱신
                    distance[i] = tmpDistance;
                    vertices[i].prev = v;
                }
            }
        }
    }

    public void SPF(Vertex start) {
        Vertex v;
        distance[start.getId()] = 0;
        v = start;

        do {
            v.setFixed();
            updateDistance(v);
            v = getMinVertex();
        while (v != null);

        for (int i = 0i < numVerticesi++) {
            String result[] = new String[numVertices];

            int count = 0;
            v = vertices[i];

            while (v != null) {
                result[count] = v.label;
                count++;
                v = v.prev;
            }
            String log = new String();
            for (int j = count - 1j >= 0j--) {
                log += result[j];
                if (j > 0)
                    log += "->";
            }
            Log.i("kjw"log);
        }
    }

    static public class Vertex {
        private String label;
        private int id;
        private boolean isFix;

        public Vertex prev;

        public Vertex(String label) {
            this.label = label;
            isFix false;
            id = -1;
            prev null;
        }

        public void setId(int id) {
            this.id = id;
        }

        public int getId() {
            return id;
        }

        public void setFixed() {
            this.isFix true;
        }

        public boolean isFixed() {
            return isFix;
        }
    }
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

Sort(countingSort, radixSort)  (0) 2017.02.24
다익스트라(Dijkstra Algorithm)  (0) 2017.02.24
DFS(미로찾기)  (0) 2017.02.24
이진트리(BinaryTree)  (0) 2017.02.24
quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24


class Graph {
    private int[][] adjMat;
    private Vertex[] vertices;
    private int numVertices;

    public Graph(int max) {
        adjMat new int[max][max];
        vertices new Vertex[max];
        numVertices 0;

        for (int i = 0i < maxi++) {
            for (int j = 0j < maxj++)
                adjMat[i][j] = 0;
        }
    }

    public void addVertex(Vertex v) {
        v.setId(numVertices);
        vertices[numVertices] = v;
        numVertices += 1;
    }

    public void addEdge(Vertex srcVertex dst) {
        adjMat[src.getId()][dst.getId()] = 1;
        adjMat[dst.getId()][src.getId()] = 1;
    }

    public void startDFS(Vertex start) {
        Stack<Vertex> stack = new Stack();
        stack.push(start);
        Vertex current;

        while (!stack.isEmpty()) {
            current = stack.pop();
            current.setVisited();
            current.showLabel();
            for (int i = 0i < numVerticesi++) {
                if (adjMat[current.getId()][i] == && !vertices[i].isVisited())
                    stack.push(vertices[i]);
            }
        }
    }
}

class Vertex {
    private String label;
    private int id;
    private boolean isVisit;

    public Vertex(String label) {
        this.label = label;
        this.isVisit false;
        this.id = -1;
    }

    public void showLabel() {
        Log.i("kjw""[" label "]");
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setVisited() {
        this.isVisit true;
    }

    public boolean isVisited() {
        return isVisit;
    }
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

Sort(countingSort, radixSort)  (0) 2017.02.24
다익스트라(Dijkstra Algorithm)  (0) 2017.02.24
DFS(미로찾기)  (0) 2017.02.24
이진트리(BinaryTree)  (0) 2017.02.24
quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24



public class BinaryTree {

    private TreeNode root;

    //순회 travers : (preOrder)
    public void preOrder(TreeNode tempNode) {
        if (tempNode != null) {
            tempNode.showNode();
            preOrder(tempNode.leftNode);
            preOrder(tempNode.rightNode);
        }
    }

    //순회 travers : (inorder)
    public void inorder(TreeNode tempNode) {
        if (tempNode != null) {
            inorder(tempNode.leftNode);
            tempNode.showNode();
            inorder(tempNode.rightNode);
        }
    }

    //순회 travers : (postorder)
    public void postorder(TreeNode tempNode) {
        if (tempNode != null) {
            postorder(tempNode.leftNode);
            postorder(tempNode.rightNode);
            tempNode.showNode();
        }
    }

    //탐색
    public TreeNode search(int value) {
        TreeNode current = root;
        while (current.value != value) {
            if (current == null)
                return null;
            if (value < current.value)
                current = current.leftNode;
            else
                current = current.rightNode;
        }
        return current;
    }

    //최소 노드
    public TreeNode getMin() {
        TreeNode current = root;
        if (current.leftNode != null)
            current = current.leftNode;
        return current;
    }

    //최대 노드
    public TreeNode getMax() {
        TreeNode current = root;
        if (current.rightNode != null)
            current = current.rightNode;
        return current;
    }

    //삽입
    public void insert(int value) {
        TreeNode insertNode = new TreeNode();
        insertNode.value = value;
        if (root == null)
            root = insertNode;
        else {
            TreeNode current = root;
            TreeNode parent;
            while (true) {
                parent = current;
                if (value < current.value) {
                    current = current.leftNode;
                    if (current == null) {
                        parent.leftNode = insertNode;
                        return;
                    }
                } else {
                    current = current.rightNode;
                    if (current == null) {
                        parent.rightNode = insertNode;
                        return;
                    }
                }
            }
        }
    }

    //삭제
    public void delete() {
    }
}

class TreeNode {
    int value;
    TreeNode leftNode;
    TreeNode rightNode;

    public void showNode() {
        Log.i("kjw"String.format("[%d]"value));
    }
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

다익스트라(Dijkstra Algorithm)  (0) 2017.02.24
DFS(미로찾기)  (0) 2017.02.24
이진트리(BinaryTree)  (0) 2017.02.24
quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24
binarySearch  (0) 2017.02.24


public void testQuickSort() {
    List<Integer> numberList = Arrays.asList(13-5-910740922);
    List<Integer> quickResult = quickSort(numberList);
    for (int i = 0i < quickResult.size()i++) {
        Log.i("kjw""result = " + quickResult.get(i));
    }
}

public static List<Integer> quickSort(List<Integer> numbers) {

    if (numbers.size() < 2) {
        return numbers;
    }

    int pivot = numbers.get(0);

    List<Integer> lower = new ArrayList();
    List<Integer> higher = new ArrayList();

    for (int i = 1i < numbers.size()i++) {
        if (numbers.get(i) < pivot) {
            lower.add(numbers.get(i));
        else {
            higher.add(numbers.get(i));
        }
    }

    List<Integer> sorted = quickSort(lower);
    sorted.add(pivot);
    sorted.addAll(quickSort(higher));

    return sorted;
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

DFS(미로찾기)  (0) 2017.02.24
이진트리(BinaryTree)  (0) 2017.02.24
quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24
binarySearch  (0) 2017.02.24
Stack(TwoStack)  (0) 2017.02.24

public class Queue {

    private QueueNode front;
    private QueueNode rear;

    public Queue() {
        front null;
        rear null;
    }

    public void insert(int value) {
        QueueNode newNode = new QueueNode();
        newNode.value = value;
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        else {
            rear.link = newNode;
            rear = newNode;
        }
    }

    public boolean remove() {
        if (isEmpty()) {
            return false;
        else {
            front.link front;
            if (front == null)
                rear null;
            return true;
        }
    }

    public int peek() {
        if (isEmpty())
            return 0;
        else
            return front.value;
    }

    public boolean isEmpty() {
        return (front == null);
    }

    public class QueueNode {
        QueueNode link;
        int value;
    }
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

이진트리(BinaryTree)  (0) 2017.02.24
quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24
binarySearch  (0) 2017.02.24
Stack(TwoStack)  (0) 2017.02.24
Stack(getMin)  (0) 2017.02.24

public boolean binarySearch(List<Integer> numbers, int value) {
    if (numbers == null || numbers.isEmpty()) {
        return false;
    }

    int comparison = numbers.get(numbers.size() / 2);

    if (value == comparison) {
        //success
        return true;
    }

    if (value < comparison) {
        return binarySearch(numbers.subList(0numbers.size() / 2)value);
    else {
        return binarySearch(numbers.subList(numbers.size() / 1numbers.size())value);
    }
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

quickSort  (0) 2017.02.24
Queue  (0) 2017.02.24
binarySearch  (0) 2017.02.24
Stack(TwoStack)  (0) 2017.02.24
Stack(getMin)  (0) 2017.02.24
문자열 rotate 체크  (0) 2017.02.24


public class TwoStack {

    public static int TYPE_TOP_1 0;
    public static int TYPE_TOP_2 1;

    private StackNode top1top2;

    public TwoStack() {
        top1 null; //top1 초기화(공백 상태의 스택
        top2 null; //top2 초기화(공백 상태의 스택
    }

    public void push(int type, int value) {   //스택의 top에 자료 삽입
        StackNode newNode = new StackNode();    //새 노드 생성
        newNode.value = value;
        if (type == TYPE_TOP_1) {
            newNode.nextLink top1//새 노드가 top이 가리키던 노드를 가리키도록 함
            top1 = newNode;//top이 새 노드를 가리키도록 변경
        else {
            newNode.nextLink top2//새 노드가 top이 가리키던 노드를 가리키도록 함
            top2 = newNode;//top이 새 노드를 가리키도록 변경
        }
    }

    public int peek(int type) {
        if (type == TYPE_TOP_1) {
            return top1.value;
        else {
            return top2.value;
        }
    }

    public int pop(int type) {
        int value = peek(type);
        if (type == TYPE_TOP_1) {
            top1 top1.nextLink;
        else {
            top2 top2.nextLink;
        }
        return value;
    }

    public boolean isEmpty(int type) {
        if (type == TYPE_TOP_1) {
            return (top1 == null);
        else {
            return (top2 == null);
        }
    }

    class StackNode {
        public StackNode nextLink//리스트 상의 다음 연결
        public int value//리스트 상의 자료
    }

}

'프로그래밍 > 알고리즘' 카테고리의 다른 글

Queue  (0) 2017.02.24
binarySearch  (0) 2017.02.24
Stack(TwoStack)  (0) 2017.02.24
Stack(getMin)  (0) 2017.02.24
문자열 rotate 체크  (0) 2017.02.24
문자열 치환  (0) 2017.02.24


public class ListStack {

    private StackNode top//스택의 top

    public ListStack() {
        top null; //top 초기화(공백 상태의 스택
    }

    public void push(int item) {   //스택의 top에 자료 삽입
        if (isEmpty())
            top new StackNode(item);
        else {
            StackNode newNode = new StackNode(item);    //새 노드 생성
            if (newNode.min top.min)
                newNode.min top.min;
            newNode.nextLink top//새 노드가 top이 가리키던 노드를 가리키도록 함
            top = newNode//top이 새 노드를 가리키도록 변경
        }
    }

    public int pop() {
        int value = peek();
        top top.nextLink;
        return value;
    }

    public int peek() {
        return top.value;
    }

    public int getMin() {
        return top.min;
    }

    public boolean isEmpty() {
        return (top == null);
    }

    class StackNode {

        public StackNode nextLink//리스트 상의 다음 연결
        public int value//리스트 상의 자료
        public int min;    //min value

        public StackNode(int value) {
            this.value = value//새 노드에 자료 저장
            nextLink null;
            this.min = value;
        }
    }
}

'프로그래밍 > 알고리즘' 카테고리의 다른 글

binarySearch  (0) 2017.02.24
Stack(TwoStack)  (0) 2017.02.24
Stack(getMin)  (0) 2017.02.24
문자열 rotate 체크  (0) 2017.02.24
문자열 치환  (0) 2017.02.24
mergeSort  (0) 2017.02.24


public boolean checkRotate(String targetStrString checkStr) {
    if (targetStr.length() != checkStr.length()) {
        return false;
    }

    char[] oldChar = targetStr.toCharArray();
    char[] checkChar = checkStr.toCharArray();

    String result = new String();
    int index = 0;

    for (int i = 0i < oldChar.length 1i++) {
        if (oldChar[0] == checkChar[i + 1]) {
            index = i + 1;
            result += oldChar[0];
            break;
        }
    }

    for (int i = 1i < checkChar.lengthi++) {
        int remain = (i + index) % checkChar.length;
        result += checkChar[remain];
    }

    return targetStr.equals(result);
}

'프로그래밍 > 알고리즘' 카테고리의 다른 글

Stack(TwoStack)  (0) 2017.02.24
Stack(getMin)  (0) 2017.02.24
문자열 rotate 체크  (0) 2017.02.24
문자열 치환  (0) 2017.02.24
mergeSort  (0) 2017.02.24
계산기(stack)  (0) 2017.02.24

+ Recent posts