https://www.acmicpc.net/problem/2577처음 알고리즘을 공부할때 당연하게도 풀어야할 배열의 가장 기초 문제를 풀어봤습니다 :) import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int multiple = 1; for (int i = 0; i digits = new ArrayList(); String numberStr = String.valueOf(multiple); for(char c : numberStr.toCharArray()) { ..
1. 탐욕 알고리즘이란?Greedy algorithm 또는 탐욕 알고리즘이라고 불러옴최적의 해에 가까운 값을 구하기 위해 사용여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제 1 : 동전 문제 지불해야 하는 값이 4720원일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. * 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 * 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨public class GreedyAlgorithm { public void coinFunc(Integer price, ArrayList coinLis..
1. DFS 알고리즘 구현 자료구조 스택과 큐를 활용함 * needVisit 스택과 visited 큐, 두 개의 자료 구조를 생성 BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있음을 인지해야 함 public class DFSSearch { public ArrayList dfsFunc(HashMap> graph, String startNode) { ArrayList visited = new ArrayList(); ArrayList needVisit = new ArrayList(); needVisit.add(startNode); while(needVisit.size() > 0) { ..
1. BFS와 DFS란?대표적인 그래프 탐색 알고리즘 * 너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 * 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식 2. Java로 그래프를 표현하는 방법Java Collection Framework에서 제공하는 Hashmap과 ArrayList를 활용해서 그래프를 표현할 수 있음 그래프 예와 Java 표현 HashMap> graph = new HashMap>();graph.put("A", new ArrayList(Arrays.asList("B", "C")));// 등등3. BFS 알고리즘 구현자료구조 큐를 활용한 * needVisit 큐..
1. 그래프(Graph)란?그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용 2. 그래프(Graph) 관련 용어* 노드(Node) : 위치를 말함. 정점(Vertex)라고도 함 * 간선(Edge) : 위치 간의 관계를 표시한 선으로, 노드를 연결한 선이라고 보면 됨(link 또는 branch 라고도 함)* 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드)* 참고 용어 * 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 * 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수 * 진출 차수(Out-Degree) : 방향 그래프에서 외..
1. 이진 탐색(Binary Search)이란?탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 * 데이터가 정렬되어 있어야함 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘(Divide and Conquer)Divide : 문제를 하나 또는 둘 이상으로 나눈다. Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide : 리스트를 두 개의 서브 리스트로 나눈다. Comquer : 검색할 숫자(search) > 중간값이면, 뒷부분 / import java.util.ArrayList;public class BinarySearch { public boolean searchFunc(ArrayList dataLi..
1 . 순차 탐색(Sequential Search)이란?탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해 원하는 데이터를 찾는 방법 ArrayList testData = new ArrayList();for(int i = 0; i 순차탐색 알고리즘import java.util.ArrayList;public class SequencialSearch { public int searchFunc(ArrayList dataList, Integer searchItem) { for(int index = 0; index
브리지 패턴(Bridge Pattern)은 GoF 디자인 패턴 중 하나로, 기능과 구현을 분리하게 독립적으로 확장할 수 있도록 돕는 구조적 디자인 패턴입니다. 이 패턴은 객체지향 설계에서 클래스 폭발 문제를 해결하기 위해 사용되며, 두 개 이상의 독립적인 자원을 클래스 계층 구조로 분리해 각각의 계층을 따로 개발하고 확장할 수 있게 합니다. 1. 브리지 패턴의 정의와 의도브리지 패턴은 두 계층(추상화와 구현)을 연결하는 다리와 같습니다. 즉, 클라이언트는 상위 계층인 추상화와 작업하고, 추상화는 하위 계층인 구현에 작업을 위임합니다. 이 패턴의 목적은 하위 계층(구현부)과 상위 계층(추상화)을 분리하여 독립적인 확장을 가능하게 만드는 것입니다. 2. 브리지 패턴을 사용하는 의도이 패턴을 사용함으로써 기..
