[바킹독 실전 알고리즘] 강의 노트 _ 0x00강~0x02강

바킹독 실전 알고리즘 강의를 듣게 되어서 강의 필기를 할겸 정리용으로 글 씁니다.

 

0x00강 

대상 : c/c++언어를 알고 있지만 자료구조/알고리즘은 약한 사람.

목표: 삼성 SW test A형과 B형 중간 수준의 코딩 테스트. 

 

강의: 총 32강 (2~4달 정도 소요)

 

코딩 테스트: 시간 제한,메모리 제한 안에서 문제를 해결하는 시험.

-> 어떤 테이스 케이스에서 오답인지 알려주지 않음.

 

사이트 추천: SW Expert Academy

 

 

• 배경지식: 다양한 알고리즘, 자료구조, 기타테크닉.
• 문제 해결 능력: 배경지식을 문제에 맞게 변형해서 적용 시키는 능력.
• 구현력: 생각한 풀이를 코드에 잘 옮길 수 있는 능력.

 

---

0x01강 기초 코드 작성 요령1

 

1) 시간, 공간 복잡도.

 

시간복잡도: 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계.

빅오표기법: 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법. 

 

공간복잡도: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계.

512MB =1.2억개의 int

 

int func1(int arr[], int n){ //1
	int cnt=0;  //1
    for(int i=0; i<n; i++){  //n*(2+
    	if(arr[i]% 5==0) cnt++; //2+1)
    }
   return cnt; //1
  }

5n+3 -> O(n)

 

 

 

빅오표기법

 

• O(N): 선형시간
• 이중  for문 : O(n^2)

 

 

int fuc1(int N)
{
	int sum;
    for(int i=0; i<N; i++)
    {
    
	if(i&5==0 || i%3==0)
    	{
    		sum+=i;
    	}
    
    }
    
    return sum;
    
}

 

---

bool func2(int arr[], int N)
{
	int sum=0;
	for(int i=0; i<N; i++)
    {
   		for(int j=1+i; j<N; j++)
        {
    		if(arr[i]+arr[j]==100){return 1;}
         
         }
    }
    return 0;
    
}

 

---

bool func3(int N)
{	
	int i=1;
	while(i<N)
    {	
        if(i*i==N)
        {
        	return 1;
        }
        
        i++;
    }
    return 0;
        
    
    
}

---

int func4(int N)
{	
	int num=0;
    int i=2;
	while(i<N)
    {	
    	num*=i;
        if(num>N)
        {
        	return num/2;
        }
         
    }
    return 0;
        
    
    
}

 

 

---

 

2) 정수 자료형 (+2의 보수법)

 

char : 1byte =8bit

 

unsigned char 0~2^7=2^8-1= 0~255

char -2^7~2^6=  2^7-1= -128~127

 

피보나치 수열을 구하다 int 자료형 크기를 넘어서면 long long을 써야함.

 

정수 오버플로우

---

3) 실수 자료형 (+IEEE)

 

1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다. 

-> double을 쓰는 것을 추천.

 

2. double에  long long 범위의 정수를 함부로 담으면 안된다

-> 허용 범위가 다름.

 

3. 실수를 비교할 때는 등호를 사용하면 안된다. 

10의 9승 -> 1e9

10읠 -12 -> 1e-12

 

---

0x01강 기초 코드 작성 요령1

 

C/C++언어의 기초가 잘되어 있는지 점검

- call by value/call by reference

- STL: vector

(그냥 쓰면 vector는 값으로 복사)

 

표준 입출력 : string 타입은 공백에 민감함. 

-> char로 선언하고 getline()을 대신 쓰는 방법도 있음.

ios::sync_with_stdio(0)  // c++ 과 c의 stream의 동기화를 끊는 명령어.

 

buffer : 임시 저장소. 

cin.tie(nullptr)  // 입력과 출력이 여러번 나오는 경우_ 버퍼를 비우지 않고 수행하게 하는 명령어.

 

endl은 쓰지 말것.

 

코딩 테스트와 개발은 다르다.

코딩 테스트:  내가 헷갈리지 않는 범위 내에서 최대한 타이핑을 줄이기.

 

출력 맨 마지막에 공백 혹은 줄바꿈이 추가로 있어도 상관이 없음.

 

디버거를 굳이 사용하지 않아도 됨.-> 권장.