본문 바로가기
반응형

Programming256

백준 알고리즘 10870번 피보나치 수열 JAVA 백준 알고리즘 10870번은 피보나치 수를 구하는 알고리즘이다. 시작은 0과1로 시작하며 2 이상의 자연수 N이 주어졌을 때 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 순서로 진행된다. 피보나치 수열의 공식은 Fn = Fn-1 + Fn-2 (n ≥ 2)이다. 뒤의 2개의 수의 합이 현재의 수를 결정하게 되는 것이다. 유럽에서 최초로 피보나치 수를 연구한 건 레오나르도 다빈치라고 한다. 토끼의 수가 늘어나는 원리로 설명했었는데, 태어난지 얼마 안된 토끼가 새로운 토끼를 낳을 수는 없기 때문이다. 풀이 백준 알고리즘 10870번 풀이 방법은 재귀함수를 사용하는 것이다. 재귀함수를 사용하기 위해서는 초기 셋팅값.. 2022. 2. 18.
백준 알고리즘 2447번 별 찍기 10 JAVA 백준 알고리즘 2447번은 별을 출력하는 문제다. 3의 제곱으로 만들어진 입력값을 받아서 중간이 비어있는 2차 배열을 만들어내야 한다. 입력값은 3, 9, 27 순서로 증가하게 되고, 그에 따라 그래프의 모양이 변하지만 팩토리얼 형식으로 출력된다. 백준 알고리즘 2447번 문제 해결은 재귀함수를 사용하는 것이다. 재귀함수를 통해서 반복 연산을 하기 위해서는 3가지 조건이 필요하다. 1. 탈출전략 2. 재귀 조건 변경 3. 초기 재귀 시작 조건 백준 알고리즘 2447번 문제의 경우 탈출전략을 세우기 위해서 입력값 N을 반복해서 쪼개는 작업을 진행해야 한다. N은 자연수 k에 대해 3의 거듭제곱이기 때문에 3으로 반복적으로 나눠줄 경우 최종적으로 1에 수렴하게 된다. 1이 되면 별을 찍고 탈출하게 된다. 재.. 2022. 2. 17.
JAVA StringBuilder란? StringBuffer란? 차이점 및 사용하는 이유 String 클래스 한계점 JAVA에서 String 객체를 사용하는 것은 메모리할당 및 해제를 사용한다. String 객체는 불변 객체이기 때문에 두개의 String 객체를 더하게 되면 새로운 String 객체가 탄생하게 된다. 그만큼 메모리 할당/해제 작업이 빈번해지는 것이고 메모리 부담이 커질 수 밖에 없다. 이런 문제의식 속에서 탄생한 방법이 StringBuilder 방버이다. String 객체를 더하는 연산을 수행할 때 새로운 String 객체를 생성하지 않는다. 기존 객체에 더하는 방식을 사용하여 메모리 부담을 완화할 수 있다. 프로그램이 고도화 되면서 좀더 라이트한 프로그램 운영을 위해서 필수적인 조건이다. String 객체 예제 public class StringTest { public st.. 2022. 2. 17.
백준 알고리즘 11729번 하노이 탑 이동순서 JAVA 하노이의 탑은 프랑스 수학자 에두아르 뤼카가 클라우스 교수의 필명으로 1883년 발표한 문제다. 한번에 한개의 원판만 옮길 수 있고, 큰 원판이 작은 원판 위에 있어서는 안된다. 하노이의 탑을 해결하는 방법은 재귀호출을 사용하는 것이다. 원판의 개수를 n이라 가정하면 (2n -1)번(메르센 수) 이동으로 원판을 모두 옮길 수 있게 된다. 백준 알고리즘 11729번 문제는 워낙 유명한 문제라서 알고리즘 강의에 꼭 등장하는 예제다. 핵심은 n개의 원판을 옮기는 문제를 원반 n-1개를 이동하는 문제로 나누는 과정을 재귀함수로 구현하는 것이다. 최종적으로 옮겨야 되는 원판이 1개가 되었을 때 이동해야 할 경로를 출력하고 복귀하게 된다. 마지막에 쌓이는 결과물들이 하나씩 쌓이면서 옮겨야 하는 원판의 개수 n은 줄.. 2022. 2. 16.
백준 10872 자바 JAVA 문제 풀이 피보나치 수열 팩토리얼 사용 백준 10872 문제는 팩토리얼 문제다. 주어진 자연수 N에 대해서 N!의 값을 출력하는 문제다. 해결방법은 재귀함수를 사용하는 것이다. Main 함수 밑에 새로운 재귀함수를 정의해서 팩토리얼 연산을 구현해 낸다. 재귀 함수의 조건은 2가지다. 첫번째 조건은 재귀함수에서 탈출하기 위한 조건이다. 아래에서는 주어진 매개변수가 1보다 작을 경우 탈출 조건으로 지정했다. 탈출 시 재귀함수가 반복되면서 할당된 resultFibo 변수를 반환한다. 두번째 조건은 재귀를 해주는 부분이다. return 부분에 주어진 매개변수 보다 1을 줄여나가면서 재귀함수를 반복해준다. JAVA 코드 import java.util.Scanner; public class Recursion { public static int resul.. 2022. 2. 16.
백준 15649 백트래킹 알고리즘 N과 M(1) 풀이 백준 15649 문제는 백트래킹 알고리즘을 다룬다. 트리 형태로 만들어진 노드들을 순회하면서 가장 유망한 노드를 선택하여 연산을 진행한다. 이 후 부모 노드로 돌아와서 새로운 노드를 찾아나서는 구조다. 노드를 순회하기 위해서는 재귀함수를 사용해야 한다. 재귀함수에는 탈출조건을 추가해줘야 한다. 현재 노드를 기억하기 위해서 depth 변수를 사용해서 탈출조건값을 만족시킨다. 노드가 순회하는 과정을 총 18단계에 걸쳐서 자세히 살펴본다. 초기단계 N은 자연수의 크기 = 3 M은 자연수 내의 수열 = 2 1단계 depth = 0 recur(0)함수를 호출한다. 최초 isVisited[]는 모두 false로 초기화 되어 있어 for문 안에서 arr[0]을 1로 변환한다. recur(1) 함수를 호출한다. 2단계.. 2022. 2. 15.
반응형

티스토리툴바