ALGORITHM/백준67 [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. [BOJ/PYTHON] 1026. 보물 백준 문제 링크: https://www.acmicpc.net/problem/1026 문제 요약 길이가 N인 정수 배열 A와 B S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 최소로 만들기 위해 A의 수를 재배열 (A만) S의 최솟값을 출력 핵심 아이디어 A를 재배열해 B의 가장 큰 수와 A의 가장 작은 수가 곱해지게 하면 된다! B는 재배열하면 안 된다고 문제에 써져 있는데, 재배열된 후의 A 배열을 문제에서 요구하고 있지 않으니 그냥 B 배열도 원하는 대로 섞어도 된다. 따라서 B는 큰 수부터 정렬, A는 작은 수부터 정렬하고, 곱한 값을 차례대로 더하면 된다. 풀이 # silver4-1026. 보물 import sys input = sys.stdin.readline.. 2023. 5. 25. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음