프로그래밍 및 개발 공부하기

🔷 백준 11053번 – 가장 긴 증가하는 부분 수열 (C++) 문제설명 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence)의 길이를 구하는 문제입니다. 부분 수열이란 원소를 연속적이지 않게 선택해도 되지만, 순서는 반드시 유지해야 합니다. 증가하는 부분 수열이란 앞에 있는 원소보다 뒤의 원소가 더 큰 경우만 연결되는 수열을 말합니다. 테스트케이스 입력 610 20 10 30 20 50 출력 4 문제 구체적 설명 (예시 기반) 입력 수열: 10 20 10 30 20 50 가능한 증가 부분 수열 예: 10..

🔷 포도주 시식 (백준 2156번) ✅ 문제 설명 포도주 시식회에 온 효주는 테이블 위에 일렬로 놓여있는 포도주 잔 중에서 포도주를 마시려고 합니다. 각 포도주 잔에는 일정한 양의 포도주가 들어있으며, 다음 두 가지 규칙이 있습니다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하며, 마신 후에는 다시 원래 위치에 놓아야 합니다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없습니다. 효주는 가능한 한 많은 양의 포도주를 마시고자 합니다. 각 포도주 잔에 들어있는 양이 주어졌을 때, 최대 몇 리터의 포도주를 마실 수 있는지 계산하는 프로그램을 작성해야 합니다. ✅ 문제 조건 및 입력 ..

🔷 포도주 시식 (백준 2156번) ✅ 문제 설명 포도주 시식회에 온 효주는 테이블 위에 일렬로 놓여있는 포도주 잔 중에서 포도주를 마시려고 합니다. 각 포도주 잔에는 일정한 양의 포도주가 들어있으며, 다음 두 가지 규칙이 있습니다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하며, 마신 후에는 다시 원래 위치에 놓아야 합니다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없습니다. 효주는 가능한 한 많은 양의 포도주를 마시고자 합니다. 각 포도주 잔에 들어있는 양이 주어졌을 때, 최대 몇 리터의 포도주를 마실 수 있는지 계산하는 프로그램을 작성해야 합니다. ✅ 문제 조건 및 입력 ..

#️⃣ 백준 10844번 쉬운 계단 수 Python 문제 설명 문제 45656이라는 숫자를 예로 들어보면, 이 숫자는 모든 인접한 자리 숫자들의 차이가 정확히 1입니다. 4와 5는 차이가 1이고, 5와 6도 1, 6과 5 역시 차이가 1입니다. 이와 같이 인접한 자리 숫자들의 차이가 모두 1인 수를 "계단 수"라고 정의합니다. 이 문제에서는 정수 N이 주어졌을 때, 길이가 N인 계단 수의 총 개수를 계산해야 합니다. 단, 다음과 같은 조건이 주어집니다. 숫자는 0으로 시작할 수 없습니다. N은 1 이상 100 이하의 자연수입니다. 정답이 매우 클 수 있으므로, 1,000,000,000으로 나눈 나머지를 출력해야 합니다. ..

#️⃣ 백준 10844번 쉬운 계단 수 C++ 문제 설명 문제 45656이라는 숫자를 예로 들어보면, 이 숫자는 모든 인접한 자리 숫자들의 차이가 정확히 1입니다. 4와 5는 차이가 1이고, 5와 6도 1, 6과 5 역시 차이가 1입니다. 이와 같이 인접한 자리 숫자들의 차이가 모두 1인 수를 "계단 수"라고 정의합니다. 이 문제에서는 정수 N이 주어졌을 때, 길이가 N인 계단 수의 총 개수를 계산해야 합니다. 단, 다음과 같은 조건이 주어집니다. 숫자는 0으로 시작할 수 없습니다. N은 1 이상 100 이하의 자연수입니다. 정답이 매우 클 수 있으므로, 1,000,000,000으로 나눈 나머지를 출력해야 합니다. ..

