algorithm28 [nodejs] 백준 1057번 https://www.acmicpc.net/problem/1057 안녕하세요오늘 풀 문제는 백준 1057번, 실버4입니다. c/c++로 계속 코테를 준비해오다가 최근 python을 거치고 nodejs로 왔습니다 .. ㅎㅎ 🔽 입력 조건- 첫째 줄에 차례대로 N A B 를 입력받음.- N은 참가자의 수 (2보다 크거나 같고, 100,000보다 작거나 같은 자연수)- A는 김지민의 번호, B는 임한수의 번호이다.- A, B는 N보다 작거나 같은 자연수, 서로 다르다. 🔽 출력 조건- 첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. - 만약 서로 대결하지 않을 때는 -1을 출력한다. ( 🔽 입출력입출력부터 까다롭더라구요우선 입출력 부터 확인해보겠습니다.const fs = .. 2025. 5. 9. [Python] input, sys :: 입력값을 받는 두가지 방법 최근에 코테 언어를 파이썬으로 변경하면서 입출력 방식부터 다시 공부중에 있다. 이때 파이썬에서는 입력받는 방식이 input, sys 두가지로 나뉘는데 오늘은 이 둘의 차이를 정리하고자 한다. 코딩 테스트에서는 문제 조건에 따라 여러 가지 입력 방식이 필요하다.입력 크기, 공백 여부, 여러 줄 입력 여부 등을 고려하여 적절한 방법을 선택해야 한다. 파이썬의 입력 방식에 관하여 아래와 같이 정리했다. ✅ 1. 기본적인 input() 사용한 줄 입력을 받을 때 사용한다.n = int(input()) # 정수 입력 s = input() # 문자열 입력 예제입력: 10 hello 출력: 10 hello 📌 사용 상황:입력이 작을 때한 줄씩 입력받을 때 ✅ 2. 여러 개의 정수 입력 (split() 사용)공백.. 2025. 1. 28. [C/C++] 백준 9252번 https://www.acmicpc.net/problem/9252 안녕하세요오늘 풀어볼 문제는 백준 9252번, 골드 4번 문제입니다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제로 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 프로그램을 구한다. 조건첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 아이디어DP 배열 정의:dp[i][j]: A[1…i]A[1 \ldots i]A[1…i]와 B[1…j]B[1 \ldots j]B[1…j]의 LCS 길이.점화식:A[i]==B[j]일 경우:dp[i][j]=dp[i−1][j−1]+1A[i]!=B[j]일 경우dp[i][j.. 2025. 1. 12. [C/C++] 백준 14002번 https://www.acmicpc.net/problem/14002안녕하신지오늘은 백준 14002번, 골드4번 문제를 풀고자한다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 구해보자.어제와 엊그제 비슷한 유형의 문제를 풀었는데 두 문제의 경우, 가장 긴 증가하는 부분 수열의 길이와 합을 구하는 문제였다면, 이번에는 길이와 그 수열을 구하는 문제이다. 조건첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 아이디어추적 배열 사용:prev[i]: i번째 원소의 이전 원소가 배열의 몇 번째 원소인지 저장.prev 배열을 통해 가장 긴 증가하는 부분 수열을 역추적하여 수열을 복원... 2025. 1. 11. [C/C++] 백준 11055번 https://www.acmicpc.net/problem/11055 오늘 풀어볼 문제는 백준 11055번, 실버2 문제이다.수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 만들어보자. 조건첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다. 아이디어점화식dp[i]: i번째 수를 마지막으로 포함하는 가장 긴 증가하는 부분 수열의 길이.점화식dp[i]=max(dp[i], dp[j]+arr[i])초기값dp[i]=arr[i]결과dp 배열의 최댓값이 정답 코드#include #include.. 2025. 1. 10. [C/C++] 백준 11053번 https://www.acmicpc.net/problem/11053 오늘은 백준 11053번, 실버2 문제를 풀어보려한다.수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 구현해보자. 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 DP를 사용해서 해결할 수 있다. 조건배열에서 부분 수열 중, 항목이 증가하는 수열의 최대 길이를 찾는다.점화식 정의dp[i]: i번째 수를 마지막으로 포함하는 가장 긴 증가하는 부분 수열의 길이.점화식:dp[i]=max(dp[j]+1)(0≤jiandarr[j]arr[i]) j는 i 이전의 인덱스 중 arr[j]를 만족하는 값만 고려.dp[i]는 dp[j]+1의 최댓값.초기값dp[i]=1: 각 원소는 스.. 2025. 1. 9. [C/C++] 백준 1912번 https://www.acmicpc.net/problem/1912 굿모닝.오늘 풀어볼 문제는 백준 1912번, 실버2 문제이다. n개의 정수로 이루어진 임의의 수열이 주어질 때, 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 프로그램을 만든다. 조건첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 아이디어dp[i]: i번째 수를 포함하는 연속된 부분합의 최댓값.dp[1]=num[1]: 첫 번째 수는 그대로 선택.점화식dp[i]=max(dp[i−1]+num[i],num[i]) 코드#include #include #include us.. 2025. 1. 8. [C/C++] 백준 2156번 https://www.acmicpc.net/problem/2156 안녕하신지..오늘 풀어볼 문제는 백준 2156번, 실버1 문제이다. 두가지 조건을 만족하여 최대한 많은 양의 포도주를 먹는 프로그램을 만들어보자. 조건포도주는 최대 3잔까지 연속해서 마실 수 없다.이전 두 잔을 마셨다면, 현재 잔은 마실 수 없다. 점화식dp[i] : i번째 잔까지 마셨을 때의 최대 포도주 양.dp[i]=max(dp[i−1], dp[i−2]+wine[i], dp[i−3]+wine[i−1]+wine[i]) :dp[i−1] : 현재 잔을 마시지 않음.dp[i−2]+wine[i]: 한 잔 건너뛰고 현재 잔을 마심.dp[i−3]+wine[i−1]+wine[i]: 이전 잔과 현재 잔을 마심. 초기값 설정dp[1]=wine[1]d.. 2025. 1. 7. [C/C++] 백준 1003번 https://www.acmicpc.net/problem/1003 오늘 풀어볼 문제는 백준 1003번 문제로 실버3 문제이다.제목부터 친절하게 피보나치 함수 문제라고 한다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하면된다. 조건N은 40보다 작거나 같은 자연수 또는 0이다. 아이디어피보나치 함수의 성질을 가질때, 0과 1이 출력되는 횟수를 구하는 문제이다.0과 1의 출력 횟수를 각각 구해야하므로 각각의 dp0, dp1의 벡터를 만들어서 기록해두었다.점화식피보나치 수열의 형식과 동일한 점화식이 만들어진다.dp[n] = dp[n-1]+dp[n-2] 코드#include #include using namespace std;int mai.. 2025. 1. 6. [C/C++] 백준 1463번 https://www.acmicpc.net/problem/1463 오늘 풀어볼 문제는 백준의 1463번 문제로 실버3 이다.정수 N이 주어졌을 때, 세 개의 연산을 적절히 사용해서 1을 만드는 프로그램을 만들어보자. 조건N은 1보다 크거나 같고, 10^6보다 작거나 같은 정수이다.연산을 하는 횟수의 최솟값을 출력한다.아이디어앞서 계산한 3가지 연산과 비교하여 가장 작은 것에 +1을 하여 구하는 방식으로 피보나치와 유사하다.초기값 설정N에 대한 연산 횟수의 최솟값을 dp(N)이라 하면N=1에 대한 dp(1)=0N=2인 값을 dp(2)=1N=3에 대한 dp(3)=1점화식따라서 dp(N)=min(dp(N/3),dp(N/2),dp(N-1))+1의 점화식을 갖게 된다.주의 ! 이때 N/3, N/2의 경우 각 나.. 2025. 1. 5. 이전 1 2 3 다음
