하루 한줄 요약
다시 폭풍속으로...!
오늘 공부한 내용
- 스택 자료구조 2회차(수식 후위 표기)
- 백준(9012, 2493)
- CSAPP (캐시, 프로세서)
새로 배우게 된 내용
스택을 활용한 수식의 후위표기
수식의 표기법은 세가지로 나뉜다
- 전위 표기 : * + A B + C D
- 중위 표기 : (A + B) * (C + D)
- 후위 표기 : AB+C+*
이때 중위 표기를 후위 표기로 변경하는 과정에서 스택 자료구조가 요긴하게 쓰인다.
- 중위 표기 -> 후위표기 방법
- 피연산자는 그냥 쓰고, 연산자를 만나면 Stack에 Push
- 연산자를 만났을 경우, 스택이 비어있지 않다면 TOS에 있는 연산자와 우선순위를 비교한다
- TOS의 연산자가 우선순위가 더 높다면 이걸 POP 하여 연산자를 빼낸다
- 남은 연산자는 Stack에 PUSH
- 수식에 끝까지 왔다면 스택에 남아있는 원소를 모두 POP 한다
- 중위 표기 -> 후위표기, 중위 표기에 괄호가 있다면?
- 여는 괄호 "(" 는 Stack에 Push
- 닫는 괄호를 만난다면 여는 괄호를 만날때 까지 POP
이걸 코드로 바꾸면
def infix_to_postfix(expression):
# 우선순위 설정
precedence = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'(': 0 # 여는 괄호는 가장 낮은 우선순위로 설정
}
stack = []
result = []
for char in expression:
if char not in precedence and char != ')': # 피연산자라면 (연산자가 아니라면)
result.append(char)
elif char == '(': # 여는 괄호는 그냥 스택에 넣기
stack.append(char)
elif char == ')': # 닫는 괄호라면 여는 괄호까지 팝
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop() # 여는 괄호 '(' 제거
else: # 연산자일 때
while stack and precedence[stack[-1]] >= precedence[char]:
result.append(stack.pop())
stack.append(char) # 현재 연산자를 스택에 추가
# 스택에 남아있는 연산자를 결과로 추가
while stack:
result.append(stack.pop())
return ''.join(result) # 리스트를 문자열로 변환하여 반환
# 테스트 예제
expression = "A+B*C-(D/E)"
print(infix_to_postfix(expression)) # 결과: ABC*+DE/-
백준 - 9012
스택은 괄호 쌍을 찾는데 많이 쓰인다,
이 문제도 스택을 활용하여 올바른 문자열을 찾는 문제.
처음에 여는 괄호는 Push, 닫는 괄호는 Pop 이라고 단순히 생각하고 풀었는데
당연히 틀렸다.
값이 없는데 Pop을 해야할 수도 있다는 예외를 생각하지 못했다.
이를 보완하여 작성한 정답 코드
import sys
input = sys.stdin.readline
T = int(input().rstrip())
for i in range(T):
stack = []
str = list(input().rstrip())
is_VPS = True
for char in str:
if char == "(":
stack.append("(")
else:
if len(stack) == 0:
is_VPS = False
break
else:
stack.pop()
if len(stack) > 0:
is_VPS = False
print("YES" if is_VPS else "NO")백준 - 2493
- 시간 초과 난 풀이
import sys
input = sys.stdin.readline
N = int(input())
towers = list(map(int, input().split()))
answer = []
while towers:
cur_tower = towers.pop()
found = False
for i in range(len(towers) - 1 ,-1,-1):
if cur_tower < towers[i]:
answer.append(i + 1)
found = True
break
if not found:
answer.append(0)
print(*answer[::-1])
매번 현재 탑(cur_tower)를 기준으로 왼쪽의 모든 탑을 탐색하는 방식
O(N^2) 이 걸리며 N이 50만 이하기에 2억 5천만번의 연산을 수행하기에 시간 초과
- 개선된 풀이
이때 스택을 활용하여 탑의 높이 값을 스택에 저장해서,
O(N)의 속도로 확인 하는 것.
import sys
# 탑의 수
n = int(sys.stdin.readline())
# 탑의 높이
arr = [0] + list(map(int, sys.stdin.readline().split()))
# 결과 배열
result = [0] * (n+1) # 인덱스 1번을 첫번째 탑에 주기 위해 n + 1
# 스택 초기화 (높이, 위치)
stack = []
for i in range(1, n+1):
# Stack에 탑의 정보가 남아있다면
while stack:
# 현재 탐색하고 있는 탑의 높이가 Stack TOP의 높이보다 크다면
if (arr[i] > stack[-1][0]):
# Stack TOP 제거
stack.pop()
# 현재 탐색하고 있는 탑의 높이가 Stack TOP의 높이보다 작다면
else:
# 현재 탐색하고 있는 탑의 레이저를 수신 받을 수 있는 탑의 위치를 저장
result[i] = stack[-1][1]
break
# 현재 탑의 정보를 Stack에 삽입
stack.append((arr[i], i))
print(*result[1:])
CSAPP 1.5 ~ 1.7
- 캐시
메모리도, CPU도 레지스터의 모임,
결국 우리가 원하는 건 빠른 속도, 그 빠른 속도를 이루기 위해선 캐시를 활용한다.
캐시를 통해 CPU와 메인 메모리간의 병목을 막고,
자주 나오는 것(지역성)을 빠르게 뽑을 수 있는 캐시에다가 넣어놓는 것.
또한 큰 저장장치일 수록 바이트당 비용은 저렴하고, 속도는 느리다
작은 저장장치 일 수록 바이트당 비용은 비싸고, 속도는 빠르다
- OS
OS의 목표는 두가지.
- 응용 프로그램의 잘못된 하드웨어 사용 방지.
- 응용 프로그램이 저수준 하드웨어 장치를 쉽게 조작할 수 있도록 단순하고 균일한 메커니즘 제공.
이를 달성하기 위해 세가지로 추상화를 진행한다
- 프로세스
- 가상메모리
- 파일
프로세스
프로그램을 구성하는 단위,
다수의 프로세스는 동시에 실행가능하다(교차 수행의 형태)
이 교차 수행시 문맥교환을 통해 다중 작업을 수행한다.
이때 커널이란 개념이 등장하는데 이게 아직 불확실해서 좀 더 살펴볼 예정
쓰레드
이 쓰레드는 프로세스의 구성 요소
프로세스 간 데이터 공유보다 쓰레드 간 데이터 공유가 편하다
가상 메모리
프로세스당, 주어지는 가상 주소 공간이고
실제 메모리 주소가 위도/경도의 느낌이라면 가상메모리는 도로명 주소의 느낌
파일
연속된 바이트의 집합.
공부하다가 아쉬운 점
키워드는 주어지지만, 디테일한 가이드라인이 없어서
어디까지 어떻게 공부할지가 조금 희미...
그래도 일단 교재 보고 구글링해야지 머...
