본문 바로가기

전체 카테고리361

[Algorithm] 공간 복잡도(Space Complexity) 1. 공간 복잡도란? 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다. 총 필요 저장 공간 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간 S(P) = c + Sp(n) c: 고정 공간 𝑆𝑝(𝑛)Sp(n): 가변 공간 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우된다. 2. 공간 복잡도 계산 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 표기법으로 표현한다. 2.1 O(n) 공간 복잡도 예시 n! 팩토리얼 구하기 재귀 함수를 통해서 구현하므로 변수 n에 따라서 변수 n이 n개가 만들어지게 됨 factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스.. 2021. 11. 15.
[Algorithm] 시간 복잡도(Time Complexity) 1. 시간 복잡도란? 알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?" 이다. 효율적으로 알고리즘을 구현했다는 것은 즉, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화했다는 것이다. 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다. 2. 시간 복잡도 표기법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 위 세가지중에서 보통 빅오 표기법을 통해서 알고리즘 수행 시간을 나타낸다. 최악의 경우도 고려하는 것이 바람직하기 때문이다. .. 2021. 11. 15.
[알고리즘] 프로그래머스 - 올바른 괄호 (Stack) 1. 문제 2. 나의 풀이 전형적인 Stack 문제로 반복문을 통해서 문자열을 순회한다. 문자가 '(' 일 경우에는 Stack에 넣어주고 ')'일 경우에는 Stack에서 제거한다. 만약 더이상 제거할게 없는데 ')' 문자가 오면 올바른 괄호가 아니다. 또한 문자열을 모두 순회하고나서 Stack에 '('가 남아있다면 괄호가 제대로 닫히지 않고 끝났기 때문에 올바른 괄호가 아니다. import java.util.*; class Solution { boolean solution(String s) { boolean answer = true; Stack stack = new Stack(); int len = s.length(); for(int i=0;i 2021. 11. 15.
[Database] HASH JOIN 최적화 1. HASH JOIN 이란? HASH 조인은 조인될 두 테이블 중 하나를 해시 테이블로 선정하여 조인될 테이블의 조인 키 값을 해시 알고리즘으로 비교하여 매치되는 결과값을 얻는 방식이다. 동작 방식 1. 둘 중 작은 집합(Build Input)을 읽어 Hash Area에 해시 테이블을 생성한다. (해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인에 엔트리를 연결) - 작은 테이블에서 해시 테이블을 만드는 이유는 해시 테이블은 DBMS의 워킹 메모리에 저장되므로 조금이라도 작은 것이 효율적이기 때문이다. 2. 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 JOIN 한다. 3. 해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다. 2. 특징 N.. 2021. 11. 14.
[Database] SORT MERGE JOIN 최적화 1. SORT MERGE JOIN이란? Sort Merge는 결합 대상 테이블들을 각각 결합키로 정렬하고, 일치하는 결합키를 찾으면 결합한다. Nested Loop의 중첩 for문과 유사하다고도 볼 수 있음. 1. 각 테이블에 대해 동시에 독립적으로 데이터를 먼저 읽어 들인다. 2. 읽혀진 각 테이블의 데이터를 조인을 위한 연결고리에 대하여 정렬을 수행한다. 3. 정렬이 모두 끝난 후에 조인 작업이 수행한다. 2. SORT MERGE JOIN 특징 대상 테이블을 모두 정렬해야 하므로 메모리를 많이 소비. Hash는 한쪽 테이블에 대해서만 해시 테이블을 만들므로 Hash보다 많은 메모리를 사용한다. Hash와 다르게 부등호를 사용한 결합에도 사용할 수 있다. 단, 부정조건 결합에서는 사용할 수 없다. 테이.. 2021. 11. 14.
[Database] 데이터베이스 I/O 원리 및 최적화 1. Database Read Database는 데이터를 블록(Block) 단위로 읽고 저장한다. 오라클의 경우는 기본 블록 사이즈가 8kb이다. 즉, database가 아주 작은 데이터를 가져온다고 하더라도 최소한 8kb의 블록을 읽는다. Database의 튜닝에서 가장 중요한 것은 바로 이 블록 단위 I/O를 줄이는 것이다. 2. 메모리 I/O vs 디스크 I/O 디스크 I/O : 디스크의 액세스 암이 움직이면서 헤드를 통해 데이터를 읽고 쓴다. 메모리 I/O : 전기적 신호 디스크 I/O를 통한 입출력은 메모리를 통한 입출력보다 평균적으로 10,000배 이상 느리다. 메모리는 물리적으로 한정된 자원이므로, 디스크 I/O를 최소화하고 버퍼 캐시 효율을 높이는 것이 데이터베이스 I/O 튜닝의 목표가 된.. 2021. 11. 14.

티스토리툴바