개발소설

순열(permutation) 요소 n개 중에 r개를 선택하여 순서에 상관 있게 뽑는 경우의 수 순서에 상관이 있다는것은 알파벳 3개를 뽑을때 [ A, B, C ]와 [B, A, C] 는 다르다 뽑은 요소가 같아도 순서가 다르면 다른것 요소가 중복되면 안된다. nPr = n! / (n - r)! 5장에서 3장을 뽑는다면 5P3 5 * 4 * 3 * 2 * 1 / 2 * 1 120 / 2 = 60 자바 순열 템플릿 (Template) //뽑을 요소들이 담긴 리스트 n //뽑을 갯수 r //결과를 담을 리스트 ArrayList result = new ArrayList(); boolean[] visited = new boolean[n.size()]; // 요소 사용 여부 체크용 return permtation(..

탐욕(Greedy) 사전적으로 '탐욕스러운, 욕심 많은' 이라는 뜻으로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒는것 지금 이 순간 당장 최적인 답을 찾는다. 항상 최적의 결과를 도출하지는 않지만, 최적에 근사한 값을 빠르게 도출 할 수 있다. 탐욕 알고리즘 단계 선택 절차 : 현재 상태에서의 최적의 해답을 선택 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사 : 원래의 문제가 해결 되었는지 검사, 해결이 안되었다면 선택 절차로 돌아가 반복 탐욕 알고리즘 적용 예시 주로 거스름돈 문제가 나오는듯 하다. 편의점 알바중 물건의 값이 4230원이 나왔고 손님은 5000원을 냈다. 거스름돈을 줄때 동전의 갯수를 최소한으로 거슬러 줘야한다. 동전은 500,100,50,10원이 있..

시간복잡도 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현 할때 입력값의 변화에 따라 연산을 실행시 연산 횟수에 비해 시간이 얼마나 걸리는가를 고려하는것 효율적인 알고리즘을 구현하는것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화 하는것 Big-O 표기법 시간 복잡도의 표현법에는 Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타)가 있다. 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 나타내는 방법이다. 그중 최악의 경우를 나타내는 Big-O 표기법을 많이 사용 하는데 프로그램이 실행하되는 과정에서 소요되는 최악의 시간까지 고려하기 때문이다. 최선의 경우나 평균의 경우로 문제가 해결 되면 좋겠지만 그렇지 않은 경우에 대하여 대처 할 수 있다. O(1) 입력값이 아무리 ..

트리 순회 (Tree traversal) 특정 목적을 위해 트리의 모든 노드를 방문하는 것을 트리 순회라고 한다. 트리 순회에는 전위 순회, 중위 순회, 후위 순회가 있다. 전위 순회 root를 먼저 순회 root(부모노드) -> 왼쪽 하위 트리 (왼쪽 자식 노드) -> 오른쪽 하위 트리 (오른쪽 자식 노드) public ArrayList preorderTree(Node root, int depth, ArrayList list) { //전위 순회 if (root != null) { list.add(root.getData()); // 부모 노드 preorderTree(root.getLeft(), depth + 1, list); // 왼쪽 자식노드 preorderTree(root.getRight(), dep..

그래프 탐색 하나의 정점에서 시작하여 그래프의 모든 정점을 순회하는 것이 목적 넓이 우선 탐색 (BFS), 깊이 우선 탐색(DFS)로 나뉜다. 넓이 우선 탐색 - BFS (Breadth-First Search) 가장 가까운 정점 부터 탐색한다. 인접한 정점을 모두 탐색한후 다음 깊이(depth)의 정점들을 모두 탐색 마지막 깊이의 정점들을 탐색할때까지 반복 주로 두 정점 사이에 최단 경로를 확인할때 사용한다. 깊이(depth)가 낮을때 사용하면 좋다. 깊이 우선 탐색 - DFS(Depth-First Search) 하나의 경로를 끝까지 탐색한후 다음 경로를 탐색 한다. 하나의 경로에 최대 깊이(depth)까지 탐색한다. 다음 경로로 넘어가기전까지 하나의 경로를 완벽하게 탐색 할 수있으므로 운이 좋다면 몇번..

BST(Binary Search Tree) 트리 구조는 편리한 구조를 전시하는것 외에 효율 적인 탐색을 위해서도 사용한다. 효율 적인 탐색을 위한 트리 구조중 가장 대표적인 트리는, 이진 트리(binary tree)와 이진 탐색 트리(binary search tree) 이진 트리(binary tree) 자식 노드가 최대 2개인 트리 왼쪽 자식노드와 오른쪽 자식노드를 가진다. 정 이진 트리, 포화 이진 트리, 완전 이진 트리로 나뉜다. 각 노드가 0개 or 2개의 자식 노드만 가진다. 마지막 레벨을 제외한 모든 노드가 가득 차야하고 마지막 레벨 노드는 전부 차있지 않아도 되지만 왼쪽 노드는 차있어야 한다. 모든 리프 노드의 레벨이 동일하고 , 모든 레벨이 가득 차 있는 이진 트리 이진 탐색 트리(binar..

Grahp 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 x축과 y축이 있는 수학에서의 그래프와 달리 거미줄처럼 여러개의 점과 선으로 이루어진 복잡한 네트워크 모양을 하고 있다. Graph의 구조 직접적인 관계가 있는 경우 두점이 직접적인 선으로 이어진다. 간접적인 관계인 경우 몇개의 점과 선에 걸쳐 이어진다, 그래프에서 하나의 점을 정점(vertex), 하나의 선은 간선(edge)라고 합니다. Graph의 표현 방식 인접 행렬 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접한다 라고 한다. 서로 다른 정점들이 인접한 상태인지를 2차원 배열의 형태로 나타낸다. A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한다. 가중치 ..

Tree 나무를 거꾸로 뒤집어 놓은 형태를 의미하는 자료 구조 단방향 그래프이고 하나의 뿌리(root)로부터 가지가 사방으로 뻗은 형태 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 하나의 데이터 아래 여러개 데이터가 존재하는 비선형 구조 stack과 queue는 데이터를 순차적으로 나열시킨 선형구조 이다. 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결 각 데이터를 노드(Node)라고 한다. 두 노드가 상하 관계의 계층으로 연결되면 부모/자식 관계가됨 연결된 상층의 노드를 부모 노드(Parent Node), 하층의 노드를 자식 노드(Child Node)라 한다. 자식이 없는 노드를 리프 노드(Reaf Node)라고 한다..