1주차 : 기초 다지기

• C++ 문법 기초 다지기
  • ‘누구나 쉽게 배우는 C++ 프로그래밍 입문’
    • https://www.inflearn.com/course/하루-10분-씨쁠쁠/dashboard
    • 총 42강 완강(7/7 ~ 7/13)
  • ‘it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비 (총 115강)
    • https://www.inflearn.com/course/알고리즘/dashboard
    • 현재 29강까지 완료(섹션 1. 코드구현력 기르기 1 ~ 32강) ← 주내용: 코드구현력을 기를 수 있는 기초 문제들 풀이

2주차 : 기초 알고리즘 다지기

• 정렬 알고리즘 + 예시 문제 풀이 (33 ~ 39강)

  • 배열 또는 벡터 안에 무작위로 배치되어 있는 수들을 오름차순 또는 내림차순으로 배치할 때 정렬이 쓰인다. 정렬하는 방법에는 대표적으로 선택정렬, 버블정렬, 삽입정렬 등이 있다

  • 선택정렬: 해당 수와 선택한 자리에 있는 수를 조건에 맞게 바꾸는 방법 ex) 가장 큰 숫자를 앞에서부터 차곡차곡 채우는 방식으로 배열을 정렬한다.

    • <선택정렬 핵심 코드>

    for (int i=0; i<n-1; i++) {
            idx = i;
            for(int j=i+1; j<n; j++) {
                if(a[j] < a[idx]) idx = j;
            }
            temp = a[i];
            a[i] = a[idx];
            a[idx] = temp;
        }
    

  • 버블정렬: 이웃한 두 수를 비교해 조건에 충족하면 자리를 바꾸는 방법

  • 삽입정렬: 조건에 해당하기 전까지 배열 또는 벡터 안에서 해당 값을 앞 또는 뒤로 땡긴 다음, 조건에 맞을 때 그 자리에 해당 값을 집어넣는 방식.

    • <삽입정렬 핵심 코드>

    for(i=1; i<n; i++) {
            tmp = a[i];
            for(j=i-1; j>=0; j--) {
                if(a[j] > tmp) a[j+1] = a[j];
                else break;
            }
            a[j+1] = tmp;
        }
    

• 이분검색(결정알고리즘) + 예시 문제 풀이 (39 ~ 46강)

  • 배열 또는 벡터 안에서 어떤 조건에 맞는 값을 찾는 문제일 때는 이분검색방법을 먼저 의심해봐야 한다.

  • 이분검색: 배열 또는 벡터의 구간을 시행할수록 찾고자 하는 값의 위치를 기준으로 반씩 줄여서 적은 횟수만으로도 값을 쉽게 찾는 알고리즘 ← 사용하기 위해선 배열 또는 벡터가 이미 정렬되어 있어야 한다.

    • <이분검색 핵심 코드>

    while(lt <= rt) {
            mid = (lt+rt)/2;
            if(a[mid] == key) {
                printf("%d", mid+1);
                return 0;
            }else if(a[mid] > key) rt = mid - 1;
            else lt = mid + 1;
        }
    

3주차 : 투포인트 알고리즘 & 2차원 배열 다루기

• 투포인트 알고리즘

  • 두 개의 포인터를 설정해서 배열을 탐색하며, 조건에 따라 포인터를 한 쪽 또는 양쪽에서 이동시키는 방식으로 연산을 최적화함. ex) 대표적으로 두 배열의 교집합을 구할 때
  • 사용하기 전에 배열은 이미 오름차순 또는 내림차순으로 정렬되어 있어야 한다.

