코테 스터디 2주차 [스택/큐]

코테 스터디에서 진행하는 책, 출처: yes24

강의 링크(인프런)

(강의 내용 정리에 사용되는 자료의 출처는 저자님의 강의입니다. 출처 - 코딩 테스트 합격자 되기 [박경록])

(자료를 참고해서 제가 시각적으로 더 보기 편하게 편집한 사진들도 있습니다.)

 

10월 13일까지는 정리하고 카페에 올렸어야 했는데, 많이 늦어버렸습니다... 면목이 없네요 ㅠ

늦게 올리는 만큼 제대로 이해해서 정리해 보겠습니다!

 

(제대로 이해하고 넘어가기 and 정리도 이쁘게 하려니까 강의 시간에 3배 정도의 시간이 소요되네요....)

(유튜브 강의를 캡처해서 canva로 옮긴 뒤, 업스케일을 해서 여기에 붙여 넣는 방식으로 하고 있습니다)

 

▶ 강의 목차

• 스택
  • 스택의 개념
  • 스택의 ADT
  • 스택의 사용 예시
• 큐
  • 큐의 개념
  • 큐의 ADT
  • 큐의 사용 예시

 

▶ 강의 내용 정리

• 스택의 개념
  • LIFO(Last In First Out), FILO(First In last Out)이라고도 한다. 의미는 같음!
  • 가장 최근에 들어간 원소가 가장 먼저 나오는 자료 구조!
  • 마지막에 들어간 게 처음 나온다!
  • 먼저 들어간 게 나중에 나온다!

• 코딩테스트 → 문제를 풀어야 한다
  • 문제가 나온다.
  • 특정 문제에서 스택을 필요로 하는 경우 스택을 선택할 수 있어야 함!
  • 즉, 이 문제가 스택 문제인지 알아야 함
  • (1) 가장 최근에 들어온 원소를 알 수 있다!
  • (2) 가장 최근에 들어온 원소순으로 나온다!

• ADT란?
  • Abstract Data Type. 추상 데이터 타입의 약어
  • 세부사항을 숨기고 사용자에게 필요한 기능만 명시

 

 

.

아래 설명 참고!

• 전화번호부 예시!
  • 전화번호부를 제공할 건데, 전화번호부가 어떻게 구현되어 있는지는 중요하지 않음!
  • 사용자는 전화번호부 라이브러리만 알면 된다~
  • put 메서드 쓰면 연락처 저장
  • get 쓰면 연락처 가져오기
  • remove 하면 연락처 삭제
  • contains 하면 특정 연락처의 저장 유무 알 수 있음
  • size 하면 연락처가 몇 개 저장되어 있는지 알 수 있음
  • 사용자는 이런 것만 알면 된다~
  • 상태의 경우 ADT에서는 map<string,int> data; 이렇게 쓰지 않음
    • DataStorage data:
    • int maxSize = 0; 정도로만 ADT를 나타낸다

 

• 스택의 ADT
  • 중요! 프로그래밍 언어마다 조금씩 구현이 다름 
  • 코드 부분은  C++이라서 생략!
  • 나는 파이썬 편 책이 있어서 책을 보며 이해했다.
    • (그런데 책이 무려 711페이지까지 있다... 대학 복수전공 때 수강한 열역학 원서보다 두꺼운 느낌)
    • (이걸 1 회독만 해도 실력이 엄청 늘 것 같다. 얼른 다 하고 싶은데 ADsP와 원서접수가 발목을 ㅠㅠ)

이렇게 구현 되는 것 같다

 

• 스택의 사용 예시(함수 호출)
  • 함수가 호출되는 구조는 스택과 유사함!
  • 함수에서 사용하는 변수 같은 게 메모리에 쌓임
  • 쌓이는 메모리 동작이 스택 동작과 유사함
  • main 함수부터 시작
  • A라는 함수를 호출했을 때 아직 main함수가 끝나지 않은 채로 A함수가 호출
  • A함수 실행할 때 안에 B함수가 있으니 호출
  • 그러면 아래 사진의 (3) 형태처럼 되어있는 상태임!
  • 그리고 출력했으니 B함수가 끝나면 B함수 스택에서 뺌
  • A함수도 끝났으니 A함수도 스택에서 뺌
  • 다시 main 가서 끝남. 스택에서 main도 빠이빠이
• 함수 호출 동작 자체가 스택을 활용한 것.
• 키워드를 기억할 것!!

 

• 스택의 사용 예시(이전 페이지로 가기)
  • 위 함수 호출과정처럼 직관적으로 이해할 수 있음!
  • 여기까지는 이해하는데 문제없음

 

• 스택의 사용 예시(괄호 짝 맞추기)
  • 이건 조금 어려움. 실제 문제로 나올 수 있음!
  • 물론 사람은 직관적으로 봐도 알 수 있음(짝이 맞는지 맞지 않는지)
  • 하지만 개발자에게 필요한 덕목 중 하나가.....?(아마 과정을 세세하게 생각해라는 말씀 같음)
  • 직관이라는 것도 생각이 빠르게 지나가지 이 문제를 분석하는 과정이 분명히 있음
  • 세세하게 과정으로 나타내는 연습을 해야 문제를 풀 수 있음
  • 규칙을 찾아서 큰 문자열이 들어와도 문제를 해결할 수 있어야 함!

 

생각을 해보자! 설명은 아래 참고

 

근데 O(N)까지 어떻게 끌고와요....?

 

설명은 아래 참고!

 

* 모든 문자열에 대해 반복한다

아래의 과정을 진행한다면, 닫힌괄호 열린 괄호를 바로 확인할 수 있으니

시간복잡도가 O(N)이 된다~!

