코딩하기 좋은날

https://www.acmicpc.net/problem/4948 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 주어진 n에 대하여 n보다 크고 2n보다 작거나 같은 범위의 소수의 개수를 출력하는 문제입니다. 저는 에라토스테네스의 체를 이용하여 2n보다 작은 소수를 모두 찾고 n과 2n사이의 소수의 개수를 카운트해서 풀었습니다. 다음은 코드입니다. #include //에라토스테네스의 체 using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int N = 1; bool arr[300000]; while(1) { fill_n(arr, 300000, true); arr[0] = false; ..

https://www.acmicpc.net/problem/1929 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 에라토스테네스의 체를 이용하여 소수를 구하는 문제입니다. 시간 제한이 있기 때문에 단순히 소수를 구하는 방법으로는 풀 수 없습니다. 에라토스테네스의 체란 어떤수 이하에 있는 모든 소수를 구해야 할 때 2의 배수를 모두 제거하고 그다음 3의 배수를 모두 제거하고 그다음 5의 배수를 모두 제거하는 방법으로 소수들을 골라내는 방법입니다. bool 배열을 통하여 구현을 하였습니다. 다음은 코드입니다. #include //에라토스테네스의 체 using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(N..

https://www.acmicpc.net/problem/2108 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 각각 입력받은 숫자들의 산술평균, 중앙값, 최빈값, 최댓값과 최솟값의 차이를 구하는 문제였습니다. 다른값들은 구하는게 아주 쉬운데 최빈값이 그나마 좀 구하기 힘들었습니다. 양수와 음수 배열을 하나씩 만들고 각 숫자가 나온 빈도를 배열에 저장한 뒤 가장 많은 빈도가 나온 값을 찾으면 됩니다. 그런데 최빈값이 여러개인 경우엔 그 최빈값들 중 두번째로 작은 숫자를 출력하라고 되있으므로 동일한 최빈값이 나올 경우 벡터에 저장 한후 두번째 원소를 출력해주면 됩니다. 다음은 코드입니다. #include #include #include #include using namespace std;..

https://www.acmicpc.net/problem/2800 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 괄호쌍이 위치해 있는 인덱스를 저장 한 후 함수의 재귀 호출로 해결을 하여야 합니다. '('을 만났을 경우 그 짝인 괄호를 지우는 경우와 지우지 않는 경우로 나누어서 진행 하면 해당 하는 모든 경우를 구할 수가 있습니다. 즉 입력받은 문자열을 비어있는 문자열에 처음부터 더해가며 '('가 나왔을 경우 이 괄호를 제거하고 가는 경우, 그렇지 않은 경우를 재귀적 호출로 모두 구해낼수가 있습니다. 계속 시간 초과가 나서 다른분들 풀이를 참고하여 풀었는데 재귀 함수는 역시 어려운것 같습니다.. #include #include #include #include using namespace..

https://www.acmicpc.net/problem/1092 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 크레인을 이용해 박스를 옮기는데 걸리는 최소 시간을 구하는 문제입니다. 각 크레인은 무게 제한이 있어 더 무거운 박스는 옮길 수 없습니다. 저는 리스트를 이용해 크레인이 옮길 수 있는 박스들을 제거해 가며 문제를 풀었습니다. 박스가 저장된 리스트와 크레인이 저장된 배열을 각각 sort 시킨뒤 가장 무거운 박스를 해당 크레인이 옮길 수 있는지를 검사하고 옮길 수 없다면 그다음으로 무거운 박스를 옮길 수 있는지를 검사 하였습니다. 만약 어떤 크레인이 리스트의 끝까지 갔는데도 어떠한 박스도 옮길 수 없다면 그 크레인의 뒤에 있는(그 크레인보다 무게제한이 더작은) 크레인들을 포함하여..

https://www.acmicpc.net/problem/2399 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 각 인덱스에서 다른 모든 인덱스와의 차이의 합들을 모두 구하는 문제입니다. 입력이 10000개이고 시간 제한이 1초라서 O(N^2)은 뭔가 애매할거 같아서 저는 0번째 인덱스부터 가면서 나오는 수들의 절댓값을 2배씩하면서 앞으로 진행 하였습니다. 이런식으로 하면 처음에는 n-1번의 연산을 하고 이후에 한번씩 줄어 마지막에 1번만 연산을 하면 되므로 각 인덱스를 n-1번씩 해주는 방법보다 효율적이라고 할 수 있습니다. 아래는 코드입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_std..

https://www.acmicpc.net/problem/3047 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 입력 받은 숫자가 크기 순으로 A B C문자에 매칭이 됩니다. 그리고 두번째에 입력받은 문자에 따라 case문에 넣어서 출력을 시키면 됩니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int arr[3]; string str; cin >> arr[0] >> arr[1] >> arr[2] >> str; sort(arr, arr+3); //입력받은 숫자를 오름차순으로 정렬 for(int i = 0; i < 3; i+..

https://www.acmicpc.net/problem/1205 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 점수를 내림차순으로 입력받고 새로운 점수를 등록해서 그 점수의 등수를 구하는 문제입니다. 랭킹 리스트가 꽉차있을 땐 가장 낮은 점수와 비교해 그점수보다 크지 않으면 -1을 출력하면 됩니다. 다음은 코드입니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); vector v; int N,score,P; cin >> N >> score >> P; int rank = 1; for(int i = 0; i < N; i++) { //..