CS

[데이터베이스 개론] 1. 데이터베이스 기본 개념

목차 데이터베이스 기본 개념 01 데이터베이스의 필요성 데이터: 현실 세계에서 단순히 관찰하거나 측정하여 수집한 사실이나 값, 자료 정보: 데이터를 의사 결정에 유용하게 활용할 수 있도록 처리하여 체계적으로 조직한 결과물 정보 처리: 데이터에서 정보를 추출하는 과정 또는 방법 정보 시스템: 조직 운영에 필요한 데이터를 수집하여 저장해두었다가 의사 결정이 필요할 때 처리하여 유용한 정보를 만들어주는 수단 02 데이터베이스의 정의와 특징 데이터베이스의 정의 데이터베이스 = 특정 조직의 여러 사용자가 ‘공유’하여 사용할 수 있도록 ‘통합’해서 ‘저장’한 운영 데이터의 집합 공유 데이터(shared data) 특정 조직의 여러 사용자가 함께 소유, 이용 → 사용 목적이 다른 사용자들을 두루 고려하여 구성해야 한..

[알고리즘] 비트 연산자 & 부분집합 (자바/Java)

비트 연산자 &둘 다 1 이면 1 / 해당 비트가 있는지 검사! System.out.println(3 & 5); // 3 = 011 // 5 = 101 // -------- // 001 -> 1 | 하나라도 1이면 1 System.out.println(3 | 5); // 3 = 011 // 5 = 101 // -------- // 111 -> 7 ^ XOR - 서로 다르면 1 System.out.println(3 ^ 5); // 3 = 011 // 5 = 101 // -------- // 110 -> 6 A >1); // 5 / (2^1) = 2 // 101 -> 010 = 2 부분집합 N개의 원소를 가진 집합에서 전체 부분집합의 개수 = 2^N 1. 재귀 부분집합은 공집합부터 원소가 1개, 2개, … ..

[DB/자바] JDBC (Java Database Connectivity) (MySQL)

목차 JDBC https://shs2810.tistory.com/18 https://devlog-wjdrbs96.tistory.com/139 JDBC = Java Database Connectivity 자바와 데이터베이스를 연결해서 데이터를 주고 받게 해주는 프로그래밍 인터페이스 각 DBMS에 맞는 드라이버가 필요함! 작업 순서 JDBC 사용 (Driver Loading) DB 연결 (Connection 생성) SQL 준비 및 실행 DB 연결 해제 (종료) 1. JDBC 사용 (Driver Loading) Class.forName("com.mysql.Jdbc.Driver"); 2. DB 연결 (connection) String url = "jdbc:mysql://localhost:3306/board?se..

[알고리즘] 너비 우선 탐색 BFS & 깊이 우선 탐색 DFS (자바/Java)

목차 BFS & DFS 그래프에서 모든 정점을 방문하는 방법 [참고] 그래프의 인접 노드 구현 1. 인접 행렬 n * n 행렬에 (i, j) (j, i)에 1 (또는 가중치)를 할당 장점 이해하기 쉬움 간선의 존재 여부를 빠르게 알 수 있음 단점 n^2에 해당하는 공간이 필요 모든 원소를 채우는 데에도 시간이 오래 걸림 2. 인접 리스트 보통 연결 리스트를 사용, 각 정점마다 인접한 정점들을 연결 리스트에 표현 장점 행렬에 비해 공간 낭비가 없다. (간선의 총 수에 비례하는 양만큼만 공간이 필요) 단점 만약 거의 모든 정점에 대해 간선이 존재한다면 (dense) 연결 리스트의 정보를 표현하기 위한 오버헤드가 많이 든다. 간선이 존재하는지 알아볼 때 리스트에서 차례로 훑어야 하기 때문에 인접 행렬보다 시간..

[알고리즘] 기본 수학 - 순열 조합 중복순열 중복조합 (자바/Java)