• 2차원 배열을 다룬 문제들 풀기(47 ~ 52강)

  • 2차원 배열을 선언하는 두 가지의 방법 → int arr[10][10] or vector <vector <int>> v(10, vector <int>(10, 0))
  • 만약 2차원 배열 안의 모든 값을 0으로 통일하고 싶을 때, int arr[10][10]은 전역변수로 선언하면 자동으로 0으로 초기화 되고 벡터의 경우에는 vector <vector <int>> v(10, vector<int>(10, 0))과 같이 적으면 안의 모든 값이 0으로 설정된다.
  • 2차원 배열을 사용하는 문제 중 흥미로웠던 문제 예시와 정답 핵심 코드 (48번 각 행의 평균 문제), 이전에 배웠던 이분검색 알고리즘을 사용해서 푸는 것이 가능하였음

  

  for(int i=0; i<9; i++) {
          sum = 0.0f;
          for(int j=0; j<9; j++) {
              sum += v[i][j];
          }
          ave = round(sum/9);
          printf("%d ", ave);
  
          flag = false; lt = 0; rt = 8;
          while(lt <= rt) {
              mid = (lt+rt)/2;
              if(v[i][mid] == ave) {
                  printf("%d\\n", v[i][mid]);
                  flag = true;
                  break;
              }else if(v[i][mid] > ave) rt = mid - 1;
              else lt = mid + 1;
          }
          if(flag == false) {
              if(v[i][mid] > ave) {
                  if(v[i][mid]-ave > ave-v[i][mid-1]) printf("%d\\n", v[i][mid-1]);
                  else printf("%d\\n", v[i][mid]);
              }else {
                  if(v[i][mid+1]-ave > ave-v[i][mid]) printf("%d\\n", v[i][mid]);
                  else printf("%d\\n", v[i][mid+1]);
              }
          }
      }   
  

4주차 : 스택 & 재귀함수

• 스택: LIFO 구조. 프로그램의 작동 방식이 스택 구조를 이용한다.(프로그램이 작동될 때, 스택 안에 스택메모리가 쌓이고, 가장 위에 있는 스택메모리를 먼저 처리한다.) 재귀함수, DFS 등 여러 알고리즘 기법들을 이해하려면 스택에 대해서 이해하는 것이 먼저 필요하다

  -스택을 직접 짜는 방식 ←push()와 pop()함수를 직접 만든다.

  void push(int x) {
      stack[++top]=x;
  }
  
  int pop() {
      return stack[top--];
  }
  

  -C++에서는 #include <stack>을 통해 제공되는 STL을 사용할 수도 있다.

• 재귀함수: 함수 안에서 자기 자신을 다시 호출하는 함수.

  • 재귀함수를 구현할 때 스택 방식을 사용하여 구현한다. 다음과 같은 구조로 구현하는 것이 좋다

    void D(int x) {
        if(/*재귀루틴을 벗어나는 조건*/) return;
        else {
            //재귀함수가 작동하는 코드
            D(x+1);
        }
    }
    

    if와 else를 나누어 if 안에는 재귀루틴을 끝내는 조건을 적고 나머지 코드는 else 안에다 적는다.

• 스택 & 재귀함수 관련 문제들 풀이(57~62강)

  • 인상깊었던 문제 예시와 풀이 코드

    

    int main() {
        stack <int> s;
        int i, j=1, n, m;
        scanf("%d", &n);
        
        vector<char> str;
        for(i=1; i<=n; i++) {
            scanf("%d", &m);
            s.push(m);
            str.push_back('P');
            while(1) {
                if(s.empty()) break;
                if(j==s.top()) {
                    s.pop();
                    j++;
                    str.push_back('O');
                }else break;
            }
        }
        if(!s.empty()) printf("impossible\\n");
        else {
            for(i=0; i<str.size(); i++) printf("%c", str[i]);
        }
    
        return 0;
    }
    

5주차 : DFS: Depth First Search

<DFS와 관련된 여러 알고리즘 개념과 문제들 풀이>

• 이진트리 깊이우선탐색: 이진트리 구조의 자료구조를 탐색할 때 쓰이는 방법

  -전위순회 출력: 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드

  -중위순회 출력: 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드

  -후위순회 출력: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드

  (62 ~ 66강)

• 병합정렬 ← divide and conquer가 핵심. 재귀적으로 배열의 크기를 나눈 다음에 나눠진 배열들을 병합하면서 정렬하는 방식.(67강)