728x90 전체 글240 [Database] 01 - 1 데이터베이스 시스템 데이터베이스 시스템 데이터베이스(Database)의 정의 데이터베이스는 조직체(데이터베이스 사용기간)의 응용 시스템들이 공유해서 사용하는 운영 데이터(Operational data)들이 구조적으로 통합된 모임입니다. 데이터베이스의 구조는 데이터 모델에 의해 결정됩니다. 자료구조와의 차이 자료구조는 주기억장치에 데이터를 저장하고 사용하는 방법 학습(파일이라는 것에 저장) 데이터베이스는 방대한 양을 다루고 데이터를 사용하고 계속해서 사용되기 때문에 데이터가 디스크에 저장 *디스크 상에 자료를 표현(저장, 관리)하고 효율적으로 처리하는 방법을 배움 *공통점: 데이터자료의 구조화 데이터과 정보 데이터는 프로그램과 질의에 의해 정보로 변환 예시 Name | Address | Course | Grade 허재경 | .. 2021. 9. 3. [알고리즘 분석] 01 - 1 알고리즘: 효율, 분석 그리고 차수 알고리즘에서 효율, 분석 그리고 차수 알고리즘을 만들어 얼마만큼의 효율성이 있는지 더불어 그것을 분석하여 얼마만큼 빨리 문제를 해결할 수 있는지 알아야합니다. 그리고 분석을 위한 척도로 차수를 정의합니다. 알고리즘 단어의 기원 페르시아의 수학자이자 천문학자, 지리학자인 알코와리즘(780-850)의 이름을 따와 알고리즘이라는 단어가 탄생했습니다. 알고리즘 사용 예시 ex1. 24와 16에 대해 최대공약수, 최소공배수 구하기 이러한 절차를 어떻게 표현할지를 알고리즘 분석을 통해 배우게 됩니다. ex2. a에서 b로 가는 최단거리? 어떻게 최단거리를 찾을 것인지? ex3. 화랑 문제 박물관에서 모든 공간을 감시하기 위한 최소 인원 배치는? ex4. 선분교차문제 컴퓨터 그래픽에서 평면 또는 3차원 공간상의 두 .. 2021. 9. 2. [C++] 백준 14852번: 타일 채우기 3 https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 중요풀이 다이나믹 프로그래밍을 사용하여 반복되는 행동을 for문 또는 재귀를 통해서 풀이를 진행합니다. dp[i]는 3*dp[i-2](1*2 두개, 1*1 두개 + 1*2한개 경우 2개 따라서 3가지) + 2*dp[i-1](1*1 두개, 2*1한개) 점화식은 dp[i] = 3 * dp[i - 2] + 2 * dp[i - 1] + (2 * dp[i-3] + ... + 2 * dp[0])이 나옵니다. 소스코드 #include using namespace std; int dp[1000001]; long long.. 2021. 8. 28. [C++] 백준 2812번: 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 중요풀이 이 문제는 그리디 알고리즘을 활요한 문제입니다. 앞에서부터 순차적으로 보았을 때 다음 자리 숫자보다 현재 자리 숫자가 작다면 현재 자리 숫자를 제거해주는 식으로 루프를 진행해주고 이 과정이 끝나고도 K자리를 다 빼지 않았다면 남은 K의 숫자만큼의 자리를 뒤에서부터 빼주는 과정을 반복합니다. 소스코드 #include #include using namespace std; int main() { int N, K, i = 0; string num; vectorv; cin .. 2021. 8. 27. [C++] 백준 11657번: 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 중요풀이 벨만-포드 알고리즘을 사용하는 대표적인 예제 문제입니다. 노드 사이에 가중치가 음수값을 갖기 때문에 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해줍니다. 거리 값이 INF이 아닌 노드들을 체크하여 이동할 수 있는 간선의 가중치를 계산하여 더 작은 값으로 갱신해 줍니다. 여기서 음의 가중치를 갖는 간선이 있다면 그 구간을.. 2021. 8. 27. [C++] 벨만-포드(Bellman - Ford) 알고리즘 벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 가중치 방량 그래프에서 최단 경로 문제를 푸는 알고리즘입니다. 다익스트라 알고리즘에서 간선의 가중치가 음수일 수 없었던 것에 반해 벨만-포드 알고리즘은 가중치를 음수 값으로 갖는 것이 가능합니다. 다만 속도 측면에서 다익스트라 알고리즘이 벨만-포트 알고리즘에 비해 빠른 속도를 갖습니다. 과정은 어떤 한 정점에서 어떤 다른 정점으로 갈 때 그 정점의 개수가 N개면 최대 N-1개의 간선을 사용해야 합니다. 그렇게 시장 정점에서 각 정점까지 가는 가는 최소 가중치합을 간선의 선택개수를 N - 1개까지 증가시키며 비교해주면 됩니다. 그렇게 최소 값들을 유지시키면 됩니다. 마지막으로 N - 1 번째 시행했을 때 남은 값들을 출력합니다. 예시 코드 #include #i.. 2021. 8. 26. [C++] 백준 10159번: 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 중요풀이 플로이드 와샬 알고리즘을 활용하여 문제풀이를 진행합니다. 서로 비교가 가능한 노드들을 체크하여 최종적으로 전체에서 비교 가능한 노드와 자기자신으로 오는 경우를 빼줍니다. 소스코드 #include #include using namespace std; int INF = 200001;// 노드가 최대 100, 간선의 수가 최대 100,000개 이기 때문에 최소 1000.. 2021. 8. 24. [C++] 백준 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 중요풀이 가장 기본적인 플로이드 와샬 알고리즘을 활용한 문제입니다. 소스코드 #include using namespace std; int INF = 10000001;// 노드가 최대 100, 간선의 수가 최대 100,000개 이기 때문에 최소 10000001으로 설정 int node[101][101]; int dp[101][101]; void floydWarshall(int n) { //그래프 초.. 2021. 8. 24. [C++] 플로이드 와샬(Floyd Warshall) 알고리즘 개념 플로이드 와샬 알고리즘이란? 다익스트라 알고리즘이 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다. 예시코드 int node[n + 1][n + 1];//입력받기 int dp[n + 1][n + 1];//다이나믹 프로그래밍 void floydWarshall(int n) { //그래프 초기화 for (int i = 1; i 2021. 8. 24. 이전 1 ··· 10 11 12 13 14 15 16 ··· 27 다음 728x90
