Learn From Failure

1. 문제 분석     1) T개의 테스트케이스가 주어진다.     2) 각 테스트케이스는 반복 횟수 R과 문자열 S가 주어진다.     3) S의 각 문자를 R번 반복하여 출력한다. 2. 제약 조건      1 ≤ T ≤ 1,000      1 ≤ S ≤ 20      1 ≤ R ≤ 8 3. 의사결정     1) T를 입력받고, T만큼 for문을 돌린다.     2) R과 S를 공백으로 구분하여 입력받는다.     3) S를 char[]로 만들지 않고 인덱스를 사용해 R번 출력한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;p..

Algorithm 2024. 11. 15. 09:42

메모이제이션은 동적 프로그래밍(Dynamic Programming, DP) 기법 중 하나로,이미 계산한 값을 저장하여 중복 계산을 피하고 속도를 개선하는 방법이다.특히 재귀 알고리즘에서 같은 문제를 반복적으로 호출할 때 유용하게 사용된다. 원리 1. 이미 계산한 문제를 저장한다. - 어떤 함수가 이미 계산한 값을 저장해 두었다가, 같은 입력으로 호출될 때 저장된 값을 반환하여 재계산을 피한다.2. 재귀 호출의 최적화 - 반복적으로 호출되는 동일한 연산을 저장된 값을 통해 빠르게 참조하므로 계산 속도가 빨라진다.3. 탑다운 접근법 - 메모이제이션은 주로 탑다운 (Top-Down) 방식에서 많이 쓰인다. 주어진 문제를 큰 문제에서 점점 작은 문제로 쪼개면서 풀어가는 방식은, 각각 작은 문제의 값을 저장해가면..

Algorithm 2024. 11. 14. 19:45

1. 문제 분석     1) 재귀 횟수 N을 입력받는다.     2) 기본 호출 1번 + N번 재귀함수를 호출한다. 2. 제약 조건    1 ≤ N ≤ 50 3. 의사결정     1) N을 입력받는다.     2) 재귀함수를 기본 1번 + N번 호출한다. 4. 문제 해결     1) underBar를 어디에 위치하느냐로 혼동을 겪었다. 스택이 생기고 사라질때마다 underBar가 변경되기 위해 재귀함수의 파라미터로 넣었다.     2) 큰따옴표 오타 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[..

Algorithm 2024. 11. 14. 17:28

1. 문제 분석     1) a, b, c를 받아서 재귀함수를 실행한 뒤 출력형식에 맞게 결과를 출력한다.     2) a, b, c = -1, -1. -1이 나올때까지 입력받는다.     3) a, b, c 계산할때마다 배열에 저장하고, 가능한 계산된 값을 활용한다. 2. 제약 조건    -50 3. 의사결정     1) a, b, c가 각각 0부터 20까지인 3차원 배열을 만든다.     2) for문을 만들고 a, b, c 입력받고, 한번 계산한 값은 저장해가면서 재귀함수를 호출한다.         - a, b, c가 -1인 경우 프로그램 종료         - a         - a > 20 or b > 20 or c > 20 인 경우 w(20, 20, 20) 반환         - a     ..

Algorithm 2024. 11. 14. 16:28

1. 문제 분석     1) 예제를 보면, N개의 사각형을 겹쳐 그리고 있다.     2) 가장 큰 사각형의 가로와 세로는 각각 4N-3이다.     3) 가장 마지막에는 정가운데에 *을 하나 찍고 마무리한다. 2. 제약 조건    1 3. 의사결정     1) N을 입력받는다.     2) 가로와 세로가 각각 4N-3인 2차원 배열을 만든다.     3) N부터 1까지 점점 작아지는 재귀함수를 호출한다.     4) N > 1일때까지 함수를 호출하면서 점점 작은 사각형을 그린다. (4개의 변을 그린다)     5) N = 1에 도달하면 정가운데에 *을 찍는다.     6) 완성된 2차원 배열을 출력한다. 4. 문제 해결     1) 코드 흐름을 만드는 과정에서 N과 4N-3을 혼용해서 사용했다. 혼용 ..

Algorithm 2024. 11. 14. 16:26

1. 문제 분석     1) T개의 문자열 S를 각각 입력받아서,     2) isPalindrome 함수의 반환값 + recursion 함수의 호출 횟수를 한줄에 공백으로 구분하여 출력 2. 제약 조건    1    1 3. 의사결정     1) T를 입력받는다.     2) T만큼 for문을 돌린다.     3) S를 입력받을때마다 isPalindrome 함수를 호출한다.     4) isPalindrome 함수는 recursion 함수를 호출한다.     5) recursion 함수는 (1) l이 r보다 크거나 같다면 1을 반환 / (2) 양쪽 값이 다르다면 0 반환 / (3) l이 r보다 작다면 다시 재귀함수 호출 import java.io.BufferedReader;import java.io.I..

Algorithm 2024. 11. 14. 16:24

1. 문제 분석1) 5에서 40 사이의 N이 주어진다.2) 코드 1과 코드 2를 각각 실행시키고, 각각 횟수를 카운트한다.3) 횟수를 출력한다. 2. 제약 조건5  3. 의사결정1) bufferedReader를 사용해 N을 받는다.2) 재귀호출 / 동적 프로그래밍 클래스를 각각 구현한다.3) 각 클래스 내에서 #코드1, #코드2가 실행되는 횟수를 세고 출력한다. 4. 문제 해결1) fib_count, fibonacci_count를 메인 클래스 안에다 선언했더니 자꾸 꼬였다. 전역변수로 설정하여 해결했다.2) fib_count가 다르게 출력되는 문제 : fib_count++;의 위치를 fib클래스 if문 안으로 옮겨서 n package com.sparta;import java.io.BufferedReade..

Algorithm 2024. 11. 14. 16:21

1. 문제 분석     1) N과 M을 입력받는다.     2) 첫행부터 N행까지 입력받는다.     3) 각 행의 내용을 좌우로 뒤집는다. (0번째 문자  M번째 문자)     4) 첫행부터 N행까지 출력한다. 2. 제약 조건    0   M3-1. 의사결정 (1) : Scanner와 StringBuilder를 사용하는 경우     1) N과 M은 정수이므로 nextInt()로 받는다.         * N과 M이 0일 경우 예외처리하는 코드를 추가한다.     2) 각 행을 입력받아 StringBuilder에 저장한다.     3) 각 행을 reverse하고 바로 출력한다. (배열을 사용하지 않는다)     4) StringBuilder를 초기화한다.     * 행별로 작업을 수행하려면 for문을 사..

Algorithm 2024. 11. 14. 16:18