백준 - 알고리즘 수업 - 피보나치 수 2 24417번 [3일차]시간제한메모리 제한1초512MB문제오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.피보나치 수 재귀호출 의사 코드는 다음과 같다.fib(n) { if (n = 1 or n = 2) then return 1; # 코드1 else return (fib(n - 1) + fib(n - 2));}fibonacci(n) ..
jjuya
백준 - 알고리즘 수업 - 피보나치 수1 24416번 [3일차]시간제한메모리 제한1초512MB문제오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.피보나치 수 재귀호출 의사 코드는 다음과 같다.fib(n) { if (n = 1 or n = 2) then return 1; # 코드1 else return (fib(n - 1) + fib(n - 2));}fibonacci(n) {..
재귀함수로 문제를 풀던중 너무 큰 값이 들어갔을 때 스택 오버플로우가 발생했다재귀 방식과 유사한 DP방식을 알아볼까한다!중복되는 하위 문제와 최적 부분 구조를 활용하여 문제를 해결 동적 계획법(DP : Dynamic programming)이란?하나의 큰 문제를 여러 개의 작은 문제로 나누고, 같은 문제라면 한 번씩만 풀어 그 결과를 저장해서 다시 큰 문제를 해결할 때 사용) 효율적으로 해결하는 알고리즘 DP사용 방법모든 작은 문제들을한 번만! 풀어야 하는 게 point!정답을 구한 작은 문제를 어딘가에 메모해두어야 함다시 그 보다 큰 문제를 풀어갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과 값을 다시 사용 DP 구성문제분할 : 하나의문제를 작은 하위 문제로 나누어 해결중복계산 방지 :..
백준 - 수들의 합 5 2018번 [2일차]시간제한메모리 제한2초32MB문제어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 입력첫 줄에 정수 N이 주어진다. 출력입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오 나의코드package day2;im..
백준 - 수들의 합 2003번 [2일차]시간제한메모리 제한0.5초128MB문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. 출력첫째 줄에 경우의 수를 출력한다. 나의코드import java.io.BufferedReader;import java.io.IOException;import java...
투포인터란?- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘- 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬의 counquer영역의 기초가 되기도 함 특정한 합을 가지는 부분 연속 수열 찾기투포인터의 대표적인 알고리즘 문제어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스를 가리키도록 한다2. 현재 부분 합이 M과 같다면 카운트한다.3. 현재 부분합이 M 보다 작다면(sum 4. 현재 부분합이 M 보다 크거나 같다면 (sum >= M) start를 1 증가시킨다. ( start++ ) 5. 모든 경우를 확인할 때까지 2-4번을 반복한다..
백준 - 뜨거운 붕어빵 11945번 [2일차]시간제한메모리 제한1초32MB문제고려대학교에 입학한 새내기 호돌이는 안암역을 지나다가 한 붕어빵 장수를 만났어요.“안녕, 안녕, 안녕하십니까, 아저씨! 붕어빵 두 개 주세요.”“안녕을 세 번 외쳤으니 붕어빵 세 개!”붕어빵 두 개의 값을 내고 세 개를 받은 호돌이는 기분이 좋았어요. 호돌이가 붕어빵 하나를 꺼내어 한 입 물었는데…. 너무 뜨거워서 그만 붕어빵을 떨어뜨리고 말았어요ㅠㅠ붕어빵은 자유 낙하운동을 하면서 땅에 떨어졌는데 신기하게도 좌우가 뒤집힌 모양으로 착지했답니다. 호돌이가 붕어빵을 한 입 물기 전의 모양이 입력으로 주어지면, 땅에 떨어졌을 때에는 어떤 모양일지 출력하세요. 입력첫째 줄에는 두 개의 정수 N과 M(0≤N,M≤10)이 주어집니다. 둘째..
백준 - 별 찍기 - 8 2445번 [2일차]시간제한메모리 제한1초128MB문제예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.* *** ***** ******* ****************** ******* ***** *** *// 5 나의코드import java.io.BufferedWriter;import java.io.IOException;import java.io.OutputStreamWriter;import java.util.Scanner;public class Solution3 { public static vo..
백준 - 별 찍기-1 2438번 [2일차]시간제한메모리 제한1초128MB문제첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 입력첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다. 나의코드import java.io.BufferedWriter;import java.io.IOException;import java.io.OutputStreamWriter;import java.util.Scanner;public class Main { public static void main(String[] args) throws IOException { // 별찍기1 - 2438번 // 첫째 줄에는 별 1개,..
백준 - 구구단 2739번 [2일차]시간제한메모리제한1초128MB문제N을 입력받은 뒤, 구구단 N단을 출력하는 프로그램을 작성하시오. 출력 형식에 맞춰서 출력하면 된다. 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 9보다 작거나 같다. 출력출력형식과 같게 N*1부터 N*9까지 출력한다 나의코드import java.io.IOException;import java.util.Scanner;public class Main { public static void main(String[] args) throws IOException { // 구구단 - 2739번 // 입력받은 N 으로 N단의 구구단 출력 // n * 1 = n; // n * 2 = ..
