[BOJ][DP] 1351. 무한 수열 (java)

✏️ 문제 https://www.acmicpc.net/problem/1351문제무한 수열 A는 다음과 같다.A0 = 1Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.입력첫째 줄에 3개의 정수 N, P, Q가 주어진다.출력첫째 줄에 AN을 출력한다. 🔢 알고리즘 #DP  🤯 풀이 방법 처음 제출한 코드는 ⬇️수열이라고 1부터 하나씩 계산하며 올라가면 메모리 초과가 난다. import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new ..

• format_list_bulleted Algorithm/BOJ
• · 2025. 2. 21.
• textsms

와일드카드(*)로 import하면 성능이 떨어지는가?

습관적으로 import java.util.*; 등등을 쓰다가 문득 궁금해졌다. GPT의 답변은 이렇다이때 주목할 부분은 "컴파일러가 최적화해서 포함되지 않거나 사용되지 않는다" 추가적인 조사를 더 해 보면컴파일 언어에서는 실행 전에 컴파일 과정이 필수이며, 그 과정에서 필요한 것만 거르기 때문에 컴파일 시간에는 영향을 미칠 수 있으나 컴파일 결과로 같은 실행 파일을 생성하므로 실제 실행 속도에는 영향을 미치지 않는다! 고 한다. 다만 와일드카드가 아닌 구체적인 명시를 권장하는 이유는 코드의 가독성과 명확성을 위해서이다  자바 클래스 import 관련 속도 문제(import java.util.*)자바에서 클래스를 가져올 때 와일드카드(*)를 써서 전체를 임포트하는 경우가 있습니다.(원인은 귀차니즘 ...b..

• format_list_bulleted TIL/etc
• · 2025. 2. 20.
• textsms

[BOJ][DP] 9251. LCS (java)

✏️ 문제문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 🔢 알고리즘 #DP  #LCS  🤯 풀이 방법 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest Common Subse..

• format_list_bulleted Algorithm/BOJ
• · 2025. 2. 19.
• textsms

[BOJ][DP] 1003. 피보나치 함수 (java / python)

✏️ 문제  🔢 알고리즘 #DP  #다이나믹프로그래밍  🤯 풀이 방법 문제에서 재귀 함수, 출력 어쩌고 했다고 그대로 풀면 당연히 시간 초과가 난다.0부터 테스트케이스를 보면,0의 경우: 0 출력 후 리턴 1의 경우: 1 출력 후 리턴 2의 경우: call f(0), f(0) 이므로 f(0)의 출력 수와 f(1)의 출력 수를 더하면 3의 경우: call f(1), f(2) -> (0, 1) + (1, 1) = 4의 경우: call f(2), f(3) -> (1, 1) + (1, 2) = 5의 경우: call f(3), f(4) -> (1, 2) + (2, 3) = 6의 경우: call f(4), f(5) -> (2, 3) + (3, 5) =  숫자의 나열이 익숙하다. 1, 1, 2, 3, 5, 8, ..

• format_list_bulleted Algorithm/BOJ
• · 2025. 2. 17.
• textsms

[BOJ][우선순위큐] 11286. 절댓값 힙 (java)

✏️ 문제문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.출력입력에서 0이 주어진 회수만큼 ..

• format_list_bulleted Algorithm/BOJ
• · 2025. 2. 14.
• textsms

[BOJ][Greedy] 11399. ATM (java/python)

✏️ 문제문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게..

• format_list_bulleted Algorithm/BOJ
• · 2025. 2. 11.
• textsms