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

백준 2885번: 초콜릿 식사 (C++) 문제 백준 2885번 "초콜릿 식사" 문제는 상근이가 점심으로 초콜릿을 먹기 위해 필요한 최소한의 초콜릿 크기와 쪼개기 횟수를 구하는 문제입니다. 문제의 주요 내용은 다음과 같습니다: 초콜릿은 막대 모양이며, 정사각형 N개로 이루어져 있습니다. N은 항상 2의 제곱수(1, 2, 4, 8, 16, ...)입니다. 상근이는 최소 K개의 정사각형을 먹어야 하며, 초콜릿을 쪼개서 정확히 K개를 만들고 나머지는 선영이에게 줍니다. 초콜릿은 반으로만 쪼갤 수 있습니다(즉, 크기 D인 초콜릿은 D/2 + D/2로 나뉨). 입력: K (1 ≤ K ≤ 1,000,000) 출력: 구매해야..

백준 A와 B 2 (12919번) 파이썬 풀이 문제 설명 문제 주어진 문자열 S를 문자열 T로 변환할 수 있는지 확인하는 문제입니다. 사용 가능한 연산: 1. 문자열 뒤에 'A'를 추가. 2. 문자열 뒤에 'B'를 추가하고 문자열을 뒤집기. 입력: 첫 줄: 문자열 S (길이 ≤ 49). 둘째 줄: 문자열 T (길이 ≤ 50, S의 길이 S와 T는 'A'와 'B'로만 구성됩니다. 출력: S를 T로 만들 수 있으면 1, 아니면 0을..

백준 A와 B 2 (12919번) C++ 풀이 문제 설명 문제 주어진 문자열 S를 문자열 T로 변환할 수 있는지 확인하는 문제입니다. 사용 가능한 연산: 1. 문자열 뒤에 'A'를 추가. 2. 문자열 뒤에 'B'를 추가하고 문자열을 뒤집기. 입력: 첫 줄: 문자열 S (길이 ≤ 49). 둘째 줄: 문자열 T (길이 ≤ 50, S의 길이 S와 T는 'A'와 'B'로만 구성됨. 출력: S를 T로 만들 수 있으면 1, 아니면 0. ..

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

🔷 부분수열의 합📌 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.📌 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다.(1 ≤ N ≤ 20, |S| ≤ 1,000,000)둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.주어지는 정수의 절댓값은 100,000을 넘지 않는다.📌 출력합이 S가 되는 부분수열의 개수를 출력한다.📌 예제 입력 15 0-7 -3 -2 5 8📌 예제 출력 11📌 예제 입력 23 31 2 3📌 예제 출력 22📌 문제 설명우리가 풀어야 하는 문제는 단순하지만 실수하기 쉽습니다.수열의 각 원소를 하나 이상 선택해 부분수열을 만든 뒤, 그 합..

🔷 부분수열의 합📌 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.📌 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다.(1 ≤ N ≤ 20, |S| ≤ 1,000,000)둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.주어지는 정수의 절댓값은 100,000을 넘지 않는다.📌 출력합이 S가 되는 부분수열의 개수를 출력한다.📌 예제 입력 15 0-7 -3 -2 5 8📌 예제 출력 11📌 예제 입력 23 31 2 3📌 예제 출력 22📌 문제 설명우리가 풀어야 하는 문제는 단순하지만 실수하기 쉽습니다.수열의 각 원소를 하나 이상 선택해 부분수열을 만든 뒤, 그 합..

백준 4963번, 섬의 개수 Python 풀이문제 설명정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다.출력 ..

🧭 백준 4963번, 섬의 개수 — C++ 풀이✅ 문제 설명2차원 배열로 이루어진 지도가 주어진다.각 칸에는 1(육지) 또는 0(바다)가 들어 있으며,인접한 땅끼리는 상하좌우 + 대각선, 총 8방향으로 연결될 수 있다.이 지도를 보고, 서로 연결된 육지의 덩어리(=섬)가 몇 개인지 세어야 한다.🔹 입력 여러 개의 테스트케이스로 구성됨 각 테스트케이스의 첫 줄에는 가로(w)와 세로(h)가 주어진다 (1 ≤ w, h ≤ 50) 다음 h줄에는 w개의 0 또는 1로 이루어진 지도 정보가 주어진다 입력의 마지막 줄은 0 0 (종료 조건)🔹 출력 각 테스트케이스마다 섬의 개수를 출력🔹 예제 입력3 21 1 11 1 15 41 0 1 0 01 0 0 0 01 0 1 0 11 0 0 1 00 0🔹 예..

🔷 백준 2468번: 안전 영역 (DFS, 스택 사용)문제 링크 바로가기 🔗🔷 문제 요약장마철에 어떤 지역에 비가 왔을 때, 일정 높이 이하의 지점은 물에 잠긴다고 가정합니다.이때, 물에 잠기지 않고 연결되어 있는 지점들을 하나의 안전 영역이라고 할 때,모든 강수량 상황에 대해 물에 잠기지 않는 안전 영역의 최대 개수를 구하는 문제입니다.🔷 문제 조건 요약지도는 N x N의 2차원 배열각 칸에는 1~100 사이의 높이 정보가 있음비의 양이 증가할수록 낮은 지점부터 잠김잠기지 않은 지점 중 상하좌우로 연결된 구역이 하나의 안전 영역🔷 나의 풀이 접근법1. 기본 전략비의 양을 0부터 100까지 바꾸어가며 시뮬레이션각 강수량마다 안전한 지역을 DFS로 탐색탐색한 영역은 방문 처리 (check 배열)각..