목록알고리즘 문제풀기/SW Expert Academy (19)
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWgqsAlKr9sDFAW0 정수 N (1 D5라서 겁먹고 시작했는데 단순한 문제였다. 문제가 어렵다기 보다는 테스트 케이스가 10,000개에 수의 범위가 10^12기 때문에 어떤 방법으로 시간을 줄여서 풀 것인지가 중요한 문제이다. 따로 줄이는 과정을 생각해보지도 않았고 while문 돌렸는데 풀려서.. 다른 사람들이 어떤 방법으로 시도를 했고 시간초과로 고민을 하는지는 잘 모르겠다. -------------------------------------------------------------------------------------..
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE 없음 100만 이하의 모든 소수 출력하기 "에라토노스의 체"라는 이론을 사용할 것이다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 간단하게 설명하면 우선 100만 이하의 2의 배수를 모두 지운다. 다음으로 3의 배수를 모두 지운다. 진행 중 지워..
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo TestCase ( 0) { arr1[index1] = num1 % 10; index1++; num1 /= (ll)10; } while (num2 > 0) { arr2[index2] = num2 % 10; index2++; num2 /= (ll)10; } int count1 = 0; // 앞자리수부터 차례대로 더하는 변수 int count2 = 0; int cur_num = 0; // 계산중인 자리수 저장하는 변수 // 일의자리 제외 for (int j = index1 - 1; j > 0; j--) { cu..
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWczm7QaACgDFAWn 각 버스의 노선 정보가 주어지고 입력되는 정류장 번호에 따라 해당 정류장이 포함된 노선의 개수를 출력하는 간단한 문제이다. 노선의 개수 N (1T; for (int test_case = 1; test_case > N; int A[5000] = { 0 }; int B[5000] = { 0 }; for (int i = 0; i
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT&categoryId=AWS2h6AKBCoDFAVT&categoryType=CODE 이 문제는 산의 높이를 순서대로 저장한 배열에서 극대값을 찾는 문제이다. 산의 높이는 10^9까지 가지만 산의 개수가 50,000개 이하이므로 long long을 사용하지 않았다.(산의 높이를 더하는 문제였으면 long long을 사용해야 한다.) 기본적인 아이디어부터 살펴보자. 극대값이 있고 그 주변을 감쌀 수 있는 범위의 개수를 찾는 문제이다. 순서대로 증가한 값이 극대값 앞에 2개 있고 순서대로 감소한 값이 극대값 뒤에 2개가 있다면..
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWd7sgDatsMDFAUh&categoryId=AWd7sgDatsMDFAUh&categoryType=CODE 강의의 수 n과 들을 수 있는 강의의 수 k가 주어진다. ( k 사용한 방법은 강의의 최대 효율이 10000이므로 효율에 따라 배열을 만들어서 n개의 강의를 입력받을 때마다 해당 효율의 count를 늘려준다.-> 앞에서부터 탐색하며 전부 스택에 넣는다.-> 새로운 스택에 k개만큼 pop하여 push한다. 2. 만들어진 stack을 pop하며 result에 더하고 2로 나눈다. * 강의의 개수가 적기 때문에 편의를 위해 새로운 stack에 ..
문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTN0cKr1oDFAWD 간선을 지나는 비용은 1로 동일하다. 이 때, 여러 개의 중간 지점을 순서대로 지나는 경로의 최솟값을 구하는 문제이다. 우선, 대각선의 길을 제외하고 보자. 모든 간선의 비용이 1이므로 최솟값은 x값의 차이 + y값의 차이 이다. 이 상황을 Case 1이라고 한다. 이제 남은 부분은 대각선이 추가되는 경우이다. Case 1에서 대각선을 추가해보면 아래와 같다. 위 상황에서 대각선을 이용해서 비용을 줄일 수 있는 경우는 어떤 경우가 있을까? 1. x와 y의 값이 +1 +1인 경우 ( 둘 다 증가하는 경우 )2. x와 y..
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWxqfhKAWgDFAW4&categoryId=AWWxqfhKAWgDFAW4&categoryType=CODE 이 문제의 핵심은 간단하다. 우선, 개구리가 몇 번을 울 수 있다는 제한이 없다. 개구리는 몇 번이고 울 수 있다. 하지만 'c' 'r' 'o' 'a' 'k' 의 문자를 순서대로 말해야 한다. 즉, 한 개구리가 5글자를 말하기 전에 울음소리가 시작된다면 이는 최소 2마리가 필요하다는 뜻이 된다. 문제 정의 및 해결방법을 떠나서 가장 먼저 고민했던 부분은 입력이 들어오는 형태이다. 입력을 잘 살펴보면, 한 테스트케이스에 몇 개의 문자가 들어..