IT 공부한거 올리는 블로그

0이 입력되면 최대 값 혹은 0 출력, 그 외의 값이 입력되면 배열에 저장 처음 생각했던 코드 deque로 최댓값 한개를 맨앞에 두고 0이 입력됐을때 pop하고 최댓값을 또 맨앞에 두는 방식 정렬되지 않은 리스트에서 최댓값을 찾기 위해 0이입력될때마다 완전탐색을 했다 #include #include #include using namespace std; int findidx(deque dq); bool cmp(int a, int b){ return a>b; } int main(){ deque dq; int n; cin>>n; int max=0; for(int i=0; i>temp; if(dq.size()>0){ max=dq[0]; } if(temp==0){ if(dq.size()==0){ cout

문제 이해부터 해보자 수열 {0,1,2,4,3,5}가 들어왔을때 두 수를 묶거나 묶지 않을 수 있다 그리고 묶는 것은 중복되지 않는다 무슨소리냐면 예를들어 (1,2)를 묶었는데 (2,4)로 또 2를 중복시켜 묶을 수는 없다는 것이다 묶게되면 묶은 두 수 끼리 곱해서 더해지고 묶지 않으면 그냥 더해진다 {0,1,2,4,3,5}의 이 규칙을 통해 최댓값을 내는 경우는 0,1, {2,3}, {4,5}이다 그러면 0+1+(2*3)+(4*5)가 되어 27이 된다 다음은 테스트케이스를 분석해보자 -1 2 1 3 이 경우는 -1,1,(2,3)을 해주면 -1 + 1 + (2*3) = 6이 최댓값 0 1 2 4 3 5 (5,4), (3,2) 1,0 20+6+1=27 -1 -1 -1 0 1 (-1,0), 1 0+1=1 1..

이 문제는 수빈이의 현재 위치와 동생들의 위치사이의 간격끼리의 GCD(최대공약수)를 구하는 문제이다 그래서 GCD를 구하는 알고리즘을 잘짜야지 통과가 되는데 I=2부터부터 해당 수 까지 일일히 찾으니 너무 오래걸린다 구글링해보니 GCD를 구하는 유명한 알고리즘 유클리드 호제법이라는게 있어서 사용해보았다 유클리드 호제법이란 수 A,B 가 있을때(A>B) A%B한 값이 0이 될때까지 반복하면 A값이 최대공약수라는 알고리즘이다 증명은 딱히 필요없고 어떻게 그게 되는지 확인해보겠다 A=12, B=8이라 가정 First step A=12, B=8 Second step A=12%8, B=8 -> A=4, B=8 -> A=8, B=4 Third step A=8%4, B=4 -> A=0, B=4 -> A=4, B=0 ..

그리디 알고리즘이고 사용할 수 있는 회의실의 최대 개수를 출력하면 된다 알고리즘 시간에 본 적 있는 유형인데 Interval Scheduling Problem이다 자료에서 힌트를 얻어 끝나는 시간이 제일 빠른 거 부터 고르는 알고리즘을 선택했다 시간 초과난 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false); int n,count=0; cin >> n; int endindex=0,startindex=0; int** schedule = new int* [n]; for (int i = 0; i < n; i++) { schedule[i] = new int[2]; } for (int i = 0; i < n; i++) { f..

문제를 설명하자면 주어진 입력값에 대해 홀수인 소수의 합으로 나타낼수 있는 값중 가장 차가 큰 합으로 나타내라는 것이다 그리고, 홀수인 소수의 합으로 나타낼 수 없으면 문구를 출력한다 예를들어 10을 홀수인 소수로 나타내라고하면 10 = 3 + 7 10 = 5 + 5 로 나타낼 수 있다(7 + 3은 없다 a + b형태에서 b가 더 크도록 나타내기때문) 여기서 차이가 큰 것은 5 + 5 보다 3 + 7이다 5+5는 차이가 0이고 3+7은 차이가 4기 때문이다 그래서 소수를 판별하는 방법에 에라토스테네스의 체를 이용했고, n으로부터 가장 가까운 홀수인 소수를 찾고 n-소수가 홀수이고 소수를 만족하면 반복문을 탈출해 합으로 나타냈다 그 외에 반복문을 다 돌았는데도 값이 변하지 않으면 홀수인 소수로 나타낼 수 ..

퀵정렬은 기준원소를 잡고 기준원소보다 작은 값은 왼쪽으로 기준원소보다 큰 값은 오른쪽으로 정렬하는 방법이다 따라서 start, end, pivot의 인덱스가 필요하다 알고리즘 예제는 이걸 따른다 기준원소는 첫번쨰,마지막,가운데 어느것을해도 상관은 없다 보통 첫번째 원소를 기준으로 잡고 i=left+1, j=right으로 설정해 i와 j 가 start~end를 돌며 i에서 pivot보다 큰값이 나오면 stop j에서 pivot 보다 큰값이 나오면 stop 그리고 arr[i]와 arr[j]를 swap해준다 i가 j를 넘었을때 stop하고 pivot과 j를 변경해준다 더 이상 swap해주지않고 j를 return해 끝내준다 quicksort(start, j-1) //pivot기준 왼쪽 다시 퀵소트 quickso..

벡터로 구현한 것 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); int n; int X, Y; vector v; cin >> n; for (int i = 0; i > X >> Y; v.push_back({ X,Y }); } sort(v.begin(), v.end()); for (int i = 0; i arr[i][1]; } MergeSort(0, n - 1); for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) { cout

문제 밑에 힌트가 적혀있다 카운팅 정렬을 이용하면 더욱 빠르게 정렬할 수 있다고 counting sort~ 밤 하늘에 퍼어얼 즉 시 알고리즘 자료 찾아 정리를 하자면 배열로 먼저 받고 일일히 비교하며 정렬하는 것이아니라 해당 key값이 몇 번 나왔는지 count하고 key값이 낮은 값부터 count만큼 출력하면 비교 정렬을 하지 않아도 오름차순으로 정렬이 가능하다 그래서 이 강의 자료를 보고 만든 코드 #include using namespace std; int main() { int n;//원소의 개수 int k = 0;//원소는 1~k사이의 수 cin >> n; int* A = new int[n+1];//처음 값 입력받을 배열 int* B = new int[n+1];//정렬된 원소 받을 배열 for ..