Algorithm84 [백준 알고리즘][자바] 2231번 : 분해합 https://st-lab.tistory.com/98 [백준] 2231번 : 분해합 - JAVA [자바] www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다 st-lab.tistory.com 분해합이란 자연수 N과 N을 이루는 각 자리수의 합을 의미합니다. 예를들어, 216의 분해합은 216 + 2 + 1 + 6 = 225입니다. 이때 어떤 자연수 M(216)의 분해합이 N(225) 인 경우, M(216)을 N(225)의 생성자라고 합니다. 이때 첫째 줄에 자연수 N이 주어졌을 때 생성자를 출력합니다. 자연수 N의 생.. 2022. 1. 9. [자바] 가장 빠른 정렬 알고리즘 - 퀵 정렬 (Quick Sort) 퀵 정렬 Quick(빠른) + Sort(정렬) 퀵 정렬은 가장 빠른 정렬 알고리즘으로 잘 알려져 있습니다. 퀵 정렬은 데이터 그룹에서 그룹을 나누는 기준인 피벗(pivot)을 선택하고, 피벗을 기준으로 그룹을 나누는 것을 반복하여 각 그룹이 1개가 되면 정렬을 마칩니다. 아래의 그림을 통해 자세하게 살펴보겠습니다. 왼쪽 끝에 커서를 pl, 오른쪽 끝의 커서를 pr, 중간의 x 화살표를 피벗이라고 하겠습니다. 양쪽 끝의 커서는 피벗과 비교할 숫자를 가리키게 됩니다. [pl] >= x 가 성립하는 데이터를 찾을 때까지 pl을 오른쪽으로 스캔합니다. [pr] pivot) { // data[pr] 값이 pivot보다 작은 수 탐색 pr--; } if (pl pivot) { // data[pr] 값이 pivot보.. 2022. 1. 1. [백준 알고리즘][자바] 2798번 : 블랙잭 & 브루트 포스(Brute Force) 브루트 포스 알고리즘의 개념 중의 하나로 영어의 뜻은 다음과 같습니다. Brute : 난폭한 + Force (힘) 이러한 뜻을 내포하고 있는 이유는 브루트 포스의 알고리즘은 정답으로 도출될 수 있는 모든 경우의 수를 탐색하는 알고리즘이기 때문입니다. 개념적으로 브루트 포스는 완벽한 알고리즘입니다. 왜냐하면 무조건 정답을 도출할 수 있기 때문이죠. 하지만 브루트 포스는 복잡도에 치명적인 단점을 가지고 있고 그에 따라 컴퓨터 자원도 문제가 될 수 있습니다. 브루트 포스를 이용하여 문제를 해결하기 위해서는 자료구조는 선형화시키는 것과 경우의 수를 빠트리지 않는 것이 중요하다고 할 수 있습니다. https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 .. 2021. 12. 31. [백준 알고리즘][자바] 11729번 : 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 알고리즘에서 유명한 하노이 탑입니다. 근데 저는 한 번도 접해보지 못한... 부족한 점이 많습니다. 단순히 최소 횟수를 출력하는 것이 아닌, 과정까지 출력되어야 하기 때문에 일단 예제부터 살펴보도록 하겠습니다. 입력으로는 원판의 개수가 주어지고 출력으로는 첫째 줄에는 최소 횟수를 출력하고 두 번째 줄부터는 그 과정을 출력합니다.' 다음은 원판이 3개 일때 입니다. 1번 장대에서 3번 .. 2021. 12. 4. [백준 알고리즘][자바] 2447번 : 별 찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 재귀 함수를 이용한 별 찍기 문제입니다. 첫째 줄에 주어지는 숫자 N은 3의 거듭제곱입니다.(3, 9, 27, 81...) 크기가 3인 패턴은 위와 같이 가운데가 비어진 *** * * *** 패턴입니다. 만약 N이 3보다 큰 수(9, 27, 81..) 일 때는 크기 N/3의 패턴으로 둘러싼 형태입니다. 즉 문제에서 주어진 27의 패턴은 아래와 같습니다. 처음 문제를 접근.. 2021. 11. 28. [백준 알고리즘][자바] 10870번 : 피보나치 수 5 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 재귀 함수를 이용한 피보나치 수 구하기 문제입니다. 이번 문제는 친절히도 문제속에 N = 17일 때까지의 수가 나열되어 있습니다. Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2) (단, N >= 2) 피보나치 수의 공식은 위와 같고, 공식의 해석은 2번째 피보나치 수부터는 바로 앞의 두 피보나치 수의 합이 됩니다. 위의 공.. 2021. 10. 23. [백준 알고리즘][자바] 10872번 : 팩토리얼 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 정수 N의 팩토리얼을 구하는 문제입니다. 간단하게 for문을 이용하여 구현할 수 있지만, 이번 파트는 재귀 함수 이기 때문에, 재귀 함수를 이용하여 문제를 풀어보도록 하겠습니다. 제가 알고리즘을 시작한지 얼마 되지 않아서 재귀 함수 같은 부분에 매우 약하다는 것을 깨달았습니다. 그래서 차근차근 재귀에 대해 분해해보았습니다. 함수를 실행했을 때, 리턴 값은 아래와 같습니다. return factorial(N) * factorial(N-1) * factorial(N-2) * factorial(N-3).... 2021. 10. 23. [백준 알고리즘][자바] 1002번 : 터랫 https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제가 복잡해 보이지만 요약한다면 좌표평면 위에 두 점(조규현의 좌표, 백승환의 좌표)이 주어졌을 때, 각각 좌표에서 r1, r2만큼 떨어져 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성합니다. 단, 위치의 갯수가 무한대 일 경우에는 -1을 출력합니다. 어떤 하나의 좌표에서 거리 r만큼 떨어져 있을 수 있는 점들의 집합은 바로 반지름이 r인 원입니다. 따라서 류재명이 있을 수 있는 좌표는 두 개의 원을 그렸을 때 생기는 점들의 개수입니다. 두 .. 2021. 10. 21. [백준 알고리즘][자바] 4153번 : 직각삼각형 https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 피타고라스 공식에 의해 직각삼각형은 아래의 공식을 따릅니다. 제일 긴 변의 제곱 = 나머지 변의 제곱의 합 아래의 예제 입력과 같이 마지막의 세 개의 숫자가 0 0 0일 때, 프로그램을 종료합니다. 이 문제의 포인트는 단순히 직각삼각형이 맞는지 아닌지의 판단보다 입력으로 받은 세 변 중 가장 긴 변을 어떻게 뽑아내는지가 포인트인 문제입니다. 단순히 Math.max()를 통해 최댓값을 알아낸다 하더라도 다시 세 변중.. 2021. 10. 17. [백준 알고리즘][자바] 3009번 : 네 번째 점 https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 세 점이 입력으로 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 문제입니다. 위의 그림을 보시면 모든 직사각형은 크기와 위치만 달라질 뿐 위의 형태를 가지게 됩니다. 그리고 아래의 특징이 있습니다. x축, y축마다 각각 두 개의 숫자가 존재한다. 각각의 숫자들은 2번씩 쓰인다. 위의 특징들은 문제에서 제시한 조건 "축에 평행한" 이기 때문에 생기는 특징입니다. 조건들을 이용하여 문제에서 제시한 예제 입력을 보겠습니다. x축의 숫자 5와 7 y축에.. 2021. 10. 17. 이전 1 2 3 4 5 6 7 ··· 9 다음 반응형
