생각하다 생각하다

피보나치 수열로 메모이제이션의 필요성 알아보기 피보나치 수열이란? 0과 1로 시작하고 이전의 두 수의 합을 다음 항으로 하는 수열을 피보나치 수열이라 함 0, 1, 1, 2, 3, 5, 8, 13, … 피보나치 수열의 i번째 값을 계산하는 함수 F를 정의하면 다음과 같다 F0 = 0, F1 = 1 Fi = Fi-1 + Fi-2 for i ≥ 2 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있음 fibo(n) IF n < 2: RETURN n ELSE : RETURN fibo(n-1) + fibo(n-2) 피보나치 수열의 문제점 앞의 예에서 피보나치 수를 구하는 함수를 재귀함수로 구현한 알고리즘은 아래와 같은데 이는 엄청난 중복 호출 문제를 초래함을 알 수 있다. 여기..

백준 17070. 파이프 옮기기 1 _Java 🧶 문제 설명 분류 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기..

백트래킹(Backtracking) 알고리즘 백트래킹 알고리즘이란? 백트래킹은 조합 최적화, 문제 해결 등 여러 문제에서 사용되는 알고리즘 기법 중 하나입니다. 주로 모든 가능한 경우의 수를 탐색하면서 해답을 찾는데 사용되며, 문제의 조건을 만족하지 않으면 해당 경로를 포기하고 이전 단계로 돌아가는 방식으로 동작합니다. 백트래킹 알고리즘 구현 단계 선택 (Choose): 다음으로 시도할 선택을 하거나, 다음 상태로 진행합니다. 조건 확인 (Constraint): 선택한 것이 조건을 만족하는지 확인합니다. 해결 여부 판단 (Is it a solution?): 현재 선택과 조건이 문제의 해결을 이끌어냈는지 확인합니다. 해결하지 못한 경우 (No): 선택한 것이 조건을 만족하지 않으면 이전 상태로 돌아갑니다. ..

백준 11723. 집합 _Java 🧶 문제 설명 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다..

백준 1157. 단어 공부 _Java 🧶 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String [] str = br.readLine().toUpperCase().split(""); String[] str2 =..

백준 27866. 문자와 문자열 _Java 🧶 문제 설명 단어 S와 정수 i가 주어졌을 때, S의 i번째 글자를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 S가 주어진다. 단어의 길이는 최대 1000이다. 둘째 줄에 정수 i가 주어진다. (1

백준 1546. 평균 _Java 🧶 문제 설명 세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다. 예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다. 세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다. 출력 첫째 줄에 새로운 평..

백준 10811. 바구니 뒤집기 _Java 🧶 문제 설명 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다. 바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N (1 ≤..