본문 바로가기

전체 글

[백준]11054 가장 긴 바이토닉 부분 수열 (Kotlin) 문제 설명 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} .. 더보기
[백준] 10844 쉬운 계단 수 (Kotlin 코틀린) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 5656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 풀이 과정 이 문제는 단계마다의 규칙을 찾아 점화식을 세워 구현하는 DP 문제이다. 길이 1짜리 계단을 생각해보면, 1 2 3 4 5 6 7 8 9 총 9개의 계단이 있다. 길이 2짜리 계단을 생각해보면, 10 12 21 23 32 34 43 45 ... 87 89 98 로 총 17개가 있다. .. 더보기
[Codility]GenomicRangeQuery (Python, Kotlin) https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/start/ Codility Your browser is not supported You should use a supported browser. Read more app.codility.com 문제 설명 A:1, C:2, G:3, T:4 이며 'A,C,G,T'로 이루어진 문자열 S를 P[i]부터 Q[i]까지 범위의 인덱스로 잘랐을 때 해당 문자열 내의 최솟값을 구하는 문제이다. 즉, 'CAGCCTA' 라는 문자열 S가 주어지고, P[0] = 2, Q[0] = 4 이면 자른 문자열은 GCC가 되고 여기서 최솟값은 C = 2가 된다. 풀이 과정 이 문제를 풀면서 굉장.. 더보기
데이터베이스 정규화(Normalization)란 데이터베이스 정규화(Normalization) 란? 관계형 데이터베이스의 설계에서 중복을 최소화하게 데이터를 구조화하는 프로세스를 정규화라고 한다. 정규화의 기본 목표는 관련이 없는 함수 종속성은 별개의 릴레이션으로 표현하는 것이다. 정규화된 결과를 정규형이라고 하며, 정규형은 기본 정규형 고급 정규형으로 나뉜다. 기본 정규형 : 제1정규형, 제2정규형, 제3정규형, BCNF(보이스/코드 정규형) 고급 정규형 : 제4정규형, 제5정규형 정규화의 장점으로는 이상 현상의 발생 가능성을 줄이지만, 단점으로는 연산 시간이 증가한다. 제 1 정규형 릴레이션에 속한 모든 속성의 도메인이 더 이상 분해되지 않는 원자값으로만 구성된 정규형이다. 제2정규형 릴레이션이 제1정규형에 속하고, 기본키가 아닌 모든 속성이 기본.. 더보기
데이터베이스 조인(Join) 정리 JOIN(조인) JOIN이란 '연결하다' 라는 뜻을 지닌 단어이다. 이 단어의 뜻처럼, 데이터베이스에서는 둘 이상의 테이블을 연결해서 테이블을 검색하는 방법을 이야기 한다. JOIN의 종류 INNER JOIN OUTER JOIN CROSS JOIN SELF JOIN 그렇다면, 이제 다음과 같은 테이블 두 개를 가지고 각각의 조인에 대해 알아보자. [Star 테이블] ID Name DepNo 1 강호동 10 2 이수근 10 3 유재석 20 4 박명수 20 5 안재현 30 6 송민호 30 7 이병헌 NULL [Dep 테이블] DepNo DepName 10 1박2일 20 무한도전 30 신서유기 40 이경규가간다 1. INNER JOIN (이너조인) 이너조인은 위의 그림처럼 두 개의 테이블에서 공통된 요소들을 .. 더보기
데이터베이스 관계대수 관계 데이터 모델 관계 데이터 모델에서 지원하는 언어는 총 2가지가 있다. 관계 해석 - 원하는 데이터만 명시하고 질의를 "어떻게 수행할 것인가"는 명시하지 않는 선언적 언어 관계 대수 - "어떻게 질의를 수행할 것인가"를 명시하는 절차적 언어 관계 대수 (Relation Algebra) 릴레이션들을 다루는 연산들 기존의 릴레이션들로부터 새로운 릴레이션을 생성함. 연산자들을 사용하여 보다 복잡한 관계 대수식을 점차적으로 만들 수 있음. 기본적인 연산자들의 집합으로 이루어짐. 결과 릴레이션은 또 다른 관계 연산자의 입력으로 사용될 수 있음. 단일 혹은 두 개의 테이블들을 입력 받아 결과 테이블을 생성. 집합 연산을 토대로 만든 것이 관계 대수이며, 기본적으로는 집합 연산자에 속함. 특징 셀렉션 (Selec.. 더보기
데이터베이스 키(key)의 개념 및 종류 데이터베이스 키(Key) 데이터베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때, 다른 튜플들과 구별 할 수 있는 유일한 기준이 되는 속성 키(key)의 특징 Key의 특징으로는 다음과 같은 종류가 있다. 이 특징들은 Key의 종류에 따라 만족하는 경우도 있고, 그렇지 않은 경우도 있다. 유일성 : 유일한 값을 가져야 함. 최소성 : 최소한의 값으로 식별할 수 있어야 함. 불변성 : 변하는 값이어선 안 됨. 키(Key)의 종류 키의 종류에는 슈퍼키, 후보키, 기본키, 대체키, 외래키가 있다. 다음의 릴레이션을 예시로 종류 별로 알아보도록 하자. 슈퍼키 유일성 O , 최소성 X 한 릴레이션 내에 있는 속성들의 집합으로 구성된 키. 유일성을 만족하므로 릴레이션을 구성하는 모든 튜플 중 슈퍼키로 구.. 더보기
데이터베이스(DB) 용어 및 기초개념 정리 데이터베이스 데이터베이스는 일반적으로 컴퓨터 시스템에 전자적으로 저장되는 구조화된 정보 또는 데이터의 조직화된 모음이다. 데이터베이스는 데이터베이스 관리 시스템(DBMS)에 의해 제어된다. 데이터베이스는 다음의 4가지 특징을 갖는다. 실시간 접근 (real-time accessibility) 계속 변화 (continuous evolution) 동시 공유 (concurrent sharing) 내용으로 참조 (content reference) 주로 사용되는 데이터베이스의 종류로 크게 2가지가 있다. 관계형 데이터베이스 행과 열로 구성된 테이블간의 관계를 나타내며, SQL을 통해 관리한다. MySQL, Maria DB, MS-SQL 등이 있다. NoSQL 관계형 데이터 베이스의 한계를 극복하기 위한 데이터 저.. 더보기

티스토리툴바