🚀 알고리즘이란?
- 프로그램을 수행하기 위한 일종의 단계적 방법
- 어떤 문제를 해결하기 위한 절차
📑 슈도코드
- 프로그래밍의 문법을 따라 쓴것이 아닌, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써 놓은 코드
✋알고리즘의 성능분석 5가지
1. 정확성
2. 작업량
3. 메모리 사용량
4. 단순성
5. 최적성
🧭 시간 복잡도(Time complexity)⭐⭐⭐⭐⭐
- 실제 걸리는 시간을 측정
- 실행되는 명령문의 개수를 계산
표기법 : 빅오(O) 빅-오메가(Ω) 빅-세타(θ)
순서 : 1, logn, n, nlogn, n^2, 2^n, n!
완전 검색(exhaustive serach)
- 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
- 경우의 수가 작을 때 유용함!
그리드 알고리즘
- 여러 경우 중 하나를 결정해야할떄마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방법
머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됨.
- 해답을 못 찾는 경우도 있음 유의할 것.
정렬(Sort)
- 2개 이상의 자료를 특정 기준에 의해 재배열 하는것
key: 자료 그 자체를 의미함.
버블,카운팅,선택,퀵삽입병렬
버블 정렬 : 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨.
- 시간 복잡도 : O(n2)
카운팅 정렬(계수) : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는 세는 작업을 하여, 선형 작업 효율
제한사항 : 정수나 정수를 표현 할 수 있는 자료에 대해서만 적용 가능, 공간할당을 위해서 집합 내의 가장 큰 정수를 알아야함
- 시간 복잡도 : O(n+k)
응용문제1 SWEA 1204
최빈수(최고 빈도수) 문제 구하기
#include<iostream>
using namespace std;
int main()
{
int i, T, j,k;
int index =0;
int count[101];
scanf("%d", &T);
for(int test_case = 1; test_case <= T; ++test_case)
{
cin>>test_case;
fill_n(count, 101, 0);
for(i=0; i<1000; i++){
cin >> index;
count[index]++;
}
int counter = 0;
int Max =0;
for(i=0; i<=100; i++){
if(count[i] >= Max){ // 빈도수 가장 큰거 찾기
Max = count[i];
counter = i ;
}
}
cout << "#" << test_case << " " << counter <<"\n";
}
return 0;
}깨달은 점
응용문제2 SWEA 1206
빌딩높이에 따른 조망권 건물 확인하기
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int higher[1001]={};
int max1,max2,n,i;
int test_case;
int sum=0;
int T=10;
for(test_case = 1; test_case <= T; ++test_case)
{
fill_n(higher, 1001, 0);
cin >> n;
for(int i=0; i<n; i++)
{
scanf("%d ", &higher[i]);
}
sum = 0;
for(int i=2; i<n-2; i++)
{
int max1 = max(max(higher[i-1],higher[i-2]), max(higher[i+1], higher[i+2]));
if(higher[i] > max1)
sum += higher[i] - max1;
}
cout << "#" << test_case << " " << sum<<"\n";
}
return 0; //정상종료시 반드시 0을 리턴해야합니다.
}
깨달은 점🤦♂
c++의 가장 장점은 STL을 사용하지 않고 알고리즘을 구현하기에는 제한적이었다.
Algorithm 라이브러리 함수를 이용해서 앞으로는 조금 더 편리한 알고리즘 구성이 가능할 것 같다
응용문제3 SWEA 1208
평탄화 작업(Flatten)
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int MAX,MIN, n, i,j,k;
int arr[100]={};
int T=10;
int index=0;
for(int test_case = 1; test_case <= T; ++test_case) // 테스트 케이스 10번
{
cin>> n; // 덤프 수 입력
fill_n(arr,101,0);
for(i=0; i<100; i++){
cin>> arr[i]; // 높이 입력 100개
}
for(i=0; i<n; i++) // 입력된 덤프 수 만큼 덤프 실시 (5번)
{
sort(arr, arr+100);
if(arr[99]- arr[0]>=1) // 둘의 차이가 1이상이면
{
arr[0] = arr[0] + 1; // 정렬된 가장 첫번재 수는 +1
arr[99] = arr[99] - 1; // 정렬된 가장 작은 수는 -1
}
else
break;
}
sort(arr, arr+100);
cout << "#" << test_case << " " << arr[99]-arr[0] <<"\n";
}
return 0;
}
깨달은 점🤦♂
계속 문제를 풀면서 실수하는 것은 라이브러리 함수에 의존하지 않고 혼자서 새로운 알고리즘을
구현할려고 시간을 너무 지나치게 보내는 것이다. 물론 그것이 후에 도움이 될 수도 있겠지만
라이브러리 함수를 사용하는 것이 복잡도나, 실제 풀이시간면에서 더 효울적이라는 것을 알게
되었고 나의 아집을 꺾고 조금더 효율적인 프로그래밍 사고를 가져야 겠다.
다재다능