개발자되기 프로젝트

1. 그리디(Greedy)알고리즘?? "당장 눈 앞에 보이는 최적의 상황마을 쫓는 알고리즘"을 뜻한다. 항상 최적의 답을 도출하지는 않지만 최적의 해에 근사한 값을 빠르게 구하는데 용이하다. 기본적으로 "무조건 큰 경우대로", "무조건 작은 경우대로", "무조건 긴 경우대로", "무조건 짧은 경우대로" 등 극단적으로 문제에 접근한다. 즉 극단적인 경우로 문제에 접근하기 때문에 Sort(정렬) 기법이 함께 사용되는 경우가 많을 수 밖에 없다.

1. 문제 M이상 N이하의 수가 나열되어 순서에 상관없이 나열되어 있다고 할 때, 각 수가 몇 개인지 세어보자. 예를들어 20세 이상 100세 이하의 사람들이 한 장소에 머물러 있다. 연령에 따라 혹은 각 나이에 따른 인원을 체크하자. 2. 배열을 쭉 돌면서 ages배열에 나이 대 별로 counting을 추가한다. 데이터의 수에 computation time이 비례한다. 즉 O(n)이다. 3. 핵심은 찾고자 하는 값에 대한 배열을 만들고 그 배열에 바로바로 입력하는 것. 4. 코드 package Counting; import java.util.Arrays; public class counting { public static void main(String[] args) { int[] people = {55..

1. "모든" 경우에 대하여 탐색하여 결과를 찾음 --> 무식하게 다찾아보기. 2. 문제의 범위가 작은 경우 완전 탐색으로 해를 찾음 3. 수열, 조합과 같은 문제를 푸는데 사용됨. 4. 문제 정의 - 어느 국가에서 10만원, 20만원, 50만원, 100만원, 200만원, 500만원 지폐를 사용. - A는 3000만원 지불 필요. - 6가지 지폐를 활용하여 300만원 지불하는 방법은 모두 몇 가지? 5. 지폐가 늘어나면 for문이 추가됨. computation time이 지수적으로 증가함. 6. code package BruteForceSearch; public class bruteForceSearch { public static void main(String[] args) { int[] bills = ..

1. 지금 상황에서 가장 좋은 해결책을 찾는 알고리즘. 2. 여러 조합에 따른 그 해를 찾는 경우가 많음. 대부분의 조건은 "가장 금액이 큰 순서부터" or "가장면적이 큰 타일을 우선적으로" 등.. 3. 조건이 명확할 때 정확한 답을 찾을 수 있다. 4. 문제 정의 가게에 놀러간 A는 8370원 어치 물건을 구매했다. A는 동전을 아래와 같이 가지고 있다. 500원 : 20개 100원 : 20개 50원 : 20개 10원 : 20개의 동전이 있다. A는 금액을 지불할 때 단위가 큰 동전부터 지불하려고 한다. A가 지불하게 되는 각 동전의 개수를 구해라. 5. code package GreedyAlgorithm; public class greedyAlgorithm { public static void ma..