니노니나니

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제모든 정점이 1부터 N까지의 수로 표현되어지는 가중치가 있는 방향 그래프가 주어진다.이때 임의의 두 정점 a에서 b로 가는 최단 경로의 길이를 구하는 프로그램을 작성하세요.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)각 테스트 케이스 첫째 줄에는 정점의 개수 N와 간선의 개수 M이 주어진다.(1 ≤ N ≤ 500, 1≤ M ≤ 100000)이어진 M개의 줄에는 간선의 정보 a, b, c가 주어진다. 이는 정점 a에서 정점 b로가는 간선이 존재하고, 이의 가중치는 c라는 의미이다.풀이#include#include # define INF 999..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제두 개의 DNA 순서열이 있을 때, 이 두 개가 얼마나 비슷한가를 측정할 것이다.DNA 순서열이라는 것은 ‘A’, ‘C’, ‘G’, ‘T’로 이루어진 문자열이다. 두 개의 DNA 순서열의 비슷한 정도는 LCS로 판별할 수 있다.이는 공통된 부분 수열(Subsequence)중 가장 긴 것을 의미한다.두 개의 DNA 순서열이 주어졌을 때, 이 둘의 LCS의 길이를 출력하세요.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)각 테스트 케이스 첫째 줄과 둘째 줄에 DNA 순서열이 입력된다. DNA순서열의 길이는 1,000이하이다.풀이#include#i..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제주어진 N*N흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형을 찾으시오.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)각 테스트 케이스 첫째 줄에는 전체 맵의 크기 N이 주어진다(1 ≤ N ≤ 1,000).그 다음 N줄에 걸쳐서 N개의 ‘0’또는 ‘1’이 입력된다. ‘0’은 비어있는 칸을 뜻하고, ‘1’은 검은 점을 뜻한다.풀이#include#include#include using namespace std;int N;int field[1001][1001] = { 0 };int dp[1001][1001] = { 0 };int ..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제2*N직사각형을 2*1과 2*2타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림을 2*15 직사각형을 채운 한가지 예이다.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 250)각 테스트 케이스 첫째 줄에는 타일의 크기인 N이 주어진다. N은 250보다 같거나 작은 자연수이다.풀이#include#include#include using namespace std;int N;string dp[251];int main(int argc, char** argv){ int test_case; int T; //freopen("in..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제자유직업인인 인테리어 업자가 있다.그는 유명한 인테리어 업자이기 때문에, 여러 요청이 들어온다.하지만 어느 두 요청의 일정이 겹치게 된다면, 두 일정 모두 소화할 수는 없다.즉, 겹치지 않는 요청들로 일정을 구성하여야 한다. 또한 각 요청한 것에 대해 수행하였을 때, 그에 따른 돈을 받게 된다. 우리의 목표는 가능한 일정 중에서 받는 돈의 양이 가장 많은 것을 택할 것이다.위와 같이 총 7개의 일정이 있다고 하자.겹치는 일정이라는 것은 T3를 선택했을 때, T2, T6, T8등을 선택할 수 없다는 것이다.또한 가능한 일정이라는 것은, {T1, T4}, {T8, ..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제2차원 좌표계에 있는 N개의 점이 주어진다.이 점들 중 가장 가까운 두 점의 거리를 구하는 프로그램을 작성하라.단 거리는 Euclidean Distance(Sqrt((x1-x2)2 + (y1-y2)2))를 이용한다.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 25)각 테스트 케이스의 첫번째 줄에는 처음 점의 개수를 나타내는 N이 주어진다. (3 ≤ N ≤ 100,000)다음 N개의 줄에는 각 점의 좌표 x y가 공백으로 구분되어 주어진다. (-100,000 ≤ x, y ≤ 100,000)풀이def Distance(p1, p2): return..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제2차원 좌표계에 있는 N개의 점이 주어진다.N개의 점으로 구성할 수 있는 Convex Hull을 이루는 점의 개수를 구하여라.Convex Hull이란 아래 그림과 같이 모든 점을 포함하는 점으로 연결된 외곽선을 의미한다.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20)각 테스트 케이스의 첫번째 줄에는 처음 점의 개수를 나타내는 N이 주어진다. (3 ≤ N ≤ 100,000)다음 N개의 줄에는 각 점의 좌표 x y가 공백으로 구분되어 주어진다. (-100,000 ≤ x, y ≤ 100,000)풀이#include#include#include usi..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제문자열 S가 주어질 때, 이 문자열에서 두 번 이상 등장하면서 가장 긴 부분 문자열을 찾아내시오.이 때, 부분 문자열이 중첩될 수 있음에 유의하라.예를 들어, S="ababa"인 경우 가장 긴 부분 문자열은 "aba"가 된다.입력첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)각 테스트 케이스의 첫 번째 줄에 문자열 S의 길이 L이 주어진다. (1 ≤ L ≤ 200,000)각 테스트 케이스의 두 번째 줄에 문자열 S가 주어진다. 문자열 S는 알파벳 소문자로만 구성되어 있다.풀이#include#include#include#include#include..

[SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com](https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxy8bKAikDFAW4)문제독서광 동철이는 책을 정말 꼼꼼히 읽는다. 그 증거로, 책에서 어떤 단어가 몇 번 등장하는지 물어보면 정확하게 그 답을 맞춰내는 신기한 능력이 있다.그런데, 특출난 능력이 있으면 누군가는 시샘을 하게 마련이다.동철이의 친구 영수는 동철이의 이런 능력을 의심하고 있었지만, 도저히 그 답이 맞는지 세어볼 수가 없어 당신에게 도움을 요청하였다.영수의 궁금증을 해소해주기 위하여, 책의 내용 B가 주어질 때 특..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제삼성의 강의실은 N개의 방으로 이루어져 있고, 각 강의실에는 한 명의 사원이 강의를 듣고 있다.편의상 각 사원에 1번부터 N번까지 번호를 붙이도록 하자.  하루는 X번 사원의 강의실에서 간담회를 열기로 하였다.각 사원들은 각자의 강의실에서 X번 사원의 강의실까지 갔다가 간담회를 마치고 돌아오려 한다.이 때, 이동하는 경로는 최단 경로로 이동한다. 다만 문제는 각 강의실을 잇고 있는 M개의 길이 일방통행이라는 점이다.결국, 그 강의실까지 가는 경로와 그 강의실에서 돌아오는 경로가 다를 수 밖에 없다.각 길의 정보가 주어졌을 때, 간담회에 참석했다가 돌아오는데 소요되는..