개발자되기 프로젝트

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..

이번에는 피보나치 수열을 구현해보자. 피보나치는 아래와 같이 n번 째 값은 n-1번째 n-2번 째 값의 합이다. 1. 먼저 함수에 표현된 대로 코드를 구성해 보자. 함수대로 표현하기 위해서는 재귀함수 방식을 활용해야 한다. 즉 int n에 해당하는 값을 구하기 위해 "n-2"번 째 값과 "n-1"번 째 값을 추가로 계산을 해줘야 한다. package fibonacci; public class FibonacciPractice { public int fibonacciRecur(int n){ if(n == 0) return 0; if(n == 1) return 1; return fibonacciRecur(n-2) + fibonacciRecur(n-1); } public static void main(Strin..

*Git : https://github.com/bsh6463/Maze bsh6463/Maze Contribute to bsh6463/Maze development by creating an account on GitHub. github.com 입구부터 출구까지 길을 찾자! 미로찾기는 stack으로 활용이 가능하다. 왜냐? 갈림길에서 한쪽 방향을 선택하고 쭉! 들어갔을 때(DFS) 길이 없다면 다시 갈림길로 돌아와서 다른 길로 가야한다. 즉, DFS의 개념이 사용된다. 다시말해, 길을 찾아갈 때 현재 노드와 인접한 노드들을 stack에 추가하고 stack 가장 맨위의 노드로 진행 했을 때, 더 이상 갈 노드가 없다면 stack에 있는 다음 노드를 꺼내서 가면 갈림길에서 다른 길로 가는 것과 동일한 효과이다..

2021.06.07 - [Java/알고리즘] - 최단경로 구하기 : Dijkstra algorithm 최단경로 구하기 : Dijkstra algorithm 시작 노드에서 전체 노드로 가는 최단 거리를 구하는 알고리즘. 이 알고리즘을 시행하면 시작노드부터 각 노드까지 최단 경로를 알 수 있다. 특징으로는 각 단계를 반복하면서 시작노드부터의 bsh-developer.tistory.com 앞서 한 노드로부터 각 노드 까지 최단 거리를 구하는 Diijkstra 알고리즘에 대해 알아봤다. 이번엔 알고리즘을 코드로 구현해보자. 크게 세 가지를 중점으로 작성했다. * 시작 노드를 기준으로 weight 행렬 작성하는 method - weight 배열은 djikstra 생성자에서 모두 inf(=9999)로 초기화. - ..

시작 노드에서 전체 노드로 가는 최단 거리를 구하는 알고리즘. 이 알고리즘을 시행하면 시작노드부터 각 노드까지 최단 거리를 알 수 있다. 특징으로는 각 단계를 반복하면서 시작노드부터의 각 노드까지 최단 거리를 계속 업데이트 한다. 현재 노드를 기준으로, 기존에 입력된 weight(현재 노드를 거치지 않음)가 더 작은지 현재 노드를 거치는게 weight가 작은지 비교해야한다. 즉 노드 v에 인접한 노드 w에 대하여 아래 조건이 성립하면 w에 대한 최단거리를 업데이트 한다. (원래 w로 가는 거리보다 v를 거쳐서 가는 거리가 가까우면 w가는 거리를 v거쳐서 가는 거리로 수정.) Yv + Cvw Yw = Yv + Cvw ex) Y1 + C1,2 < Y2 그 결과로 알고리즘이 종료되었을 때, 시..