CS (44) 썸네일형 리스트형 [공부 방법] SQLD 공부 팁 취득 일자 : 2021.10 발행 기관 : 한국데이터베이스진흥센터 공부법 : 1달동안 매일 7시간 이상씩 기출문제와 개념 노트를 여러 번 보았습니다. 그리고 부족한 개념들은 유튜브 강의와 구글링을 통해 채워나갔습니다. 느낀점 : 처음으로 응시한 자격증이라 긴장이 많이 되었고 정신적인 스트레스가 많았습니다. 하지만 끝까지 포기하지 않고 매일 스터디 카페에 가서 공부했더니 합격을 할 수 있었습니다. 그리고 이전에 전통시장 음식 배달 서비스를 진행할 때 DB관리를 엑셀로 하고 한 장의 sheet로 모든 정보를 담으려고 하니 정보를 정확하고 빠르게 얻기 어려웠던 경험이 있었습니다. 하지만 DB를 공부하면서 이러한 문제는 여러 테이블을 만들어 DBMS로 관리하면 편하게 관리할 수 있겠다고 느꼈습니다. [ TIPS.. Chap 4-7. 허프만 압축 파일을 저장할 때 최대한 작게 저장하는 것이 효율적일 것이다. 데이터 압축 문제는 데이터를 코드화하는 효율적인 방법을 찾는 것이다. (1) 허프만 코드라고 하는 코드화 방식 (2) 주어진 파일을 허프만 코드화하는 탐욕적인 알고리즘 파일은 기본적으로 이진코드를 사용해서 표현한다. 코드화 방식에서 각각의 문자는 코드워드라고 하는 유일한 이진 문자열로 각 문자를 표현한다. 이 중 길이가 고정된 이진 코드는 각각의 문자를 표현하는 bps가 일정하다. 예를 들어 a, b, c를 코드화한다. a : 00, b: 01, c:11 ababcbbbc ⇒ 000100011101010111 (18비트가 필요함) 그러나 길이가 변하는 이진 코드를 사용하면 좀 더 효율적인 코드화 방식을 사용할 수 있다. → 각 문자를 다른 길.. Chap4-6. 작업스케줄링(Job scheduling) 작업 스케줄링 문제 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계(프로세서)에 배정하는 문제 *여기서 기계는 프로세서이며 문제마다 다르다. 하지만 이를 가장 적게 사용하는 방법을 고안하는 것이다. 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다. 발표 = ‘작업’, 강의실 = ‘기계’ 작업 스케줄링 문제에 주어진 문제 요소 1. 작업의 수 입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야하는 직접적인 요소는 아니다. 2. 각 작업의 시작시간과 종료 시간 3. 작업의 길이 - 작업의 시작 시간과 종료시간은 정해져 있으므로 작업의 길이도 주어진 것 - 주어지는 조건에 따라서 작업 스케줄링 문제가 다양하다. - 여러 가지 작업들이 있고 그 작업들마다 시작시간과 종료 시간이 다 .. Chap4-2. 최소 신장 트리 4.2 최소 신장 트리 그리디 알고리즘을 통해 항상 정답을 도출할 수 있는 알고리즘 최소 신장 트리 (1) 최소 신장 트리란 ? 최소 신장 트리 = 신장트리 + 가중치의 합이 최소 -트리는 그래프의 한 종류이다, 정점과 간선으로 된 그래프이다. -신장트리는 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다. (노드 = n개 , 간선 = n-1개 ) 트리에 간선을 하나 추가 시키면 반드시 사이클이 만들어진다. 하지만 그래프에 사이클이 형성이 되면 안된다. [크러스컬 알고리즘] 1) 특정한 정점에서 시작되는 것이 아니라 전체 가중치 그래프에서 가중치 가장 작은 간선을 선택한다 2) 먼저 가중치를 기준으로 정렬 후.. Chap4-1. 동전 찾기 문제 4.1 동전 거스름돈 문제 동전 거스름돈 문제를 해결하는 가장 간단한 효율적인 방법 남은 액수를 초과하지 않는 조건하에 ‘욕심내어' 가장 큰 액면의 동전을 취하는 것 동전 거스름돈 문제의 최소 동전 수를 찾는 그리디 알고리즘 동전의 액면은 500원, 100원, 50원, 1원 coinChange(N) 입력 = 거스름돈 액수 W 출력 = 거스름돈 액수에 대한 최소 동전 수 1. D = {10, 50, 100, 500 } //거슬러줄 수 있는 거스름돈 단위의 집합 2. S = { } //답이라고 한다면 3. value = N 4. while(value != 0) x = D에서 x < value 인 가장 큰 값 if 조건에 만족하는 항목이 없으면(D에 해당하는 값이 없을 때) return S = S (합집합) .. Chap 4. 그리디 알고리즘 그리디 알고리즘 그리디 알고리즘은 "최적화 문제를 해결하는 알고리즘" 최적화 (optimization) 문제 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 매 순간 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함 전체를 끝까지 보는 것이 아니라 해당 시점에서 최적의 선택을 계속적으로 누적하여 마지막 결과까지 진행하는 방법이므로 "근시안적" 이라고 표현함 그리디 알고리즘 방법 = 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해(전역 해)를 얻는다. [특징] (1) .. Chap3-4. 최근접 점의 쌍 찾기(Closest Pair) 3.4 최근접 점의 쌍 찾기 = 최근접 점의 쌍(closest pair)문제는 2차원 평면 상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제이다. ex) 기상 예보, 외판원 문제 등에서 사용 [가장 간단한 방법 구현] 모든 점에 대해서 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점을 찾는 방법 #include #include #include #include #define N 10 typedef struct { int x, y; }Point; void print(Point p[]) { for (int i = 0; i < N; i++) printf("[%d %d]", p[i].x, p[i].y); printf("\\n"); } double dist(Point p1, .. Chap3-2 퀵정렬(QuickSort) 3.2 퀵정렬 퀵 정렬은 분할 정복 알고리즘으로 분류하지만 분할할 수 없을 때까지 분할 후 합병이 아닌 분할 정복, 분할 정보의 과정을 반복하는 알고리즘 2개의 부분 문제로 분할, 각 부분 문제의 크기가 일정하지 않음(비균등 분할) -a = 2이고 b의 값은 정해지지 않음 퀵정렬 알고리즘의 아이디어 순환의 방법으로 과정이 수행된다. 배열의 원소 중 하나를 “피봇”이라는 이름으로 선정 피봇이 위치한 곳을 기준으로 작은 것은 피봇의 왼편으로 큰 것을 피봇의 오른편으로 보낸다. 피봇을 제외한 왼쪽 부분에서 새로운 피봇을 정하여 이 과정을 반복 왼쪽 부분에서 더 이상 정렬할 것이 없다면 오른쪽 부분에서 새로운 피봇을 찾아 이 과정을 반복한다. 피봇 피봇을 기준으로 오른쪽 왼쪽이 다 정렬되면 피봇의 자리는 고정된.. Chap3-1. 합병 정렬(MergeSort) 합병 정렬 = 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 절반으로 감소하는 분할 정복 알고리즘 중 대표 -순환문의 형태로 정렬을 한다. -2개의 부분 문제를 합병하면서 정렬하는 알고리즘 [ 설명 ] 정렬과 탐색 알고리즘이 제일 중요하다. 가장 효율적으로 원하는 것을 찾는 것이 매우 중요 정렬 알고리즘은 구현의 복잡도에 따라 단순한 알고리즘, 복잡으로 나눌 수 있다. -단순한 알고리즘 = 순차적으로 찾아다니면서 한다(1씩 감소하면서 정렬) ex) 문제의 크기가 1씩 감소하는 중첩된 반복문을 통해 크기를 비교한다. → 시간 복잡도를 따지면 n * n의 시간 복잡도임 -복잡한 알고리즘 = 단순보다는 효율적이다. - 합병 정렬 로그 선형으로 가기 때문에 n의 제곱보단 효율적이라고 할 수 있다 . .. Chap 3. 분할 정복 알고리즘 분할정복 알고리즘 : 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 부분 해(분할)를 취합( =정복)하여 원래 문제의 해를 얻음 부분문제와 부분해 더 이상 분할할 수 없을 때까지 분할한다. → 분할한 문제들의 해를 취합 → 부분 취합을 다시 취합 (1) 분할 과정 [상황] 입력 = n 분할 = n을 3개로 분할 각각 분할된 부분 문제의 크기 = n/2 *질문 = 여기서 n을 3개로 분할한 것이므로 각각 분할된 부분 크기는 n/3이 아닌가? ⇒ n이라는 전체 크기를 3등분하여 반으로 나눈다는 의미 3등분을 전체에 대한 것이 아니라 전체의 반의 반이 하나의 등분으로 생각하면 된다. [ 이를 일반화 하면 ] 입력 = n 분할 = n을 b개로 분할 각각 분할된 부분 문제의 크기 = n/a.. 이전 1 2 3 4 5 다음
