Yoon Da Yeong

I am an amazing person.

Basic

문제 해결 순서

  1. 예제 답 계산
  2. 알고리즘 떠올리기 & 시간 복잡도 계산
  3. 코드 작성
  4. 디버깅 or Print

에러 종류

  1. Wrong Answer

    => 테스트 케이스 직접 만들어보기(아주 작거나 아주 큰 값으로)

  2. Runtime Error

    => 보통 선언한 배열의 크기보다 더 큰 index에 access하려고 뜨기 때문에 확인

  3. Time Limit Exceed

    => 시간복잡도 계산해서 더 적은 시간의 알고리즘 구현

  4. Memory Limit Exceed

    => 메모리 줄이기

  5. Compile Error

    => 에러 내용 확인

시간복잡도

image

​ -> 마지막 for문에서 1로 다 바꿔주기 때문에 if문은 한번만 걸려서 O(NM)임

  • 사용방법

    (for문 1억번 -> 1초)

    1. N<=10

      => O(N!), O(2^N), O(3^N)

    2. N<=20

      => O(2^N)

      (좋은 알고리즘 생각할 필요 X)

    3. N<=100

      => O(N^4)

      (4중 for문까지 가능)

    4. N<=500

      => O(N^3)

      (3중 for문까지 가능)

    5. N<=1000

      => O(N^2), O(N^2*lg N)

      (이중 for문까지 가능)

    6. N<= 100,000

      => O(NlgN), O(N)

      (이중 for문 안됨! 좋은 알고리즘 생각해야 함)

간단한 반복문

  • for문

    for(int i = s_idx1, j = s_idx2;
      	i <= e_idx1 && j <= e_idx2;
    	i++, j++)

    => 위와 같이 변수 2개를 동시에 선언하기 가능!

  • 숫자의 규칙 출력

    => 이때 수학적 계산을 하려고 하지 말기!!

    ex)

    image

    • 안좋은 예

      ->규칙을 수학적으로 찾음

      int n = 4;
for(int i =0; i<n; i++){
    for(int j = 0; j<n;j++){
        cout<<(n*i +j + 1)
    }
    cout << endl;
}

    • 좋은 예

      -> 규칙 찾기 & 변수 활용

      int n = 4;
int cnt = 1;
    
for(int i =0; i<n; i++){
    for(int j = 0; j<n;j++){
        cout<<cnt++<<" ";
    }
    cout << endl;
}

최대 최소

  • 배열에서 최댓값 찾기

    -> 초기값 설정하기!

    # include <iostream>
# include <climits>
  
using namespace std;
   
int main(){
    int arr[5] = {-2, -5, -3, -4, -10};
      
    int max_val = INT_MIN; // 초기값을 매우 작은 값으로 잡기
    for(int i=0;i<5;i++){
        if(max_val<arr[i])
            max_val = arr[i];
    }
    cout<<max_val
}

    최댓값 구하기 -> 초기값을 매우 작은 값으로!

    최솟값 구하기 -> 초기값을 매우 큰 값으로!

문자열 다루기

  • 문자열 거꾸로 출력하기

    -> 내장 함수 이용

    #include <iostream>
#include <string>
  
using namespace std;
int main(){
    string input_str = "leebros";
      
    reverse(input_str.begin(), input_str.end());
      
    cout << input_str;
    return 0;
}

  • 문자열 첫 글자 수정하기

    -> 인덱스로 접근

    (쉬우므로 코드 생략)

2차원 Array

  • 2차원 배열에 테두리에 숫자 채워넣기

    image

    • step 별로 채우기

      -> for문 4개로 각 변마다 채우기

    • dx dy 테크닉

      image

      ​ ※ dx, dy를 행렬로 따져서 생각!

      # include <iostream>
    
using namespace std;
    
bool in_range(int x, int y){
    return 0 <= x && x<4 && 0 <= y && y < 4;
}
    
int main(){
    int grid[4][4]= {};
    
int dx[4] = {0,1,0,-1}, dy[4]={1,0,-1,0};
int dir = 0;
int num =1;
    
for(int x=0, y=0;;x=x+dx[dir], y=y+dy[dir]){
   	grid[x][y] = num++;
        
   	int new_x =  x+dx[dir], new_y = y+dy[dir];
    if(!in_range(new_x,new_y)) //격자에서 벗어나면
        dir = dir + 1;//방향 바꿔주기
        
    if(new_x == 0 && new_y == 0)//처음 위치
        break;
	}
    return 0;
        
}

배열 정렬

  • 오름차순 정렬

    -> 내장 함수 사용(algorithm - sort())

    #include <iostream>
#include <string>
#include <algorithm>
  
using namespace std;
  
int main(){
    int arr[5] = {3, 1, ,2, 5, -1};
    string str = "leebros";
      
    sort(arr, arr + 5);
    sort(str.begin(),str.end());
      
    return 0;
}

  • 내림차순 정렬

    -> 내장 함수 사용(algorithm - sort(start,end,greater))

    #include <iostream>
#include <string>
#include <algorithm>
#include <functional>
  
using namespace std;
  
int main(){
    int arr[5] = {3, 1, ,2, 5, -1};
    string str = "leebros";
      
    sort(arr, arr + 5 , greater<int>());
    sort(str.begin(),str.end(),greater<char>);
      
    return 0;
}

Object 정렬

  • 2개 이상의 정보를 정렬

    -> class 사용

    ex) 과일 정렬하기

    ​ -> custom 비교함수

    • 과일의 신선도와 가격을 오름차순 정렬(신선도기준, 신선도 같으면 가격)

      #include <iostream>
#include <algorithm>
#include <vector>
    
using namespace std;
    
class Fruit{
    public:
    	int freshness;
    	int price;
    	Fruit(int freshness, int price){ // 매개변수를 가진 생성자
            this->freshness = freshness; //멤버 변수 초기화
            this->price = price;  // 멤버 변수 초기화
        }
};
bool cmp(const Fruit &a, const Fruit &b){
    if(a.freshness != b.freshness)
        return a.freshness < b.freshness;
    return a.price < b.price;
}
int main(){
	int freshnesses[5] = {3,5,3,2,1};
    int prices[5] = {5, 4, 3, 6, 2};
    vector<Fruit> fruits; // 벡터 선언
        
    for(int i = 0; i<5; i++)
        fruits.push_back(Fruit(freshnesses[i], prices[i]));
        
    sort(fruits.begin(), fruits.end(), cmp);
        
    return 0;
}

      생성자(Constructor)

      ​ : 클래스의 객체가 인스턴스화될 떄 자동 호출되는 종류의 멤버함수

      벡터(vector)

      ​ : 크기를 변경할 수 있는 컨테이너(같은 타입의 데이터를 모은 객체)

      • 선언 방법

      ​ vector<자료형> 컨테이너 이름

      • front(), back() 사용 X

        => begin(), end() 사용

※ [코드트리에서 강의한 내용을 바탕으로 작성함]

​ https://www.codetree.ai/

You may also enjoy