스택 문제는 이렇게 풀어야 함!

(구현 부분 코드는 생략. 하지만 꿀팁은 적어둠)

메인함수 부분에 모든 로직을 다 때려 넣는 사람 = 초보자(바로 나)

그렇게 하면 디버깅이 어렵다. 비효율적이고 나중에 코드 보기도 힘들다.

복잡하거나 로직 부분은 따로 빼주는 게 좋음!

 

---

 

• 큐의 개념
  • FIFO(First In First Out), 가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조
  • LILO(Last In Last Out) 임

• 큐의 ADT
  • 큐에는 2가지 상태 있음. front, rear.
  • int front 상태의 경우, 가장 먼저 푸시된 원소의 위치로 아는 게 더 편함
  • (코드 부분은 생략하겠습니다)

 

 

• 큐의 사용 예시(줄 서기)

 

한 명씩 줄을 서는 모습

(rear는 가장 최근에 들어온 원소의 위치이고)

(front는 가장 먼저 들어온 원소의 위치입니다!)

 

처음 A가 줄 섰으므로 front는 A로 유지.

rear는 가장 최근 들어온 사람으로 계속 변경됨!

 

그러면 줄은 이렇게 섰는데, 영화관에 들어가는 건 어떻게 할까요??

pop()을 하면 front 위치에 있는 원소가 큐에서 삭제됩니다.

대기자가 한 명씩 영화관에 들어가는 모습

front 위치에의 원소들이 나가는 걸 볼 수 있습니다.

 

먼저 들어온 인원부터 들어가니까 A부터 순서대로 들어가서 front는 계속 변경되고

rear는 E로 변경되지 않는 걸 볼 수 있습니다!

(front는 계속해서 남아 있는 원소중 가장 먼저 삽입한 원소의 위치를 가리킵니다.)

 

 

• 큐의 사용 예시(요세푸스 문제)
  1. N명의 사람들이 원형으로 둘러앉고, 각 사람들 번호를 1~N로 매김
  2. 시작 위치부터 K번째 사람 제거
  3. 제거한 위치부터 다시 K번째 사람 제거
  4. (3) 과정을 한 명이 남을 때까지 반복

업스케일해도 화질이 아쉽네요 ㅠ

크게 어려움 없는 직관적인 내용인데 코드로 구현해라고 한다면 고민이 필요할 것 같습니다.

큐를 이용해라고 한다면 바로 못할 것 같습니다 ㅠ

 

• 요세푸스 문제 : 배열로 푼다면?

[배열로 풀 때 문제점]

괴롭히고 싶을 때 이걸 배열로 풀어봐라고 하면 된다...(?) 상당히 까다롭기 때문

1. 제거의 방향에 바뀜

2. 제거 시 제거한 뒤의 원소가 모두 이동해야 함

시간복잡도 O(N^2)이 된다. (N개의 원소에서 N번 땡겨야 할 수 있으므로)

 

• why? 왜 이렇게까지 꼬일까?
  • 문제 자체는 원형인데, 원형을 가정하고 문제를 풀어야 하는데 배열은 리니어함.
  • 리니어 한데 회전하는 걸 표현하려고 하니까 어려운 것

 

큐를 사용한다면 이 원형을 잘 구현할 수 있음!!! (대박사건)

어떻게 하는지 알아보도록 하자

N = 5, K = 2

1 2 3 4 5 넣음

k번째 원소 제거

k-1 번째까지는 팝&푸시로 뒤로 뺌, k번째 제거

팝&푸시를 통해서 원처럼 돌아가게끔 구현한다~

 

큐로 풀면 

1. 제거 동작이 푸시/팝으로 구현되므로 방향고려 x

2. 제거 후에도 이후 원소 이동 필요 없음

시간 복잡도 O(N*K) → why? : 매번 k-1개를 팝&푸시하고 있으니까~

N^2보다는 훨씬 적음. 물론 k가 많아지면 비슷할 수 있지만 구현 난이도가 많이 낮아짐.

(코드 구현 부분은 생략)

 

 

 

---

 

 

▶ 강의 후기

• 코테를 찍먹 수준으로 풀면서 머리로는 이해가 갔지만 이게 무슨 원리로 구현해야하는지 몰랐던 문제들이 있었다
• 근데 스택/큐 강의를 수강하면서 이해한 결과 이 개념들을 몰라서 그랬었구나 싶은 ㅠ
  • ex) O(N^2)인데도 그냥 로직은 맞는거 아님? 이러고 제출했다가 틀리고 띠용? 한 문제들
• 강의는 C++ 기준으로 진행되어서, 파이썬 편 책을 참고해서 이와 관련된 문제를 풀어봐야 장기기억으로 남을 것 같다.
  
  • 물론 그런 문제들을 풀어야 경험치가 쌓이니까. 강의 하나만 들었다고해서 머리에 영구적으로 저장되진 않음!
• 생각보다 엄청 어려운 내용들일것이라 생각하고 겁먹었었는데 다행히 그렇지는 않았다.
  • 예시들로 설명을 잘 해주셔서 이해하는데 도움이 된 것 같음

 

▶ 궁금한 점

• 딱히 없는데 이게 내가 완벽하게 이해해서 없다기 보다는 현재 내 지식이 얕아서 그런 것 같다.
• 아마 파이썬 코테 문제들을 풀면서 어? 요세푸스 문제는 이렇게 풀었는데, 이건 유사한 문제같은데 어떻게 구현하지?
  • 아마 의사코드까지는 작성해도, 그걸 코드로 구현하면서 느끼는 벽이 있을 것 같다.
  • 아직 파이썬 문법도 완벽하게 숙지한 것이 아니기 때문