수민's 개발 이야기

💡기본 정보유형: DP풀이 날짜: 2025년 01월 31일 풀이방법 한줄 요약: i번째 날의 일을 선택하는지 안하는지에 맞춰 최댓값 확인 💡문제에서 구해야 할 것상담원으로 일하고 잇는 백준이는 퇴사를 하고자 함오늘부터 N+1일 째 되는 날 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고함 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁했고 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아둠 Ti : 상담을 완료하는데 걸리는 기간Pi : 상담을 했을 때 받을 수있는 금액 N=7인 경우에 다음과 같음1일에 잡혀있는 상담은 총 3일이 걸리며 상담했을 때 받을 수 있는 금액은 10 , 5일에 잡혀있는 상담은 총 2일이 걸리며 받을 수 있는 금액은 15상담을 하는데 필요한 기간은 1일보다 ..

밀라 알고리즘 스터디 2025. 2. 2. 00:01

💡기본 정보유형: DP풀이 날짜: 2025년 01월 30일 풀이방법 한줄 요약: bottom-up형식으로 점화식 세워서 구현 💡문제에서 구해야 할 것2*n 크기의 직사각형을 1*2 , 2*1 타일로 채우는 방법의 수를 구하는 프로그램- 입력 : 첫째 줄에 n이 주어짐- 출력 : 첫째 줄에 2*n크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지 출력 💡알고리즘 설계- Bottom-up 방식으로 반복문 구현- dp[1] = 1- dp[2] = 2- dp[3] = 3- dp[4] = dp[3] + dp[2] = 5     => dp[N] = dp[N-1] + dp[N-2] : 점화식💡CODEconst fs = require("fs");const N = Number(fs.readFileSy..

밀라 알고리즘 스터디 2025. 1. 30. 21:14

💡기본 정보유형: DP풀이 날짜: 2025년 01월 29일 풀이방법 한줄 요약: 각 계산을 1을 빼는 것과 비교해서 더 적은 횟수인 것을 출력 💡문제에서 구해야 할 것정수 X에 사용할 수 있는 연산은 다음과 같이 세가지   - X가 3으로 나누어 떨어지면 3으로 나눔   - X가 2로 나누어 떨어지면 2로 나눔   - 1을 뺌정수 N이 주어졌을 때 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 함 연산을 사용하는 횟수의 최솟값 출력- 입력 : 첫째 줄에 1보다 크거나 같고 10^6 보다 작거나 같은 정수 N이 주어짐- 출력 : 첫째 줄에 연산을 하는 횟수의 최솟값 출력 💡알고리즘 설계- Bottom-up 방식으로 반복문 구현- 1일때는 0- 2의 배수면 2로 나눔=> dp[N] = min(..

밀라 알고리즘 스터디 2025. 1. 29. 22:43

💡기본 정보유형: DP풀이 날짜: 2025년 01월 28일 풀이방법 한줄 요약: bottop-up형식으로 점화식 세워서 구현 💡문제에서 구해야 할 것피보나치 수는 0과 1로 시작함 . 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1임 그 다음 2번째부터는 바로 앞 두 피보나치 수의 합이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2) 가 됨n이 주어졌을 때 n번째 피보나치 수를 구하는 프로그램을 작성하시오- 입력 : 첫째 줄에 n이 주어짐 . n은 90보다 작거나 같은 자연수- 출력 : 첫째 줄에 n번째 피보나치 수를 출력💡알고리즘 설계- Bottom-up 방식으로 반복문 구현- F0 = 0   F1 = 1   F2 = F1 + F0 = 1   Fn = Fn-1+Fn-2  💡COD..

밀라 알고리즘 스터디 2025. 1. 28. 23:50

💡기본 정보유형: DP풀이 날짜: 2025년 01월 27일 풀이방법 한줄 요약: bottom-up형식으로 점화식 세워서 구현 💡문제에서 구해야 할 것계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임 그림1과 같이 각각의 계단에는 일정한 점수가 쓰여있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게됨그림2와 같이 시작점에서 첫번째 , 두번째, 네번째 , 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25+ 20 = 75점이 됨계단 오르기 규칙1) 계단은 한 번에 한 계단이나 두 계단씩 오를 수 있음2) 연속된 세 개의 계단을 모두 밟아서는 안됨 , 단 시작점은 계단에 포함되지 않음3) 마지막 도착 계단은 반드시 밟아야 함각 계단에 쓰여있는 점..

밀라 알고리즘 스터디 2025. 1. 27. 23:07

밀라 알고리즘 스터디 4주차 개념 정리  ✍🏻DP: Dynamic Programming 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것- 이미 계산된 결과는 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 함- 메모리 적절히 사용하여 수행시간 효율성 향상 ✍🏻DP를 사용하는 경우 : 일단 재귀함수, 그리디 , 완전 탐색 등 다른 방법으로 풀 수 있는지 생각 : 그 이후로 코드 개선이나 되는 경우가 없으면 DP를 고려- 대표적인 사용 경우       : 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있을 때 (= 작은 문제의 답을 모아서 큰 문제를 해결함)      : 중복되는 부분 문제 - 동일한 작은 문제 반복..

밀라 알고리즘 스터디 2025. 1. 27. 21:58

💡기본 정보유형: DFS/BFS풀이 날짜: 2025년 01월 25일 풀이방법 한줄 요약: BFS를 활용해서 방문 체크하며 여러 최단 경로 찾기 💡문제에서 구해야 할 것수빈이는 동생과 숨바꼭질 중수빈이는 현재 점 N에 있고 , 동생은 점 K에 있음 N과 K 모두 0 이상 100000 임수빈이는 걷거나 순간이동을 할 수 있음. 수빈이의 위치가 X일때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 됨순간이동을 하는 경우엔 2*X의 위치로 이동하게 됨수빈이와 동생의 위치가 주어졌을 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고 가장 빠른 시간으로 찾는 방법이 몇가지 인지 구하는 프로그램- 입력 : 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어짐. N과 K는..

밀라 알고리즘 스터디 2025. 1. 25. 11:16

💡기본 정보유형: DFS/BFS풀이 날짜: 2025년 01월 24일 풀이방법 한줄 요약: BFS를 활용해서 방문 체크하며 최단 경로 찾기 💡문제에서 구해야 할 것수빈이는 동생과 숨바꼭질 중수빈이는 현재 점 N에 있고 , 동생은 점 K에 있음 N과 K 모두 0 이상 100000 임수빈이는 걷거나 순간이동을 할 수 있음. 수빈이의 위치가 X일때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 됨순간이동을 하는 경우엔 2*X의 위치로 이동하게 됨수빈이와 동생의 위치가 주어졌을 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램- 입력 : 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어짐. N과 K는 정수- 출력 : 수빈이가 동생을 찾는 가장 빠른 시간을 ..

밀라 알고리즘 스터디 2025. 1. 24. 23:26