본문 바로가기

전체 글

 (162)
섹션 8 DFS, BFS - 7. 조합의 경우수(메모이제이션) 문제 설명조합의 경우의 수는 보통 nCr = n! / (n-r)!r!의 공식으로 계산되지만 이번 문제는 재귀 호출과 메모이제이션을 통해 아래의 조합 점화식을 이용하여 nCr을 계산해야 한다.입력 & 출력입력첫 줄: 두 자연수 n, r (3 ≤ n ≤ 33, 0 ≤ r ≤ n)출력조합값 nCr 출력예제 입력 & 출력예제 입력 1 5 3예제 출력 1 10예제 입력 2 33 19예제 출력 2 818809200해결 방법nCr = (n-1)C(r-1) + (n-1)Cr조합 점화식이 식은 파스칼의 삼각형 원리 기반메모이제이션을 통해 중복 계산 제거코드 구현 (Java)package partDfsBfs;import java.util.Scanner;public class Problem7 { static int[][] ..
섹션 8 DFS, BFS - 6. 순열 구하기 📌 문제 설명10 이하의 N개의 자연수가 주어졌을 때 이 중 M개를 선택하여 일렬로 나열하는 모든 순열을 출력하라.중복 없이 선택해야 하며순서를 고려하여 나열해야 한다.출력은 사전순(오름차순) 으로 정렬되어야 한다.📝 입력 & 출력입력첫 줄: 자연수 N, M (3 ≤ N ≤ 10, 2 ≤ M ≤ N)둘째 줄: N개의 자연수 (오름차순)출력가능한 모든 순열을 한 줄에 하나씩 출력출력 순서는 사전순으로 오름차순🔹 예제 입력 & 출력예제 입력 3 2 3 6 9예제 출력 3 6 3 9 6 3 6 9 9 3 9 6💡 해결 방법✅ 핵심 전략: DFS + 방문 체크 배열DFS를 통해 깊이 L까지 탐색현재 선택한 수를 pm[L]에 저장중복 방지를 위해 ch[i] 배열로 방문 여부 체크순열 생성이 끝나..
섹션 8 DFS, BFS - 5. 동전교환 📌 문제 설명여러 단위의 동전이 주어졌을 때무한히 동전을 사용 가능하다면주어진 금액 M을 최소 개수의 동전으로 교환하는 방법은 무엇일까?📝 입력 & 출력입력첫 줄: 동전 종류 수 N (1 ≤ N ≤ 12)둘째 줄: N개의 동전 단위 (각각 100원을 넘지 않음)셋째 줄: 거슬러 줄 금액 M (1 ≤ M ≤ 500)출력거슬러 줄 수 있는 최소 동전 개수🔹 예제 입력 & 출력예제 입력 31 2 515예제 출력 3💬 설명5원짜리 3개로 15원을 만들 수 있음 → 동전 3개💡 해결 방법✅ 핵심 전략: DFS + 백트래킹가능한 모든 동전 조합을 시도하면서 최소 개수인 경우만 추적중복 사용 가능 → 동전 하나를 여러 번 선택 가능백트래킹 조건:현재 사용한 동전 수(L)가 answer 이상이면 중단현재 합(..
섹션 8 DFS, BFS - 4. 중복순열 구하기 📌 문제 설명1부터 N까지의 자연수가 적힌 구슬이 있을 때,중복을 허용하여 M번을 뽑아 일렬로 나열하는 모든 경우를 출력하라.같은 숫자를 여러 번 뽑을 수 있다 (중복 허용)출력은 사전순으로 오름차순📝 입력 & 출력입력첫 번째 줄: 자연수 N, M (3 ≤ N ≤ 10, 2 ≤ M ≤ N)출력가능한 중복순열을 한 줄에 하나씩 출력출력 순서는 사전순🔹 예제 입력 & 출력예제 입력 3 2예제 출력 1 11 21 32 12 22 33 13 23 3💡 해결 방법✅ 핵심 개념: 중복순열 (Permutation with Repetition)중복 허용 → 뽑을 때마다 모든 숫자를 다시 선택 가능깊이 L이 m에 도달할 때마다 출력DFS를 이용해 순서를 고려하며 선택💻 코드 구현 (Java)package par..
섹션 8 DFS, BFS - 3. 최대점수 구하기(DFS) 📌 문제 설명정보올림피아드 대회 준비를 위해 현수는 선생님이 준 N개의 문제 중에서 최대한 많은 점수를 얻고자 한다.각 문제는 정해진 점수와 소요 시간이 있으며 총 제한 시간 M분 안에 풀 수 있는 문제들을 선택해얻을 수 있는 최대 점수를 구하라.각 문제는 한 번만 풀 수 있다.선택한 문제들의 총 소요 시간이 M을 넘으면 안 된다.📝 입력 & 출력입력첫 줄: 문제 개수 N (1 ≤ N ≤ 20), 제한 시간 M (10 ≤ M ≤ 300)다음 N줄: 각 문제의 점수, 소요 시간출력제한 시간 안에 얻을 수 있는 최대 점수🔹 예제 입력 & 출력예제 입력 5 2010 525 1215 86 37 4예제 출력 41💬 설명25점(12분) + 6점(3분) + 10점(5분) → 총 43점, 20분하지만 이렇게 선..
섹션 8 DFS, BFS - 2. 바둑이 승차(DFS) 📌 문제 설명철수는 시장에 가기 위해 트럭에 바둑이들을 태우려고 한다.하지만 트럭은 최대 C kg까지만 적재 가능하며총 N마리 바둑이들의 무게가 주어질 때C를 넘지 않으면서 태울 수 있는 최대 무게를 구하는 프로그램을 작성하라.📝 입력 & 출력입력첫 줄: 트럭의 허용 무게 C (1 ≤ C ≤ 100,000,000), 바둑이 수 N (1 ≤ N ≤ 30)둘째 줄부터: N마리 바둑이의 무게가 한 줄에 하나씩 주어진다.출력첫 줄: 트럭에 태울 수 있는 가장 무거운 무게🔹 예제 입력 & 출력예제 입력 259 58158423361예제 출력 242💡 해결 방법✅ 접근 방법가능한 모든 바둑이 조합을 부분집합 형태로 탐색한다.DFS를 이용해 각 바둑이를 태우거나 태우지 않는 두 가지 경우로 분기누적된 무게 su..
인턴 1주차 - Helm을 활용한 NestJS 애플리케이션 Kubernetes 배포 Helm을 활용한 NestJS 애플리케이션 Kubernetes 배포 실습저번 실습에 이어서 이번에는 Helm을 활용하여 NestJS 애플리케이션을 Kubernetes 클러스터에 배포하는 실습을 진행했습니다. Helm Chart를 생성하고 ClusterIP, NodePort, LoadBalancer 세 가지 Service 유형으로 로컬 환경에 배포해본 경험을 정리합니다. 🔹 Helm이란?Helm은 Kubernetes의 패키지 관리자입니다. Helm을 사용하면 여러 Kubernetes 리소스를 하나의 패키지로 묶어 관리할 수 있으며 이를 통해 재사용성과 배포 편의성을 크게 높일 수 있습니다.🔹 Helm의 핵심 구성 요소Chart: Kubernetes 리소스가 정의된 패키지 단위 (Chart.yaml, v..
인턴 1주차 - 쿠버네티스 실습(로컬에서 NestJS 애플리케이션 배포하기) 쿠버네티스 실습 – 로컬에서 NestJS 애플리케이션 배포하기앞서 Kubernetes의 구조와 개념을 학습한 뒤, 간단한 NestJS 애플리케이션을 직접 컨테이너화하고 로컬 쿠버네티스 클러스터에 배포하는 실습 과제를 수행했다. 해당 애플리케이션은 응답 테스트를 위해 현재 시간을 반환하는 단일 API로 구성하라는 요구사항이 있었다. Docker 환경에서 Kubernetes를 활성화한 후 Deployment와 Service 리소스를 적용하는 과정을 실습하면서 실제 동작 흐름과 리소스 간의 관계를 이해할 수 있었다.쿠버네티스 설치 및 초기 상태 확인Docker Desktop에서 쿠버네티스를 활성화하고 설치했다.kubectl version 명령어로 클라이언트와 서버 버전이 1.25.0으로 일치하는 것을 확인했다..

티스토리툴바