1.알고리즘 기본

입력 / 처리/ 출력
세단계로 나눠서 생각하는 훈련을 해야 한다.

2. 복잡도

---

2-1. 시간복잡도

'시간'으로 복잡도로 처리하느 것이 아니라 '연산횟수'로 복잡도를 처리한다.
Big-O표기법으로 표시한다.
상수 다 빼고 나타내는 표기법이다.
연산의 횟수가 2n+1이면 O(2n)으로 나타낼 수 있다.

2-2. 공간복잡도

'메모리'의 문제이다. 요즘에는 메모리가 싸져서 효율성을 위해 시간복잡도를 위해서 공간복잡도를 희생하는 방향으로 간다.

3. 정렬

---

3-1. 버블정렬

function bubbleSort(){
	let array=[1,3,5,7,9,77,65,42];

  	for(i=1;i<array.length;i++){
    	for(j=0;j<array.length-1-i){
          if(array[j]>array[j+1]){
            [[array[j],array[j+1]]=[array[j+1],array[j]];
    }
  console.log(array)
}
      

op라는 변수 넣어서 해보기

let array=[1,3,5,7,9,77,65,42];

function bubbleSort(arr,op){
  	for(i=1;i<arr.length-1;i++){
    	for(j=0;j<arr.length-1-i){
          if(op(arr[j],arr[j+1])){
            [[arr[j],arr[j+1]]=[arr[j+1],arr[j]];
    }
  console.log(array)
}

bubbleSort(array,op(ele1,ele2)=>ele1>ele2); //오름차순
      //내림차순으로 하려면  ele1<ele2

3-2. 선택정렬

원소의 취리를 먼저 정한 후 어떤 원소를 넣을지 선택하는 알고리즘.

function selectionSort(arr){
	for(i=0;i<arr.length;i++){
		for(j=i;j<arr.length;j++)
			if(arr[i]>arr[j]){
				[arr[i],arr[j]]=[arr[j],arr[i]];
			}
	}	
    console.log(arr)
}

arr1=[1,3,7,8,9]

selectionSort(arr1);

범용적인 함수로 바꾸어주기 위해서 op라는 변수를 넣어보자.

function selectionSort(arr,op){
	for(i=0;i<arr.length;i++){
		for(j=i;j<arr.length;j++)
			if(op(arr[i],arr[j])){
				[arr[i],arr[j]]=[arr[j],arr[i]];
			}
	}	
    console.log(arr)
}

arr1=[1,3,7,8,9]

selectionSort(arr1,(ar1,ar2)=>ar1>ar2);

문제

🤔내가 푼 풀이

const fs= require('fs');

const [_,input]=fs.readFileSync('/dev/stdin').toString().split('\n');

inputarr = input.split(' ').map(w=>+w);
console.log('input',input);

SelectionSort(inputarr,(ls,lt)=>(ls>lt));
DeleteArray(inputarr)

function SelectionSort(arr,op){
	for(i=0;i<arr.length;i++){
		for(j=0;j<arr.length;j++){
			if(op(arr[i],arr[j])){
				[arr[i],arr[j]]=[arr[j],arr[i]]
			}
		}
	}
}

function DeleteArray(arr){
	for(i=0;i<arr.length;i++){
		if(arr[i]==arr[i+1]){
			arr.splice(i+1,1);
		}
	}
	console.log(arr);
}
console.log(inputarr[2]);

3-3. 삽입 정렬

해당 요소를 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해서 자신의 위치를 찾아 삽입하는 정렬 알고리즘

문제

🤔나의 풀이(잘 못풂)

const fs= require('fs');
 
const input= fs.readFileSync('/dev/stdin').toString().split('\n');
 
let number_arr = input[0].split(' ').map(w=>+w);
let input_arr = input[1].split(' ').map(w=>+w);
 
let memory_arr = new Array(number_arr[0]).fill(0);
for(i=0;i<number_arr[1];i++){
	if(index(memory_arr,input_arr[i])){
		memory_arr.splice(parseInt(index(memory_arr,input_arr[i]))+1,1);
		memory_arr.unShift(input_arr[i])
	}else{
		//만약 메모리에 없다면
		//그 중에서 배열의 끝값이 0이 아니라면
			memory_arr.pop();
			memory_arr.unShift(input_arr[i]);
	}
}
function index(arr,num){
	for(i=0;i>arr.length;i++){
		if(arr[i]==num) return i;
 
	}
	return false;
}
 
console.log(memory_arr)

function main(){
	let [S,N] =propmpt("S,N").split(" ").map(x=>Number(x));
  	let cache = new Array(S).fill(0);
  
  	for(let i = 0; i < N; ++i){
       let task = Number(prompt("task"));
      
      	let taskIndex = S - 1;
      	for(let j=0;j<S;++j){
          //Cache Hit인가?
      		if(cache[j] ==task){
              taskIndex =j;
              break;
            }
        }
      
      //삽입할 위치를 제외하고 나머지 부분 복사==선택정렬
      	for(let j = taskIndex;j>0;--j){
          cache[j]=cache[j-1];	
        }
		cache[0]=task;
    }
  console.log(cache);
}

main();