분류 전체보기
-
알고리즘 - 정렬CS/알고리즘 2021. 2. 13. 21:48
정렬 Selection Sort 최소 원소를 찾아 맨 왼쪽 원소와 교환하고 맨 왼쪽 원소를 제외한다. 하나의 원소가 남을 때까지 반복한다. 장점: 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적어 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용할 수 있다.(역순 정렬일때 가장 효율적이다.) 단점: 이미 정렬된 상태에서 자료가 추가되면 재정렬할때 최악의 처리 속도를 보인다. 수행시간: O(n^2) 구현 with JAVA 1 2 3 4 5 6 7 8 9 public void selectionSort(int[] arr) { for(int i = 0; i
-
[백준]17136: 색종이 붙이기 - JAVA문제풀이/백준 2021. 2. 13. 17:10
[백준]17136: 색종이 붙이기 - JAVA www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 완전 탐색을 통해서 풀어야 하는 구현 문제이다. 이번 문제는 풀고나니 어렵지 않았는데 구현하면서 생각해 줘야 하는 조건들을 놓쳐 다시 구현하느라 시간이 오래 걸렸다. 구현 문제는 꼭꼭 문제를 정확히 읽고 조건을 하나라도 빠트리지 않는 것이 가장 중요하다! 탐색 방향은 오른쪽 아래로만 확인하면 되므로 탐색할 때 x, y좌표 값에 따라 이동 방향을 지정해..
-
[프로그래머스]가장 먼 노드 - JAVA문제풀이/프로그래머스 2021. 2. 13. 14:33
[프로그래머스]가장 먼 노드 - JAVA programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 최단경로로 이동하며 답을 찾아야 하는 문제이므로 BFS를 사용했다. 인접 행렬을 사용했는데, boolean이 아닌 int형으로 선언하면 메모리 초과가 난다. 인접 리스트로 구현하면 메모리 초과가 나지 않는다고 한다. 기본적인 BFS와 동일한데 중요한 점은 반환 값이 가장 멀리 떨어진 노드의 수 라는 점이다. 이를 위해 qSize로 큐의 크기를 저장해 마지막 큐의 크기를 반환하도록 구현하였다. 가장 멀..
-
알고리즘 - DFS, BFSCS/알고리즘 2021. 2. 12. 22:23
DFS, BFS DFS, BFS 그래프의 탐색 방법이다. 시간복잡도는 노드, 엣지의 개수에 영향을 받으며 DFS, BFS 동일하다. 인접 리스트로 구현시 -> O(|v|+|e|) 인접 노드로 구현시 -> O(v^2) DFS - 깊이 우선 탐색 재귀적으로 구현한다. 모든 노드를 다 탐색해야 최단 거리를 알 수 있으므로 최대 길이, 최대값 등을 찾을때 적합하다. 시작 노드로 부터 한 방향으로 계속 탐색을 진행하다가 더 이상 갈 곳이 없을때 되돌아와서 다른 방향으로 다시 탐색한다. 트리의 순회에서 중순위 탐색한 결과와 같다. 구현 with 자바 1 2 3 4 5 6 7 8 9 static void dfs(int[][] node, boolean[] memo, int num) { memo[num] = true; ..
-
DB - KEYCS/DB 2021. 2. 12. 20:33
KEY KEY 데이터베이스에서 조건에 맞는 튜플을 찾거나 검색할 때 기준이 되는 속성이다. Super Key 릴레이션을 구성하는 모든 튜플에 대해 유일성은 만족하지만 최소성은 만족하지 못한다. 유일성: 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있어야 한다. 최소성: 키를 구성하는 속성 하나를 제거하면 유일하게 식별할 수 없도록 꼭 필요한 최소의 속성으로 구성되어야 한다. Canditate Key 후보키: 유일성과 최소성을 모두 만족하는 모든 키를 의미한다. Primary Key 기본키: 후보키 중에서 선정된 것을 의미한다. Alternate Key 대체키: 후보키 중에서 선정된 기본키를 제외한 나머지 후보키를 의미한다. Foreign Key 외래키: 다른 릴레이션의 기본키를 참조하는 속성을 ..
-
DB - 파티셔닝과 샤딩CS/DB 2021. 2. 12. 20:23
파티셔닝과 샤딩 파티셔닝과 샤딩 서비스 크기 증가에 따른 DB 크기 증가하며 VLDB(Very Large DBMS)가 등장했고 여러 테이블을 관리하며 생기는 성능 이슈를 해결하기 위해 파티셔닝과 샤딩이 나왔다. 파티셔닝 큰 테이블이나 인덱스를 관리하기 쉬운 크기로 분리하는 방법이다. 장점 가용성: 물리적인 노드 분리에 따라 전체 DB내의 데이터 손상 가능성이 줄어들고, 데이터 가용성이 향상된다. 관리 용이성: 큰 테이블을 제거하여 관리를 쉽게 할 수 있다, 성능: 대용량 Data Write환경에서 효율적이며 특정 DML과 쿼리 성능을 향상시킨다. 단점 테이블 간 JOIN비용 증가 테이블과 인덱스를 별도로 파티셔닝 할 수 없고 함께 파티셔닝 해야 한다. 방법 Horizontal Partitioning(수평..
-
DB - NOSQLCS/DB 2021. 2. 12. 19:47
NOSQL SQL 관계형 데이터베이스 에서 사용되며 '구조화 된 쿼리 언어(Structured Query Language)'의 약자이다. RDBMS(관계형 데이터베이스 관리 시스템)에서 데이터를 저장, 수정, 삭제 및 검색할 수 있다. 데이터는 정해진 데이터 스키마를 따라 테이블에 저장되고 관계를 통해 연결된 여러개의 테이블에 분산된다. 장점: 데이터의 무결성을 보장한다. 각 데이터를 중복 없이 한번만 저장한다. 단점: 데이터 스키마를 나중에 수정하기가 번거롭거나 불가능 할 수 있다. JOIN문이 많은 복잡한 쿼리가 만들어질 수 있어 성능에 문제가 생길 수 있다. NOSQL 스키마가 없고 관계가 없는 비 관계형 데이터베이스를 말한다. 레코드를 문서(documents)라고 부른다. 다른 구조의 데이터를 같..