🔷 백준 1904 01타일 Python 풀이 ✅ 문제설명 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨습니다. 이 타일들은 각각 0 또는 1이 쓰여 있는 낱장의 타일입니다. 어느 날 짓궂은 동주가 장난을 쳐서 0이 적힌 타일 두 장을 붙여서 하나의 \($00$\) 타일을 만들었습니다. 결국 사용할 수 있는 타일은 다음 두 가지뿐입니다. 1이 적힌 낱장 타일 (길이 1짜리) 0이 적힌 낱장 두 장이 붙어 있는 \($00$\) 타일 (길이 2짜리) 지원이는 이 두 가지 타일을 사용하여 길이가 \(N\)인 2진 수열을 만들고자 합니다. 예를 들어 \(N=1\)이라면 \(1\)만..

🔷 백준 1904 01타일 C++ 풀이 ✅ 문제설명 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨습니다. 이 타일들은 각각 0 또는 1이 쓰여 있는 낱장의 타일입니다. 어느 날 짓궂은 동주가 장난을 쳐서 0이 적힌 타일 두 장을 붙여서 하나의 \($00$\) 타일을 만들었습니다. 결국 사용할 수 있는 타일은 다음 두 가지뿐입니다. 1이 적힌 낱장 타일 (길이 1짜리) 0이 적힌 낱장 두 장이 붙어 있는 \($00$\) 타일 (길이 2짜리) 지원이는 이 두 가지 타일을 사용하여 길이가 \(N\)인 2진 수열을 만들고자 합니다. 예를 들어 \(N=1\)이라면 \(1\)만 가능..

🔷 부분수열의 합: DFS의 문제점과 DP로의 전환 ✅ 1. DFS 방식의 문제점 배열이 주어졌을 때, 숫자를 하나씩 선택하거나 선택하지 않아 만들 수 있는 모든 합을 찾는 문제를 생각합니다. 예시로 다음 배열을 생각합니다. A = [4, 7, 2, 5] 각 숫자는 독립적으로 선택(1)하거나 선택하지 않음(0)을 결정합니다. 이 과정에서 모든 가능한 경우의 수를 살펴보는 것이 DFS입니다. 모든 경우를 비트열(0과 1의 조합)로 표현하면 다음과 같습니다. 비트열 선택된 숫자 합 0000 없음 0 ..

백준 문제번호 24416번 문제명: 알고리즘 수업 - 피보나치 수 1 (C++) 문제 설명 문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있습니다. 아버지가 수업한 내용을 학생들이 잘 이해했는지 확인하기 위해 문제를 풀어봅니다. 주어진 n에 대해 재귀 호출과 동적 계획법(DP) 두 가지 방법으로 피보나치 수를 계산합니다. 각 방법이 실행된 횟수를 출력합니다. 테스트케이스 예시 입력: 5 출력: 5 3 (재귀는 if문을 5번 검사했고, DP는 덧셈을 3번 수행함) 입력: 30 출력: 832040 28 아이디어 재귀 함수를 만들어 n==1 or n==2 조건이 몇 번 실행되는지 센다. ..

🔷 백준 17626 Four Squares Python ✅ 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였습니다. 어떤 자연수는 여러 가지 방법으로 표현됩니다. 예를 들어, 26은 \(5^2 + 1^2\)로 표현할 수 있고, \(4^2 + 3^2 + 1^2\)로도 표현됩니다. 역사적으로 암산 명수들에게 주어진 문제 중 하나가 바로 자연수를 네 개 이하의 제곱수의 합으로 표현하는 것이었습니다. 1900년대 초 한 암산가는 \(15663 = 125^2 + 6^2 + 1^2 + 1^2\)라는 해를 8초 만에 구했고, 더 어려운 \(11339 = 105^2 + 15^2 + 8^2 + 5^2\)는 56초가 걸렸다고 ..