본문 바로가기

Study for Backend

 (91)
[Algorithm 기초] 백트랙킹 (Backtracking) 백트랙킹 (Backtracking) - 모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더이상 구하지 않는 방법 - 돌다리 두드려보고 가는 느낌 용어 유망 (Promising) : 해가 될 가능성이 있는 경우 유망하다고 함 가지치기 (Pruning) : 해가 될 가능성이 없는 경우 해당 노드를 제외하는 것 백트랙킹 (Backtracking) : 유망하지 않은 쪽으로 가지 않고 되돌아 오는것 알고리즘 복잡도 : O(N^M) //알고리즘 백트랙킹 //N-Queen 문제 (N x N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수) public class backTracking { static int n = 4; static int[] board = new int[n];..
[Data Structure 기초] 트라이 Trie (트라이) - 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조 - 정렬된 자료구조 - 문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름 - 음의 간선이 포함되어 있어도 사용 가능하나 음수 사이클이 있으면 정상 동작 하지 않음 알고리즘 복잡도 : O (N) // 비선형 자료구조 - 트라이 (Trie) import java.util.HashMap; class Node { HashMap child; // 단어 끝인지 체크 용 boolean isTerminal; public Node() { this.child = new HashMap(); this.isTerminal = false; } } class Trie { Node root; public Trie() { this.root = new..
[Algorithm 기초 연습] 이진 탐색을 이용한 숫자 찾기 //이진탐색 - 숫자 찾기 import java.util.*; class Solution { public int solution(int[] nums, int target){ int answer = 0; int left = 0; int right = nums.length - 1; // 배열의 길이 while(left
[Data Structure 기초 연습] 우선순위 큐 - 오름차순 정렬 02 // 비선형 자료구조 - 우선순위 큐 // Practice 2 // 나이 오름차순 (인터페이스 상속 구현 없는 버전) import java.util.PriorityQueue; class Person3 { String name; int age; public Person3(String name, int age) { this.name = name; this.age = age; } } public class priorityQueuePractice03 { public static void solution(String[] name, int[] age) { PriorityQueue pq = new PriorityQueue(); } public static void main(String[] args) { String[..
[Data Structure 기초 연습] 우선순위 큐 - 오름차순 정렬 01 // 비선형 자료구조 - 우선순위 큐 // Practice 1 // 나이 순으로 오름차순 또는 내림차순 출력 // 자바 기본 PriorityQueue import java.util.PriorityQueue; class Person2 implements Comparable { String name; int age; public Person2(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Person2 o){ // 1 : 변경 안함. 우선순위가 높지 않음 // -1 : 변경 //새롭게 추가하는 데이터가 더 적을 때 변경 (적은 값이 위로 올라감) return this.age >= o.age ?..
[Data Structure 기초] 우선순위 큐 Priority Queue (우선순위 큐) - 우선순위가 높은 데이터가 먼저 나옴 - 모든 데이터에 우선순위가 있음 - Dequeue 시 , 우선수위가 높은 순으로 나감 - 우선 순위가 같은 경우는 FIFO - 최소 힙 및 최대 힙의 삽입 삭제가 같다 - 배열, LinkedList, Heap 으로 구현 가능 시간 복잡도 비교 // 비선형 자료구조 - 우선순위 큐 // 연결 리스트를 이용한 우선순위 큐 // 자바 기본 PriorityQueue import java.util.*; public class Main { public static void enqueue(LinkedList list, int data) { int idx = list.size(); for (int i = 0; i < list.size(..
[Data structure 기초 연습] ArrayList로 최소/최대 힙 구현 import java.io.IOException; import java.util.ArrayList; //비선형자료구조 힙 //ArrayList로 최소 힙 구현 class MinHeap{ ArrayList heap; public MinHeap(){ this.heap = new ArrayList(); this.heap.add(0); } public void insert(int data){ heap.add(data); int cur = heap.size() - 1; //insert 하는 곳 while (cur > 1 && heap.get(cur / 2) > heap.get(cur)){ //비교 int parentVal = heap.get(cur / 2); heap.set(cur / 2, data);//스왑 h..
[Data Structure 기초] 그래프와 트리의 차이 Graph (그래프) Trees (트리) 개요 노드와 간선으로 이루어진 자료 구조 그래프의 한 종류 방향성 방향 그래프, 무방향 그래프 방향 그래프 사이클 Cyclic Acyclic 모델 네트워크 모델 계층 모델 루트 노드 루트 노드 X 최상위 노드 부모-자식 부모-자식 관계 X 인접한 상하위 노드 간선 수 그래프에 따라 간선 개수 다름 N개의 노드로 구성된 트리의 간선 수는 N-1개 순회 DFS , BFS Pre-, In-, Post-order / Level-order 경로 2개 이상의 경로 가능 두 노드 간의 경로는 1개
[Data Structure 기초] 그래프 그래프 (Graph) - 정점과 간선으로 이루어진 자료구조 (Cyclic) - 연결된 정점간의 관계를 표현할 수 있는 자료구조 - 그래프의 용도 : 지하철 노선도, 통신 네트워크 등 그래프 구조 용어 정점 (Vertex) 각 노드 간선 (Edge) 노드와 노드를 연결하는 선 ( link, branch ) 인접 정점 (Adjacent vertex) 간선 하나를 두고 바로 연결된 정점 정점의 차수 (Degree) - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 진입 차수 (In-degree) 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-degree) 방향 그래프에서 외부로 나가는 간선의 수 경로 길이 (Path lengt..
[기초 수학] 지수와 로그 제곱(Square) - 같은 수를 두 번 곱함 - 거듭 제곱 : 같은 수를 거듭하여 곱함 제곱근 (Square root, √ ) - a를 제곱하여 b가 될 때 a 를 b의 제곱근이라고 함 지수 (Exponent) 어떤 밑수를 몇 번 곱해야 하는지 나타냄 로그 (Logarithm) - a 가 b 가 되기 위해 제곱해야 하는 수 // 기초 수학 - 지수와 로그 public class mathPractice09 { public static void main(String[] args) { //1. 제곱, 제곱근, 지수 System.out.println("=== 제곱 ==="); System.out.println(Math.pow(2, 3)); System.out.println(Math.pow(2, -3)); Sy..

티스토리툴바