[알고리즘 스터디] 스택, 큐, 덱

🐣 알고리즘 스터디

이화여자대학교 SW학부 원스탑 튜터링에서 진행하는 코딩 테스트 대비 알고리즘 스터디 알튜비튜 튜터링을 듣고 수행 내용, 새롭게 알게 된 점, 어려웠던 점, BOJ 문제 노트, 자료/사이트, 느낀점 등을 기록합니다.

🍭 스택, 큐, 덱 (3월 11일)

🖤 수행 내용

• 스택, 큐, 덱 자료구조에 대한 개념을 배우고, 코드로 구현해본다.
• 자료구조 코드를 직접 작성하지 않아도 사용할 수 있는 스택, 큐, 덱 라이브러리를 이용하여 알고리즘 문제를 푼다.

🖤 새롭게 알게된 점

1. 이미 push 해버린 commit, 어떻게 되돌리지?

커밋 내역이 깔끔해야 한다는 강박증이 생겨버려서 구글링을 통해 이미 push 해버린 것을 어떻게 되돌릴 수 있을지 알아내었다...

• git revert/reset 명령어 사용. 그 중 내가 많이 사용한 것을 아래에 작성해보겠다.

  git reset --hard [commit ID]

• 이후 새로운 작업 후에 push가 안된다면

  git push --force

• commit ID는 git log를 치면 나오고, 입력한 commit ID의 커밋이 사라지는 것이 아니라, 입력한 commit ID 이후에 commit한 내역이 모두 사라진다.

• 주의할 점은 commit 내역이 사라질 뿐만 아니라 그때까지의 작업 또한 모두 사라진다.

• 협업시에는 conflict 문제로 reset을 잘 사용하지 않는다고 한다. 이 블로그에 자세한 내용이 설명되어 있다.

• 절대 함부로 사용하지 말 것... 이라고 하지만 엄청 사용했다

2. 스택, 큐, 덱에 배열 인덱스 접근이 가능할까?

원칙적으로는 STL stack, queue, deque에 인덱스 접근도 불가능하고, 중간에 위치한 자료에 대한 삽입/삭제 등의 연산도 불가능하다. only 앞이나 뒤에서만 가능하다. 즉 중간에 있는 원소에 대한 확인/변경 모두 불가능하다. 또한 vector처럼 초기 크기 할당이 불가능하다.

• 예외) 스택, 큐를 구현할 때 배열로 구현하면 가능하지만, STL에서는 불가능하다는 것!

❗중요 하지만 STL deque은 굉장히 특별하다!

• deque에서는 인덱스로 원소에 접근할 수 있다.
• deque에서는 초기 크기 할당도 가능하다.

임의의 인덱스 접근/변경과 초기 크기 할당이 가능하다는 점에서 vector와 비슷해보이지만 분명한 차이가 있다. 대표적으로 deque는 vector와 달리 크기가 할당되지 않아도 처음부터 특정 인덱스에 접근할 수 있다. 그 이유는 vector는 공간을 늘릴 때 배열 자체를 reallocation(재할당)하지만, deque은 일정 크기를 가지는 chunk(덩어리) 단위로 공간을 늘려주기 때문이다.

이에 대한 내용은 공식문서에 더 자세히 나와있다.

예시를 한번 보자.

• vector의 경우 오른쪽 코드의 vector<int> v(5)(5의 크기만큼 0으로 초기화)처럼 크기를 할당해주어야 임의의 원소에 접근할 수 있다.

그렇다면 deque은 어떨까?

• 둘 다 된다! 위에서 말했듯 deque은 chunk 단위로 공간을 가지고 있기 때문이다.

그렇다면 궁금증이 생길 수 있다. 그럼 chunk 단위니까 내가 할당한 크기 5 뒤에도 or 크기를 할당하지 않아도 공간이 할당되어 있을 수도 있겠네?

이를 실험하기 위해 이렇게 코드를 짜보자!

1. deque에 크기 10을 할당해준다.
2. 앞 5개는 사용자 입력을 받아서 값을 넣어준다.
3. 총 15개를 출력해본다.

👉 예상되는 결과는

1. 할당한 크기 10개 중 앞 5개는 사용자 입력값이 나오고,
2. 나머지 5개는 0이 나올 것이다.
3. 그리고 크기를 할당하지 않은 부분인 나머지 5개도 0이 나오겠지..?

예상이 맞을지 확인해보자!

• 역시나 1, 2번 예상대로 사용자 입력 부분(결과 첫 번째 줄)은 제대로 나오고, 크기를 할당한 나머지 부분(결과 두 번째 줄)은 0으로 출력된다.
• 하지만 3번 예상이 틀렸다! 크기를 할당하지 않은 나머지 부분(결과 세 번째 줄)은 이상한 결과가 출력된다.

👉 chunk 단위로 할당할 때 항상 0으로 할당되지는 않는다는 것을 알 수 있다!!

3. Pull Request를 닫기 전에 Merge부터 하자!

아무 생각없이 merge 안하고 냅다 PR 닫았다가 깜짝 놀랐다 이게 닫아버리면 나중에 merge를 못하더라구요........... 다행히 다시 들어가보니 Reopen Pull Request가 있어서 눌러서 다시 열었다 휴우

4. Pull Request를 하는 방법도 여러가지이다..

