본문 바로가기

프로그래밍_백준

 (48)
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..
*Java) 2579번 계단 오르기 (dp) 이 문제의 핵심은 두 가지 경우의 수를 생각하는 것입니다. 바로 직전 계단을 밟지 않고 이전 계단과 현재 계단을 밟는 경우: (2칸) DP[i - 2]​ 바로 직전 계단을 밟고 현재 계단을 밟는 경우: (i-3에서 2칸을 올라오고 i-1에서 한 칸을 올라옴) DP[i - 3] + arr[i - 1]) + arr[i]​ DP[i-3]이 1칸+1칸으로 올라오는 경우가 있기 때문에 2칸을 올라간다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); // 계단의 개수 입력 int[] DP = new in..
Java) 1463번 1로 만들기 (dp) 이 문제는 dp를 사용하는 문제입니다. N부터 시작하여 1까지 내려가는 과정에서 숫자를 만드는데 필요한 횟수를 메모제이션 합니다. 1. 1을 빼는 경우를 계산 2. 2로 나누어 떨어지는 경우 1을 뺀 경우와 비교하여 더 작은 값을 찾음. 3. 으로 떨어지는 경우 1을 뺀 경우와 비교하여 더 작은 값을 찾음. 각각에서 +1을 하는 경우는 1을 뺀 경우, 2로 나눈 경우, 3으로 나눈 경우를 더해주는 것 입니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[n+..
Java) 백준 1003번 피보나치 함수 (DP) 피보나치 함수를 이용하여 0과 1의 사용빈도를 출력하는 문제입니다. 이 문제는 다이나믹 프로그래밍을 사용해야 합니다! 재귀 Top-Down Bottom-Up 1. 재귀 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.IOException; public class Main { static int count_0 = 0; static int count_1 = 0; public static void main(String[] args) throws IOException { BufferedReader br..
Java) 백준 1874 스택 수열 프로그램 로직 사용자로부터 수열의 크기(n)를 입력. 수열의 각 요소를 입력받아 배열(arr)에 저장. 배열의 각 요소에 대해 다음을 수행: 스택이 비어 있거나, 스택의 맨 위 요소가 현재 배열 요소보다 작으면, 스택에 새로운 값을 '푸시'(+ 연산). 스택의 맨 위 요소가 현재 배열 요소와 같으면, 스택에서 값을 '팝'(- 연산). 스택의 맨 위 요소가 현재 배열 요소보다 크면, 수열을 재구성할 수 없으므로 "NO"를 출력하고 프로그램을 종료. import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner..
*Java) 백준 1966번 프린터 큐 1966번 문제입니다. 프린터가 여러 문서를 어떤 순서로 출력하는지를 알아내는 문제입니다. 만약 중요도가 같은 문서가 여러 개 있다면, 입력된 순서대로 출력됩니다. 여기서 3번째 케이스를 계속 헷깔렸어요.. 이렇게 생각하면 편하더라구요! '1' 1 9 1 1 1 9 > 1 > 1 > 1 > '1' > 1 따라서 5입니다! 저는 입력한 순서라고 해서 9 > '1' > 1 > 1 > 1 > 1 이런 줄 알았어요.. PriorityQueue 원소를 중요도 순서로 정렬합니다. 단 PriorityQueue는 입력 순서를 보장하지 않습니다. 따라서 Queue를 사용하여 문서의 순서를 유지합니다. Document 클래스 생성 Document 클래스를 통해 우선 순위와 인덱스 값을 저장합니다. 이렇게 하면 찾으려는 인..
728x90
반응형

티스토리툴바