Hello World

백준 1806 : 부분합 문제 링크: www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 내용: 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. Idea: 가장 짧은 길이를 구하기 위해 두 개의 포인터를 사용한다. left : 부분합의 가장 왼쪽 인덱스를 가리키는 용도 right : 부분합의 가장 오..

데이터 모델링 데이터 모델링이란? 정보시스템을 구축하기 위한 데이터 관점의 업무 분석 기법 현실세계의 데이터(what)에 대해 약속된 표기법에 의해 표현하는 과정 데이터베이스를 구축하기 위한 분석/설계의 과정 데이터 모델의 기능 시스템을 현재 또는 원하는 모습으로 가시화하도록 도와준다. 시스템의 구조와 행동을 명세화할 수 있게 한다. 시스템을 구축하는 구조화된 틀을 제공한다. 시스템을 구축하는 과정에서 결정한 것을 문서화한다. 다양한 영역에 집중하기 위해 다른 영역의 세부 사항은 숨기는 다양한 관점을 제공한다. 특정 목표에 따라 구체화된 상세 수준의 표현방법을 제공한다. 데이터 모델링의 유의점 데이터 품질의 문제가 야기되는 문제 중 하나가 바로 데이터 구조의 문제이다. 중복 데이터, 데이터 구조의 비즈니..

속성 Attribute 정의 : 업무에서 필요로 하는 인스턴스에서 관리하고자 하는 의미상 더 이상 분리되지 않는 최소의 데이터 단위. 속성의 명칭 부여 해당 업무에서 사용하는 이름을 부여한다. 서술식 속성명은 사용하지 않는다. 약어 사용은 가급적 제한한다. 전체 데이터모델에서 유일성을 확보하는 것이 좋다. 복합명사를 사용하여 구체적으로 명명한다. 엔터티, 인스턴스, 속성, 속성 값의 관계 한 개의 엔터티는 두개이상의 인스턴스의 집합이다. 한 개의 엔터티는 두개이상의 속성을 갖는다. 한 개의 속성은 한 개의 속성값을 가진다. 속성의 분류 기본 속성 업무로부터 추출한 모든 속성이 해당하며 엔터티에 가장 일반적이고 많은 속성을 차지한다. 코드성 데이터, 엔터티를 식별하기 위해 부여된 일련번호, 그리고 다른 속..

식별자 Identifier : 하나의 엔터티에 구성되어 있는 여러 개의 속성 중에 엔터티를 대표할 수 있는 속성을 의미한다. 식별자의 특징 유일성 : 주식별자에 의해 엔터티 내에 모든 인스턴스들을 유일하게 구분한다. 최소성 : 주식별자를 구성하는 속성의 수는 유일성을 만족하는 최소의 수가 되어야 한다. 불변성 : 주식별자가 한 번 특정 엔터티에 지정되면 그 식별자의 값은 변하지 않아야 한다. 존재성 : 주식별자가 지정되면 반드시 데이터 값이 존재해야한다.(NULL 안됨) 식별자의 분류 대표성 여부 주식별자 : 엔터티 내에서 각 어커런스를 구분할 수 있으며, 타 엔터티와 참조 관계를 연결할 수 있는 식별자 보조식별자 : 엔터티 내에서 각 어커런스를 구분할 수 있으나 대표성을 가지지 못해 참조 관계 연결을 ..

백준 2231 : 분해합 문제 링크 https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 문제 내용 (요약) 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구하는 프로그램을 작성하라. ex) 245의 분해합은 256(=245+2+4+5). 즉 245은 25..

백준 1568 : 새 문제 링크: https://www.acmicpc.net/problem/1568 1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현�� www.acmicpc.net 문제 내용: (요약) 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 숫자 K를 노래할 때, K마리의 새가 하늘을 향해 날아간다. 만약, 현재 나무에 앉아있는 새의 수가 지금 불러야 하는 수 보다 작을 때는, 1부터 다시 시작한다. 앉아있는 새 N마리가 주어질 때, 하나의 수를 노래하는데 1초가 걸린다고 하면, 모든 새가 날아가기까지 총 몇 초가 걸리는가? Ide..

백준 10870 : 피보나치 수 5 문제 링크: https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 �� www.acmicpc.net 문제 내용 (요약) 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1일 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. Idea 이번 문제는 재귀 함수로 풀어보았다. 피보나치 수는 자신 앞의 두 수를 합한 값과 같다는 것을 이용하여 먼저 점화식을 작성한다. 이를 그대로 코드에 옮겨적으면 된다. ..

백준 10872 : 팩토리얼 문제 링크 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 내용 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. Idea 팩토리얼을 구하기 위해서는 두가지 방법이 있다. 반복문을 사용하여 N까지 곱하기 재귀함수를 사용하여 구하기 N!의 값은 N*(N-1)! 임을 이용하여 재귀 함수 수식을 작성한다. 재귀함수를 사용할 때는 아래와 같이 수식을 적어두고 코딩하면 편하다. Code 1) 재귀X 1 2 3 4 5 6 7 8 9 10 #include int main() { int N,..

Lower Bound와 Upper Bound 일종의 이분 탐색(binary search) 오름차순으로 정렬되어 있을 때를 가정한다. Lower Bound -정렬된 숫자들 중에 목표값이 처음 등장하는 인덱스 값을 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int lower_bound(int *arr, int key, int size) { int mid, left, right; left = 0; right = size - 1; while (left = key) right = mid; else left = mid + 1; } return right; } Colored by Color Scripter cs Upper Bound -정렬된 숫자들 중에 목표값보다 높은 숫자가 처음 등장하는..

이분 탐색 Binary Search 이분 탐색의 개념과 특징 이분 탐색(혹은 이진 탐색)은 이미 정렬된 배열에 대해 log₂N의 평균 검색 길이를 갖는 매우 빠르고 간단한 알고리즘이다. 기본 알고리즘 구간에 대해 중간값을 우선 검사한다. 중간값보다 작다면 찾는 값은 왼쪽 구간에 있다. (right = mid-1) 중간값보다 크다면 찾는 값은 오른쪽 구간에 있다. (left = mid+1) 중간값과 같다면 종료 구간을 줄여가며 1~3을 반복한다. 예제 정렬된 배열에 대해 목표값 9를 찾고자 한다. Search 1. left = 0(인덱스 위치) right = 8 mid = (0+8)/2 = 4 >>7(중간값)은 목표값 보다 작으므로 구간을 오른쪽으로 옮긴다. >>left = mid + 1 Search 2...