농부공학자

ATM 얘도 그리디 알고리즘 문제 유형에 있는 문제이다. https://ticssfm.tistory.com/32?category=1008893 [Algorithm] 탐욕(그리디) 알고리즘 (greedy algorithm) 그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘 ticssfm.tistory.com 문제를 표로 만들어서 살펴보자 예시에서는 P1 = 3, P2 = 1 ... 이런식으로 5가지 수를 받았다. 이 줄을 오름차순 정렬 한 후 계산을 수행하는 것이 가장 효율적이라고 나타낸다. 그러므로 입력을 받은 후 오름차순 정렬을 하고 계산을 수행해야 하..

동전0 이 문제는 그리디 알고리즘 유형에 있는 문제이다. https://ticssfm.tistory.com/32?category=1008893 [Algorithm] 탐욕(그리디) 알고리즘 (greedy algorithm) 그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘 ticssfm.tistory.com 필요한 동전의 개수라는 말만 봐도 그리디를 사용함을 알 수 있다. 그리디는 가장 최적의 값을 우선적으로 할당해주는 알고리즘이므로 본 문제를 풀 때 가장 큰 값을 먼저 대입해봐야한다. Ai는 Ai-1의 배수라는 말은.. 어차피 입력은 여기서 해줄 것이기 ..

소수 정말 개많이 틀린 문제;;;.... 결국 남의 코드를 참고했다. 예전에 정리했던 적이 있었는데 최적의 코드라고 보기는 어려웠고 백준에서 맞은 사람의 코드도 살펴보았는데 다들 비슷하게 푼 느낌이라 넘어갔었다. 아무튼 이번 문제는 에라토스테네스의 체라는 방법을 다들 사용하였다...!! 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Baek2581 { // 소수 public static boolean prime[]; public static void main(String[] args) throws IOException { BufferedReader br = ..

그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘을 사용하면 그때그때 최대값이 될 것이라고 추측되는 값을 사용하게 된다. 따라서 5 다음에 7, 10, 8 중 가장 큰 값인 10을 사용하고 4, 3 중 큰 값인 4를 사용하게 된다. 이처럼 그리디 알고리즘이 문제의 해결에 있어서 최적의 해를 매번 보장하지는 않는다. 그러나 그리디 알고리즘은 계산 속도가 빠르다. 그리디 알고리즘이 적절하다고 판단되는 문제에서는 최적의 해를 빠르게 산출할 수 있다. 예시 출처 : 이것이 취업을 위한 코딩 테스트다 예를 들어 N = 5이고 각 모험가의 공포도가 2 3 1 2 2..

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 예시를 보자!! 이렇게 가운데에 있는 값을 확인하면서 검색하는 방법이 이진검색이다. 처음 시작할 때 a = 0이고 b = n-1값이면 검색할 가운데 값은 (a+b) / 2 값이 된다. 오름차순일 때 키값이 찾으려는 값보다 크면 b값은 중앙값 - 1 이 되고 키값이 찾으려는 값보다 작으면 a값은 중앙값 + 1이 된다. 이 방법을 코드로 짜보면 import java.util.Scanner; public class binarysearch { static int binSearch(int[] x, int n, int key) { int a = 0; int b = n - 1; do { int c = (a..

정수 n에 대하여 아래의 조건을 만족시키면 소수임을 알 수 있다. 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않는다. 먼저 어떤 정수 이하의 소수를 모두 나열하는 알고리즘을 직관적으로 풀어보자. public class PrimeNumber { public static void main(String[] args) { int counter=0; for(int n = 2; n

정숫값을 기수로 변환하는 알고리즘을 살펴보자. 기수 = 수를 나타내는 데 기초가 되는 수로 10진수, 2진수, 8진수, 16진수가 있다. 10진수 10진수는 아래 10종류의 숫자를 사용해 수를 나타낸다. 0 1 2 3 4 5 6 7 8 9 10진수의 각 자리는 아랫자리부터 100,10¹, 10², ...으로 10의 거듭제곱 값을 갖는다. 1234 = 1 x 10³ + 2 x 10² + 3 x 10¹ + 4 x 100 와 같이 풀어쓸 수 있다. 8진수 8진수는 아래 9종류의 숫자를 사용하여 수를 나타낸다. 0 1 2 3 4 5 6 7 8진수의 각 자리는 아랫자리부터 80, 8¹, 8², ...으로 8의 거듭제곱 값을 갖는다. 5306 = 5 x 8³ + 3 x 8² + 0 x 8¹ + 0 x 80 와 같이..

배열 요소를 역순으로 정렬하는 알고리즘을 살펴보자. 배열 역순 정렬 과정 위 그림은 n=7 일 때 역순으로 정렬하는 과정을 그린 그림이다. 교환 횟수는 n / 2 이며 n이 홀수일 때 가운데 요소는 교환하지 않기 때문에 나머지는 버려준다. 위의 예시에선 n = 7이므로 7 / 2 = 3이므로 3번의 교환이 이루어졌다. 교환 방법 위 그림에서 파란색의 자릿수를 i라고 하면 i와 n-i-1과의 교환이 계속해서 이루어지게 된다. 여기서 배열 안 값을 교환하는 방법으로 변수 t를 활용할 수 있다. 따라서 값의 교환은 다음과 같이 이루어진다. 메서드 swap 구현하기 배열 안의 두 요소를 교환하는 것은 자주 쓰이므로 독립적인 메서드로 구현하는 것이 좋다. //배열 요소 a[idx1]과 a[idx2]의 값 교환하기..