선형자료구조6 [BOJ/PYTHON] 19591. 독특한 계산기 백준 문제 링크: https://www.acmicpc.net/problem/19591 문제 요약 수식에서 맨 앞의 연산자, 또는 맨 뒤의 연산자 먼저 계산한다. 단, 음수의 부호는 연산자로 취급하지 않는다. 곱셈, 나눗셈을 덧셈, 뺄셈보다 더 먼저 계산한다. 연산자의 우선순위가 같다면 해당 연산자를 계산했을 때 결과가 큰 것부터 계산한다. 계산했을 때 결과 값 또한 같다면 앞에 것을 먼저 계산한다. 맨 앞 숫자만 음수가 들어올 수 있음 불필요한 0이 앞에 있을 수 있음. (001 + 0002 가능) (출력 시 제거해야) 나눗셈은 나누어지는 수가 양수면 나머지가 0 이상, 음수면 나머지가 0 이하로 처리가 되는 식으로 진행했을 때 나오는 몫을 계산 핵심 아이디어 주의해야 하는 조건만 잘 처리해주면 나머지는.. 2023. 6. 1. [BOJ/PYTHON] 3078. 좋은 친구 백준 문제 링크: https://www.acmicpc.net/problem/3078 문제 요약 좋은 친구가 몇 쌍 있는지 구하기 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아님 좋은 친구는 이름의 길이가 같아야 함 -> 좋은 친구는 등수의 차이가 K를 넘지 않으며 이름의 길이가 같음 핵심 아이디어 이름 길이에 해당하는 딕셔너리를 사용한다. 키값은 길이, value값은 그 길이인 이름 개수이다. 이름을 순서대로 보면서 일단 큐에 이름을 넣고 딕셔너리에 그 이름 길이에 해당하는 키값에 1을 더해주면 된다. 확인하는 사람의 범위가 k를 넘어가면 앞에서 하나씩 빼준다. 그러면 등수의 차이가 k 이내를 계속 유지하게 된다. 슬라이딩 윈도우를 덱으로 구현한 셈이다. 해당 딕셔너리에서 이름 길이가 같은.. 2023. 6. 1. [BOJ/PYTHON] 20301. 반전 요세푸스 백준 문제 링크: https://www.acmicpc.net/problem/20301 문제 요약 (N, K, M)-반전 요세프스 순열 구하기 요세푸스 순열: 원을 이뤄 앉아있는 사람 중 k번째 사람을 순서대로 제거. 반전: M명의 사람이 제거될 때마다 원 돌리는 방향 바꿈 핵심 아이디어 요세푸스 문제를 풀었으면 쉽게 풀 수 있다. 요세푸스 순열에서 반전되는 경우를 추가적으로 핸들링해주면 된다. 파이썬 덱에서는 양수로 rotate할 때는 rotate(k)를 해주면 되는데 음수로 해줄 땐 rotate(-(k-1))을 해줘야 한다. 사람 제거하면서 제거된 사람 수를 1씩 더해주고, m만큼 제거했으면 방향을 바꿔주면 된다. 풀이 # silver3-20301. 반전 요세푸스 import sys from colle.. 2023. 6. 1. [BOJ/PYTHON] 1158. 요세푸스 문제 백준 문제 링크: https://www.acmicpc.net/problem/1158 문제 요약 (N, K)-요세프스 순열 구하기 요세푸스 순열: 원을 이뤄 앉아있는 사람 중 k번째 사람을 순서대로 제거. 핵심 아이디어 문제에서 사람이 원을 이뤄 앉아있다는 내용을 읽고 바로 원형 큐를 생각하면 된다. k번째 사람을 순서대로 제거해야 하는데, rotate로 k번을 돌려줘 제거할 사람을 맨 앞에 오게 만들고, 맨 앞 사람을 pop해주면 된다. 풀이 # silver4-1158. 요세푸스 문제 import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) q = deque(range(1, n+1).. 2023. 6. 1. [BOJ/PYTHON] 1935. 후위 표기식2 백준 문제 링크: https://www.acmicpc.net/problem/1935 문제 요약 후위 표기식이 주어질 때, 계산 결과를 소수점 2번째까지 출력 핵심 아이디어 알파벳이 주어지는데, 알파벳을 ord를 사용해 숫자로 바꾸는 것이 필요하다. ord(x) - ord('A')를 할 경우 A가 오면 0이 된다. 알파벳이면 스택에 넣어주고, 연산자가 오면 스택에서 pop해주고 계산, 계산 결과를 다시 넣어주면 된다. 풀이 # silver3-1935. 후위 표기식2 import sys input = sys.stdin.readline n = int(input()) formula = list(input().rstrip()) nums = [int(input()) for _ in range(n)] stack = .. 2023. 6. 1. [BOJ/PYTHON] 9012. 괄호 백준 문제 링크: https://www.acmicpc.net/problem/9012 문제 요약 입력으로 주어진 괄호 문자열이 VPS인지 판단 올바른 괄호 문자열(Valid PS, VPS)은 괄호 짝 잘 지어진 문자열 핵심 아이디어 전형적인 스택 문제다. 괄호 모양을 보고 스택에 넣어주거나 빼면 된다. )가 왔을 때 스택에서 무조건 빼주는 게 아니라, 스택 맨 위가 ( 모양이면 빼주면 된다. 풀이 # silver4-9012. 괄호 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): stack = [] # 테스트 케이스마다 스택 초기화 ps = input().rstrip() # 각 줄 입력 for i in range(len(ps.. 2023. 6. 1. 이전 1 다음