깃허브는 왜 파도파도 끝이 없는가.... PR하는 방법조차 다양했다.
깃허브 만든 사람은 정말 천재가 아닐까 자세한 것은 이 블로그 참고!
나는 블로그에서 추천하는 squash and merge 방식을 많이 사용할 것 같다. 아래는 squash and merge를 위한 코드이다. 깔끔한 커밋 메시지에 목숨 거는 살암..바로 나

$ git checkout main
$ git merge --squash <main에 merge할 브랜치명>
$ git commit -m "<커밋 메세지>"

5. break문의 탈출 범위

break문은 for, switch, while, do while과 같은 가장 가까운 반복문 1단계를 탈출한다. if문을 탈출하는게 아니라는 것 주의!

6. 스택, 큐, 덱에서 원소를 삭제/탐색할 때는 반드시 empty 체크를 해주자!

없는 원소를 삭제(pop)하거나 탐색(top, front, back 등)하려고 하면 런타임 에러가 나므로 스택, 큐, 덱에서 삭제/탐색할 때는 항상 empty 체크를 해주자!

7. branch명을 쉽게 변경할 수 있다

바꾸려는 branch를 그대로 두고 이름만 바꾸는 것은 불가능하지만, 해당 branch의 commit 내역까지 포함하여 완전히 복사해서 새로운 branch에 붙여넣는 것은 가능하다! 자세한 것은 이 블로그 참고! 해당 코드를 아래에 작성하겠다.

$ git branch -m <변경 전 브랜치명> <새로운 브랜치명> //이름 변경하기
$ git push --set-upstream origin <새로운 브랜치명> //깃헙에 새로운 브랜치 업로드
$ git push origin :<변경 전 브랜치명> //이전 브랜치 제거

🖤 BOJ 문제 노트

#2108 통계학

• accumulate 함수 : 합계를 구하는데 많이 사용한다. 링크 참고

• floor 함수 : 소수점 아래를 무조건 무시한다. 즉, 버림해주는 함수이다. cmath 헤더에 있다.
  floor를 이용한 반올림해주는 코드 (소수점 첫째자리에서)
  👉 floor(반올림하고자 하는 숫자 + 0.5)
  👉 링크 참고

• round 함수 : 반올림 함수이다. cmath 헤더에 있다.
  ❗주의 다만, -0.33과 같이 반올림하여 -0이 되는 수도 존재하는데, 대부분의 문제에서 -0을 0으로 취급하라는 조건이 주어지기 때문에 조건문을 통해 -0의 경우를 걸러주어야 한다.
  해당 코드

#1213 펠린드롬 만들기

• 문자 자체를 수 연산하면 아스키코드로 바뀌어서 연산되며, 정수 자료형과 연산시 자동으로 정수 자료형으로 형 변환된다.
  해당 코드

• 문자열 s에 AB가 저장되어 있다고 할 때, s+"CDE"와 같이 단순히 + 연산자를 이용하여 뒤에 문자열을 써주면, 문자열의 뒤에 그대로 붙는다. 즉 ABCDE가 되는 것이다.
  해당 코드

#18115 카드 놓기

• vector는 선언시 크기를 할당할 때 변수인 크기도 가능하다!
  배열에서는 절대 불가능일텐데 vector의 경우에 처음에 변수 크기 할당이 가능해서 너무너무 좋았다.
  예를 들어, 아래와 같은 경우가 된다는 것!!

	int N;
	cin >> N;
	vector<int> A(N); //이렇게!!

• 사용자에게 입력받은 값을 vector에 넣을 때, 거꾸로 넣어주는 방법이 있다.
  vector A의 크기가 N이라고 했을 때, vector<int> A(N);으로 우선 N 크기만큼을 할당해주어야 한다. 그 다음 거꾸로 넣어주면 되는데, 2가지 방법이 있다.

  1. i를 0부터 N-1까지 for문 돌리기 A[N-1-i] 에 참조
  2. i를 N-1부터 0까지 for문 돌리기 A[i]에 참조

  vector가 가변 크기 배열임에도 반드시 크기 할당을 먼저 해주어야 하는 이유는 A[i]와 같이 특정 인덱스에 접근해야 하기 때문이다.
  vector <int> A; 선언 시에는 크기가 하나도 없는 주소 값만 할당 받은 벡터가 생성된다. 이때, A는 현재 크기가 없으니 할당 받은 메모리 영역이 하나도 없는 것이다. 따라서 존재하지 않는 A[i]라는 메모리에 접근하려 해서 오류가 나는 것!
  PR 링크 참고
  해당 코드

#4949 균형잡힌 세상

• 공백 포함 문자열 string을 입력받을 때, getline(cin, <문자열 이름>)을 사용해주어야 한다.
  해당 코드

• switch문을 작성할 때 여러 개의 case가 같은 결과를 내면,
  case <조건1> : case <조건2> :와 같이 한꺼번에 작성해줄 수 있다.
  해당 코드

🖤 느낀 점

자료구조에서만 배우던 스택, 큐, 덱을 직접 알고리즘 문제에 구현해보니 재밌다 히히

새롭게 알게 된 점 중에서 2번은 두고두고 보면 좋을 것 같아서 그 부분만 떼어내서 따로 글에 작성하려고 한다! 👉 여기

그리고 내가 모르고 있던 개념이 굉장히 많은 것 같은데... 역시 이론 공부를 제대로 해놓는게 중요한 것 같다! 공식문서가 최고의 참고서가 될 수 있으니 무작정 구글링 하지말고 힘들더라도 공식문서부터 읽어보는 습관을 들이자😋