순열/조합 순열, 조합, 중복 순열, 중복 조합을 dfs를 이용하여 구할 수 있다. 백준의 N과 M시리즈가 순열/조합을 공부하기 좋은 문제들이다. https://www.acmicpc.net/workbook/view/2052 1. 순열 순열은 N개의 수에서 R개의 수를 뽑아 순서대로 나열하는 것이다. {1, 2, 3, 4} 4개의 수에서 2개의 수를 뽑아 나열하는 경우의 수는 {1, 2} {1, 3} {1, 4} {2, 1} {2, 3} {2, 4} {3, 1} {3, 2} {3, 4} {4, 1} {4, 2} {4, 3} 의 12가지다. $$ nPr = n*(n-1) * ... (n-r+1) $$ 순열을 구하기 위해서는 dfs를 활용한다. static void dfs(int N, int M, int cn..

[알고리즘] 조합론 - 이항 계수 (자바/Java)

목차 조합론 이항계수 https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients 정의 이항 계수는 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 의미한다. 즉 nCr을 구하는 알고리즘이다. 구현 1: 팩토리얼 이용 $$ nCk = \frac{n!}{{n-k}!*k!} $$ 첫 번째 정의는 팩토리얼 재귀함수를 이용하여 알고리즘으로 구현할 수 있다. public class MyBinoCo { public static void main(String[] args) { int N = 10; int K = 3; // 팩토리얼 System.out.println(fact(N) / fact(N - K) / fact(K))..

[자료구조] 이진 트리의 구현, 순회 (자바/Java)

이진 트리를 각각 배열과 링크드 리스트로 구현하고 트리의 노드들을 전위순회, 중위순회, 후위순회하는 코드를 구현하였다. 1. 배열 1-1. 트리 구현 배열로 이진 트리를 구현할 때는 배열의 index를 통해 부모와 자식 노드를 확인할 수 있다. 루트 노드의 index를 1로 하고, 같은 층위의 노드들을 순서대로 배열에 삽입하면 부모 노드의 인덱스가 i일 때 자식 노드의 인덱스는 i*2, i*2+1이 된다. 전체 정점의 개수를 입력받고 그 다음 줄에 각 간선의 parent와 child 값을 입력받는다. 13 1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13 위 케이스에서 1 2는 부모가 1, 자식 노드가 2임을 의미한다. 이때 루트노드는 부모 노드가 없으니 첫 ..

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..

[자료구조] 트리 & 이진 탐색 트리 Binary Search Tree (자바/Java)

목차 트리 (Tree) 비-선형 자료 구조 (Non-Linear) 선형 자료 구조: 구조에 저장될 데이터들이 순차적으로 저장되는 형태 ArrayList, LinkedList, Map, Stack, Queue 등 비-선형 자료 구조: 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조 Tree 검색 트리 내장 vs 외장 검색 트리 내장 검색 트리: 메인 메모리 내에 존재 외장 검색 트리: 검색 트리가 외부(주로 디스크)에 존재-검색 트리 전체를 메인 메모리에 올려놓고 쓸 수 없는 경우 이진 검색 트리(Binary Search Tree) 특성 각 노드는 키값을 하나씩 갖는다. 이 키값은 모두 다르다. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다. 임의 노드의 키값은 자기..

[자료구조] 스택 Stack & 큐 Queue

목차 Stack 스택 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 Last in First out: 마지막에 삽입한 자료를 가장 먼저 꺼냄 선형구조(자료 간의 관계가 1대 1의 관계) 맨 위의 원소만 접근 가능(top) 응용: 문자열 뒤집기, postfix 계산 메소드 push: 스택에 값을 추가 pop: 스택의 마지막 값을 삭제하고 반환 peek: 스택의 마지막 값을 반환(삭제x) isEmpty: 스택이 비어있는지 확인 push, pop 배열 스택을 이용 public class MyArrayStack { private E[] stack; private int topIndex; public void push(E item) { stack[++topIndex] = item; } public E po..