[TIL] 2주차_Day2: 자료구조/알고리즘 풀기(2)

💡Today I Learned

• 자료구조/알고리즘에 대한 두 번째 이론 및 실습 강의를 진행했습니다.
• 연결 리스트, 양방향 연결 리스트, 스택 자료구조의 개념
• 연결 리스트, 양방향 연결 리스트의 삽입/삭제 멤버 메소드로 구현
• 스택을 활용한 후위 표기법 변환, 계산 알고리즘 구현

 

---

1. 추상적 자료 구조

- 내부 구현을 숨겨두고 데이터+연산은 외부에서 사용 가능

 

2. 연결 리스트 (Linked List, LL)

- Node들이 연결됨

 

- Node(구조체) 속성:

1. data(문자열, 레코드, 또다른 연결 리스트 etc..)
2. link / next (다음 노드 가리킴)

 

- 리스트 속성:

1. head: 연결 리스트의 맨 앞 노드를 가리키는 포인터
2. tail: 연결 리스트의 맨 끝 노드를 가리키는 포인터
3. num_of_nodes: 연결 리스트 안에 노드의 개수

 

- 가능한 연산:

1. k번째 원소 참조: 실질적 노드는 1-based indexing (0번째 → dummy node용도)
2. 리스트 순회(방문)
3. 길이 계산
4. 원소 삽입/삭제: 삽입/삭제가 유연한 것이 LL의 가장 큰 장점
5. 두 리스트 병합

 

- (↔배열) 특징:

1. 노드들이 메모리 내 임의의 위치에 저장
2. 특정 원소 지칭 시 O(N)의 시간 복잡도를 가짐

 

3. 연결 리스트의 노드 삽입/삭제

- 삽입: (pos, newNode) → pos가 가리키는 위치 or pos가 가리키는 위치 뒤에 newNode를 삽입

1. 맨 앞/끝에 삽입: O(1) → head, tail 포인터 이용
2. 중간에 삽입: O(N) → 해당 pos까지 순차적으로 방문해야 하므로

 

- 삭제: (pos) → pos가 가리키는 위치 or pos가 가리키는 위치 뒤의 Node를 삭제, 삭제된 Node는 return

1. 맨 앞 삭제: O(1) → head 포인터 이용
2. 중간~끝 삭제: O(N) → 해당 pos까지 순차적으로 방문, 이 때 tail의 정보로 tail 앞의 노드를 알 수 없기 때문

 

- 주의할 것:

1. 리스트에 남은 마지막 한 개의 노드를 삭제하는 경우
2. 노드 삽입/삭제 후 tail과 head의 재조정이 필요한지 확인

 

4 .양방향 연결 리스트 (Doubly Linked List, Doubly LL)

- 앞으로도(다음 Node) 뒤로도(이전 Node) 진행 가능

- 연결 리스트에서 previous Node를 가리키는 ‘prev’ 포인터가 추가

- 처음과 끝에 모두 dummy node (head, tail) 추가

 

- getAt()의 개선: 앞/뒤 양 방향으로 이동 가능하므로→ 찾고자하는 pos가 head에 가까우면(=절반보다 앞) head에서부터 뒤로 이동하며 찾기

    → 찾고자하는 pos가 tail에 가까우면(=절반보다 뒤) tail에서부터 앞으로 이동하며 찾기

 

5. 스택

- LIFO(Last In First Out)

ex) 수식의 괄호 유효성 검사 → 괄호 열기 = push, 닫기 = pop → stack이 비어있으면 올바른 수식

 

6. 스택을 이용한 수식의 중위 표기법 → 후위 표기법 변환

- 중위 표기법 (infix notation): 연산자가 피연산자의 사이에 위치

- 후위 표기법 (postfix notation): 연산자가 피연산자의 뒤에 위치

 

- 변환 과정:

• 연산자 = push, 피연산자 = print
• push 전, 아직 행하지 않은(stack에 남아있는) 연산자들이 있다면 우선순위 비교
• pop: 현재 연산자보다 top이 더 높거나 같음 → top을 pop
• push: top보다 현재 연산자가 더 높음 → 현재 연산자를 push

 

- 주의할 것:

1. 괄호의 처리: 여는 괄호 = push, 닫는 괄호 = 여는 괄호 나올 때까지 연산자 pop
2. 여는 괄호의 우선순위는 가장 낮게 설정 → 닫는 괄호 나오기 전까지 여는 괄호를 pop하지 않기 위함

 

7. 스택을 이용한 후위 표기법의 수식 계산

- 피연산자 = push, 연산자 = stack에서 두 개의 피연산자 pop → 연산 수행 후 결과를 push

- 주의할 것:

1. /, - 연산 시 피연산자의 연산 순서에 유의하기!

 

 

---

📒 Furthermore

• 10강 실습 (선택강의)