경일 메타버스 20220622 12주차 3일 수업내용. 자료구조와 알고리즘, 오답노트

백준 풀이

백준 1406 에디터 풀이

• 2022. 06. 22 리스트 예제 : 백준 1406번 에디터 내 풀이

• 2022. 06. 22 리스트 예제 : 백준 1406번 에디터 풀이

• 2022. 06. 22 리스트 예제 : 백준 1406번 에디터 제출번호_28348215_jinhan814

백준 5397 키로거 풀이

• 2022. 06. 22 리스트 예제 : 백준 5397번 키로거 내 풀이

• 2022. 06. 22 리스트 예제 : 백준 5397번 키로거 풀이

range-based for loop

• 컨테이너를 순회할 일이 너무 많다.
  그런데 순회할 때마다 반복자를 치기가 너무 귀찮다.

  for (list<char>::iterator iter = lst.begin(); iter != lst.end(); ++iter)
  {
  
  }

  • 그래서 range-based for loop이 등장했다.

  for (char ch : lst)
  {
  		// 컨테이너를 수정하면 절대 안된다. X
  		// 컨테이너에 데이터를 삽입하거나 삭제하면 X.
  }

• 연결 리스트의 단점

  캐싱에 있어서 손해

자료

https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

스택

• 리스트의 일종으로 연산이 한 쪽 끝에서만 이뤄지는 자료구조.
  컨테이너 어댑터이다.

  • 컨테이너 어댑터 :
    구현을 할 때, 기존의 컨테이너에서 그 끝에서만 연산이 이루어지도록 제한해 놓는다.

    • vector :
      stack.push() ⇒ vector.puch_back()
      stack.pop() ⇒ vector.pop_back()

    • forward_list :
      stack.push() ⇒ forward_list.puch_front()
      stack.pop() ⇒ forward_list.pop_front()

    • list : 양쪽 다 된다.
      stack.push() ⇒ list.puch_back(); list.puch_front()
      stack.pop() ⇒ list.pop_back(); list.pop_front()

• LIFO(Last-In First-Out)구조 :
  가장 나중에 들어간 것이 처음에 나온다.

• 스택의 끝을 위(Top), 스택의 시작을 밑(Bottom)이라 한다.

• 괄호가 올바른지 검사 / 후위 표기식 / DFS 등에 사용

• STL 상의 구현

  • std::stack :
    https://en.cppreference.com/w/cpp/container/stack

• std::stack의 사용

  2022. 06. 22 std::stack의 사용 예시 코드

C++ 표준 입력 함수

• <iostream>에 존재

- cin

• 표준 입력 버퍼에서 개행 문자를 제외한 값을 가져온다.

• 공백, 개행을 무시한다.

• 사용 예 :

  char ch;
  cin >> ch;
  int num;
  cin >> num;
  std::string str;
  cin >> str;

• cin.get()

  • 표준 입력 버퍼에서 문자를 하나만 가져온다.

  • 공백, 개행을 포함한다.

  • 문자만 입력 받는다. Char

  • 사용 예 :

    char ch;
    ch = cin.get();

• cin.getline()

  • 종결 문자를 NULL로 바꾼다. 종결 문자 생략시 개행 문자로 간주.

  • 최대 입력 가능 문자 수 N보다 많은 문자를 입력한 경우 N-1개 만큼 받아들이고 N번째 문자는 NULL로 바꾼다.

  • 공백, 개행을 입력받는다.

  • 문자열만 입력 받는다. string, char*

  • cin.getline() 과 getline()는 다른 함수이다.

  • 사용 예 :

    char ch[10];
    cin.getline(ch, 10, '.');
    // 매개변수 : 저장 메모리 주소, 문자 수, 종결 문자 (default NULL)

• 출처: https://luyin.tistory.com/334 [Luyin:티스토리]

• 오답노트 : 백준 4949, 백준 11650

  • 백준 4949 균형잡힌 세상
    다른 사람들의 코드도 한번 보자. 더 나은 알고리즘을 궁리해보자.

  • 백준 11650 좌표 정렬하기
    std::pair의 개념, sort()의 사용법 (세 번째 매개변수 : 함수 포인터), Compare()함수,
    sort()를 사용하지 않고 본인이 구현한 정렬의 방법으로. O(logN)으로.

  • 백준 18870 좌표 압축
    <aldorithm>의 unique()와 lower_bound를 쓰지 않고, 자신이 구현하거나 다른 방식으로. 특히, 이진 탐색 공부.