목록전체 글 (468)
기록방
👉 문제링크🔸 문제 분석 🔸전형적인 최장 증가 부분 수열 (LIS) 문제이다.LIS의 DP 풀이는 O(n^2) 이고, 이분탐색 풀이는 O(nlogn)이다.여기서는 n이 1000이므로, DP 풀이를 사용했다.🔸 문제 풀이 🔸DP 배열을 만들어 사용한다.DP 배열에는 현재 인덱스를 포함해서 만들어지는 가장 긴 증가하는 부분 수열의 길이를 저장한다.배열을 순회하며, 이전 인덱스들 중 DP 배열 값의 최대값 + 1을 저장한다.dp[i] = max(dp[i], dp[j] + 1)🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;..
👉 문제링크🔸 문제 분석 🔸N개의 컴퓨터 사이 M개의 네트워크가 있다.모든 컴퓨터를 연결할 수 있는 네트워크 최소 비용을 구한다.🔸 문제 풀이 🔸전형적인 MST 문제이다. 모든 노드를 한 번씩은 연결하며 최소 비용이 되도록 하기 때문이다.여기서는 크루스칼(Kruskal) 알고리즘을 사용했다.🔸 코드 🔸import java.io.*;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { private static int[] parent; public static void main(String[] args) throws IOException { // Input Buf..
👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 1년마다 상하좌우의 바닷물 수 만큼 줄어든다.빙하가 두 덩어리 이상으로 나뉘어지는 최소 시간을 출력한다.끝까지 두 덩어리가 되지 않으면 0을 출력한다.🔸 문제 풀이 🔸빙하가 녹는건 4방탐색을 하면 되고, 덩어리 확인은 그래프 탐색과 4방 탐색을 함꼐 하면 된다.여기서는 그래프 탐색 알고리즘으로 너비 우선 탐색 (BFS) 를 사용했다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;public class Main { private static int N, M; private static int..
1번(4) 데이터 종속성⇒ 파일 구조에 응용 프로그램이 종속적. 파일 구조가 변경되면 응용 프로그램도 함께 변경해야 하는 문제 2번(3) 데이터의 가용성 증가를 위해 중복을 허용하고 싶었다.⇒ 데이터베이스는 데이터 중복을 최소화 한다. 3번(2) 예약 시스템과 같이 최신 정보를 다수의 사용자가 공유해야 하는 경우⇒ 동시 공유는 데이터베이스의 주 기능 4번(2) 데이터베이스의 안정성을 유지하기 위해 사용자의 데이터 공유를 제한한다.⇒ 데이터베이스는 데이터를 동시 공유 할 수 있다. 5번(4) 절차 기능⇒ DBMS의 주요 기능 : 정의, 조작, 제어 6번(2) 조작 기능⇒ 조작 기능 : 데이터를 삽입, 삭제, 수정, 검색하는 연산을 한다. 7번(3) 데이터베이스의 구조를 정의하거나 수정한다.⇒ 정의 기능의 ..
01 데이터베이스 관리 시스템의 등장 배경과거에는 데이터를 관리하기 위해 파일 시스템(file system)이라는 소프트웨어 이용데이터를 파일로 관리할 수 있도록 파일을 생성/삭제/수정/검색하는 기능을 제공운영체제와 함께 설치 됨응용 프로그램별로 필요한 데이터를 별도의 파일로 관리파일 시스템 환경에서는 응용 프로그래머가 파일의 논리적인 구조 뿐 아니라 물리적인 구조까지 정확히 파악해야 함필요한 데이터에 직접 접근하여 처리하는 응용 프로그램 개발을 위해파일 시스템의 문제점같은 내용의 데이터가 여러 파일에 중복 저장된다.파일 시스템에서는 응용 프로그램 별로 파일을 유지하므로 같은 데이터가 여러 파일에 저장될 수 있다. 데이터 중복성(data redundancy) 문제가 발생한다.데이터가 중복되면 저장 공간이..