본문 바로가기

프로그래밍_백준/Python

(11)
Python) 30804번 과일탕후루 (슬라이딩 윈도우) https://www.acmicpc.net/problem/308041. 문제 소개이번 포스팅에서는 백준의 과일 탕후루 문제(30804번)를 해결하면서 슬라이딩 윈도우라는 새로운 개념을 배웠던 경험을 기록해두려고 합니다. 문제는 과일을 스틱에 꽂았을 때, 두 종류의 과일만 남길 수 있도록 과일을 제거하고, 가장 긴 구간을 찾는 내용입니다.문제 요약과일 N개의 목록이 주어집니다.우리는 과일의 앞이나 뒤에서 하나씩 과일을 제거할 수 있습니다.이때, 두 가지 종류의 과일만 남도록 할 수 있는 가장 긴 구간을 구하는 것이 목표입니다.2. 슬라이딩 윈도우 개념 정리문제를 풀면서 처음 접한 개념이 슬라이딩 윈도우였는데, 이 방식은 주어진 리스트에서 특정 조건을 만족하는 연속된 구간을 찾아내는 방법이에요. 기본적으로 ..
Python) 백준 1463번: dp, 1로 만들기 https://www.acmicpc.net/problem/1463숫자 N이 주어졌을 때, 1로 만드는 최소 연산 횟수를 구하는 문제이다.1. 3으로 나누어떨어지면, 3으로 나누는 연산 2. 2로 나누어떨어지면, 2로 나누는 연산 3. 1을 빼는 연산이 문제는 Dynamic Programming(동적 계획법)을 사용하여 해결할 수 있다. import sysinput = sys.stdin.readlinedef make_one(n): dp = [0] * (n + 1) for i in range(2, n + 1): if i % 2 == 0: a = dp[i // 2] + 1 else: a = float('inf') ..
Pyton) 정렬 함수 사용 및 lambda numbers = [5, 2, 9, 1, 7]words = ["apple", "banana", "cherry", "date"]items = [(1, 'apple'), (2, 'banana'), (3, 'cherry')]#sorted() 함수sorted_numbers = sorted(numbers)sorted_numbers_desc=sorted(numbers, reverse=True)sorted_words = sorted(words, key=len)#list.sort()numbers.sort()numbers.sort(reverse=True)word.sort(key=len)# 튜플 리스트에서 두 번째 값을 기준으로 정렬sorted_items = sorted(items, key=lambda item: item..
Python) sort()함수 Sort 1. 기본적인 리스트 정렬 numbers = [4, 2, 7, 5, 1] numbers.sort() print(numbers) # 출력: [1, 2, 4, 5, 7] list.sort(reverse=True)를 사용하면 역순으로 정렬할 수 있다. numbers = [4, 2, 7, 5, 1] numbers.sort(reverse=True) print(numbers) # 출력: [7, 5, 4, 2, 1] 2. key를 사용한 정렬 words = ['apple', 'banana', 'cherry', 'grape', 'kiwi'] words.sort(key=len) print(words) # 출력: ['kiwi', 'apple', 'grape', 'banana', 'cherry'] 3. 2차원 배열..
Phthon) 1929번 소수 구하기 백준 1929문제는 소수를 M과 N사이의 소수를 출력하는 문제입니다. 소수 문제를 제한 시간 안에 효율적으로 풀기 위해서는 공식을 사용해야 합니다! 소수를 판별을 할 때 사용하는 공식은 제곱근을 이용한 방식입니다. 만약 36이라는 숫자가 있으면 제곱근을 통해 6을 구하고 이를 범위로 설정하여 검사하면 효율적으로 검사할 수 있습니다. M, N = map(int, input().split()) for i in range(M, N+1): if i == 1: continue prime = True for j in range(2, int(i**0.5) + 1): # 소수 확인을 위한 for 루프 범위 수정 if i % j == 0: prime = False # i가 j로 나누어 떨어지면 소수가 아님 break i..
Python) 10989 수 정렬하기 Counting Sort (계수 정렬) 이번 문제는 수를 정렬하는 문제입니다. 계수 정렬도 풀어야지 해결할 수 있습니다! (몰랐어요..ㅠㅠ) 계수 정렬이란? 데이터의 범위가 작고 정수일 경우 효율적인 정렬 알고리즘이며, 시간 복잡도는 O(n+k)입니다. (n은 입력 데이터의 수, k는 입력 데이터의 범위) 계수 정렬의 기본 원리는 입력 데이터의 각 정수 값을 계수하기 위해 배열을 사용하는 것입니다. 배열의 각 인덱스는 입력 정수 값에 대응하며, 배열의 값은 해당 정수가 데이터에 나타나는 회수를 나타냅니다. 제가 해결한 방법은 숫자 목록(N개의 정수 값)을 입력 받습니다. 크기가 100인 배열(arr)을 생성합니다. 배열의 크기는 입력 데이터의 최대 범위에 따라 조정될 수 있습니다. 입력 받은 숫자 목록에서 각 숫자를 읽고, 해당 숫자와 같은 ..
Python) 1181번 단어 정렬 (sort함수) 1. 단어을 사전 순으로 정렬한 다음에 2. 길이 순으로 정렬하면 => 길이 순으로 정렬한 후 사전 순으로 정리한 것 처럼 출력할 수 있습니다. 또한, set 함수를 이용해서 중복된 값을 합쳤고, sort에서 key를 이용하여 길이 순으로 정렬하였습니다. import sys input = sys.stdin.readline # 입력 속도를 높여주는 sys.stdin.readline을 input으로 사용합니다. n = int(input().strip()) # 입력받을 문자열의 개수를 저장합니다. a = [] # 문자열을 저장할 리스트를 초기화합니다. # 문자열을 입력받아 리스트에 추가합니다. for i in range(n): a.append(input().strip()) # 중복 제거 a = set(a) #..
Python) 9012번 괄호 문제 (stack) 괄호가 올바르게 균형을 이루었는지 확인하는 문제입니다. 스택을 사용한 방법, 사용하지 않은 방법 두 가지로 문제를 풀었습니다. 첫 번째 문자열의 개수를 입력받습니다. 각 문자열에 대해 입력을 받아 bracket_list에 저장합니다. 문자열 길이의 홀수 여부를 확인하여 짝수문자열인 경우에만 올바른 조합 검증을 수행합니다. 문자열 내부에서 여는 괄호와 닫는 괄호의 개수를 세어 올바른 조합 여부를 판정합니다 a = int(input()) # 테스트 케이스의 수를 입력받습니다. bracket_list = [] # 괄호 문자열을 저장할 리스트를 초기화합니다. count_open = 0 # 여는 괄호의 개수를 추적하기 위한 변수를 초기화합니다. count_close = 0 # 닫는 괄호의 개수를 추적하기 위한 변..

728x90
반응형