problem solving/ps java7 [ps java] 재귀 -> DP 변환 예시 코드(BOJ 9184) https://www.acmicpc.net/problem/9184재귀를 DP로 바꾸는 문제이다 [실버2]재귀 호출만 생각하면 신이 난다! 아닌가요? 아래와 같은 재귀 호출 알고리즘 코드가 있다하지만 a b c 에 15 15 15 만 입력하더라도 실행하는 데에 너무 많은 시간이 걸린다따라서 우리는 아래의 코드를 DP로 변형해 볼 것이다import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); whi.. 2025. 1. 19. [ps java] 피보나치 수열 알고리즘(재귀, DP) 우리가 일반적으로 알고 있는 피보나치 수열에 대한 재귀 알고리즘은 다음과 같다import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); System.out.println(fibonacci(n)); br.close(); } private static int fibonacci(int n) { if (n == 0) {.. 2025. 1. 19. [ps java] BOJ 15663 N과 M (9) 해설 "백트래킹" 대표 시리즈인 N과 M 시리즈 9번 문제 [실버2]역시 문제 조건 N ※ 백트래킹은 재귀를 활용하므로 보통 시간복잡도가 O(N^N), O(N!) 꼴이다 풀이의 핵심은 중복을 피하는 것이며, 이에 대해 두 가지 풀이 방법이 있다1) HashSet 사용 풀이2) 중복 방지 로직 풀이 https://www.acmicpc.net/problem/15663문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건.. 2025. 1. 7. [ps java] BOJ 15650 N과 M (2) 해설 "백트래킹" 대표 시리즈인 N과 M 시리즈 [실버3]문제 조건 N ※ 백트래킹은 재귀를 활용하므로 보통 시간복잡도가 O(N^N), O(N!) 꼴이다 https://www.acmicpc.net/problem/15650문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 13 1예제 출.. 2025. 1. 6. [ps java] fast I/O 정확하게 알고 쓰기 JAVA 같은 엔터프라이즈 언어의 입출력은 타 언어에 비해서 상대적으로 느리며, 특히 System.out.println()을 여러 번 호출하면 성능에 큰 영향을 미친다. 따라서 우리는 익히 아는 BufferReader와 StringBuilder를 사용하는데, StringBuilder를 ps에서 명확하게 사용하는 방법을 알아보고자 한다. 먼저 다음의 코드를 살펴보자! 전형적인 큐의 웰노운 문제이다import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Deque;import java.util.StringTokenizer;pu.. 2025. 1. 4. [ps java] binarySearch() 정석 코드 2가지 버전 https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep2-%EC%82%AC%EC%A0%84dictionary 유일키 - 직접응용: 연" data-og-host="claremont.tistory.com" data-og-source-url="https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep2-%EC%82%AC%EC%A0%84dictionary" data-og-url="https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep2-%EC%82%AC%EC%A0%84dicti.. 2024. 11. 6. [ps java] PriorityQueue() 사용법 ps에서 우선순위 큐는 최단거리 알고리즘(다익스트라 알고리즘)에 많이 사용되며, 구현 문제에도 사용될 수 있다최댓값 혹은 최솟값 꺼내서 처리한 뒤 다시 넣고.. 이렇게 반복하는 종류의 문제들에서 잘 쓰인다 ㅇPriorityQueue(): 입력 요소에 우선순위를 부여e.g. 입력[3, 1, 5, 2, 4] -> 출력[1, 2, 3, 4, 5] 기본 설정이 최소 힙(min-heap)으로 되어있기 때문에 오름차순으로 출력된다import java.util.PriorityQueue;public class PriorityQueueExample { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); .. 2024. 10. 27. 이전 1 다음
