반응형 Programming/Algorithm29 백준 알고리즘 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. 버블 정렬 알고리즘 백준 2750번 JAVA 버블정렬은 각 위치와 인접한 오른쪽 값과 비교해서 데이터를 교환하는 방식이다. 모든 인수들을 비교해서 마지막 위치에 가장 큰 값이 오도록 하는 정렬방법이다. 작업을 반복할 때 마다 비교 종료위치는 오른쪽으로 이동하게 된다. 버블정렬의 평균 복잡도 및 최악 복잡도는 O(n2) 다. 정렬을 하는 경우게 가장 많이 사용하는 방법이다. 백준 코딩 2750번 정렬 문제도 버블정렬로 간단하게 해결 할 수 있다. JAVA 코드 import java.util.Scanner; import java.util.Arrays; public class ArrangeTest{ public static void main(String []args){ Scanner inputValue = new Scanner(System.in); in.. 2022. 2. 14. Brute Force Algorithm 브루트 포스 알고리즘 JAVA What is Brute Force Algorithm? 1990년대 청와대 해킹 사건이 발생했다. 당시 범인은 김재열이었고, 비밀번호를 뚫어던 사건이다. 당시 김재열 해킹과정에서 사용한 방법이 바로 Brute Force Algorithm 방식이다. 비밀번호는 어디에나 존재한다. 인가된 사용자만 접근할 수 있도록 하기 위한 장치다. 이 비밀번호를 뚫기위한 최적의 방법이 Brute Force Algorithm이다. 어렵게 생각할 필요없이 가능한 모든 조건의 입력값을 하나씩 넣어보는 것이다. 키전수조사 혹은 무차별 대입 공격이라고도 부른다. Brute Force Algorithm은 항상 100%의 정확도를 보인다는 장점을 가진다. 암호학에서도 비밀번호를 뚫기 위한 가장 확실한 방법으로 인정받고 있다. 아라비안.. 2022. 2. 13. 이전 1 2 3 4 5 다음 반응형