전체 글

1197 - 최소 스패닝 트리https://www.acmicpc.net/problem/1197문제최소 스패닝 트리: 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리입력첫째 줄: 정점의 개수 V (1 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, CA번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않음그래프의 정점은 1~V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있음(-2,147,483,648 출력최소 스패닝 트리의 가중치 풀이MST (Minimum Spanning Tree): 최소 스패닝 트리: 모든 정점을 연결하면서, 사이클 없이 간선 가중치 ..

1260 - DFS와 BFShttps://www.acmicpc.net/problem/1260문제방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문, 더 이상 방문할 수 있는 점 X -> 종료정점 번호: 1 ~ N번입력첫째 줄에 정점의 개수 N (1 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호 주어짐어떤 두 정점 사이에 여러 개의 간선이 있을 수 있음/ 입력으로 주어지는 간선은 양방향출력: V부터 방문된 점을 순서대로 출력DFSBFS풀이DFS: 깊게, 한 방향으로 끝까지 파고들다가 돌아옴/ 재귀static void dfs(int node) { System.out.print(node + " "); visited[node] = true; for (int next..

SECTION 1 데이터베이스 기본1. 데이터베이스(DB; DataBase)일정한 규칙/규약 ~> 구조화되어 저장되는 데이터 모음DBMS(DataBase Management System): 데이터베이스 제어, 관리하는 통합 시스템특정 DBMS마다 정의된 쿼리 언어 ~> 삽입/삭제/수정/조회 등 수행실시간 접근, 동시 공유 가능응용 프로그램 DBMS 데이터베이스 엔터티(entity)사람, 장소, 물건, 사건, 개념 등 여러 개의 속성을 지닌 명사서비스의 요구 사항에 맞춰 속성이 정해짐ex. 회원이라는 엔터티 -> 속성: 이름, 아이디, 주소, 전화번호 A가 혼자서 존재 X B의 여부에 따라 종속적 -> A: 강한 엔터티 / B: 약한 엔터티ex. 방은 건물 안에서만 존재 -> 건물: 강한 엔터티 / 방..

11404 - 플로이드https://www.acmicpc.net/problem/11404문제모든 도시 쌍 (a, b)에 대해 도시 a에서 b로 가는데 필요한 비용의 최솟값입력첫째 줄: 도시의 개수 n (2 둘째 줄: 버스의 개수 m (1 셋째 줄 ~ m+2줄: 버스의 정보버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c시작 도시와 도착 도시가 같은 경우 X, 비용 (자연수) 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음출력n개의 줄 출력i번째 줄에 출력하는 j번째 숫자: 도시i에서 j로 가는데 필요한 최소 비용만약, i에서 j로 갈 수 없는 경우 0 출력풀이모든 도시 쌍 (i, j) 간의 최소 이동 비용 구하기=> 플로이드 워셜 알고리즘(Floyd-Warshall Al..

1744 - 수 묶기문제https://www.acmicpc.net/problem/1744길이가 N인 수열 -> 수열의 두 수를 묶어서 그 수열의 합어떤 수를 묶으려고 할 때, 위치에 상관 X 묶을 수 있음 But, 같은 위치에 있는 수(자기자신)를 묶는 것을 불가능어떤 수를 묶게 되면, 서로 곱한 후에 더함ex. {0, 1, 2, 4, 3, 5} -> 합: 0+1+2+4+3+5 = 15But, 2와 3, 4와 5 묶으면 -> 0+1+(2*3)+(4*5) = 27 최대수열의 모든 수는 단 한번만 묶거나 아니면 묶지 않아야 함=> 수열이 주어졌을 때, 각 수를 적절히 묶었을 때 최대합?입력첫째 줄: 수열의 크기 N (N (자연수) 둘째 줄부터 N개의 줄: 수열의 각 수가 주어짐 (-1,000 출력: 합이 최..

문제https://www.acmicpc.net/problem/115013가지 중 한 행동을 함1. 주식을 산다2. 원하는 만큼 가지고 있는 주식을 판다3. 아무 것도 안한다=> 날 별로 주식의 가격을 알려줬을 대, 최대 이익이 얼마나 되는지?ex. 날 수: 3일/ 날 별로 주가: 10, 7, 6 -> 주가가 계속 감소 => 최대 이익: 0주가: 3, 5, 9 -> 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익: 10입력첫 줄: 테스트케이스 수 T각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 N (2 둘째 줄: 날 별 주가를 나타내는 N개의 자연수들 (공백, 날 별 주가 출력각 테스트케이스 별로 최대 이익을 나타내는 정수 출력부호 있는 64-bit 정수형으로 표현 가능풀이미래의 최..