알고리즘/알고리즘 개념8 [알고리즘 개념] 다익스트라(Dijkstra) 개념설명다익스트라 알고리즘은 노드와 노드의 사이 간선에 가중치가 있을 때 특정 노드에서 다른 노드로 가는 최단거리를 구하는 알고리즘이다.내가 기존에 알던 방식은배열에 각각의 최단거리 갱신 -> 배열에서 최솟값 찾기 -> 그 최솟값을 기준으로 다시 탐색하기 였는데여기서 가르친 방법은 배열에서 최솟값 찾는 과정의 효율성을 증가시키기 위해서 우선순위큐를 썼다.파이썬 코드로 되어있어서 처음에는 이해가 잘 되지 않았지만, 지피티의 도움을 받아 자바로 이해해보았다(확실히 파이썬이 간단하긴 하다.. 옮기고싶지만 가면 돌아올 수 없을것 같아 망설여진다ㅎㅎ) 이러한 노드와 간선들이 주어진다. 그 다음 시작 노드인 5를 기준으로 각 노드까지 가는데 얼마나 드는지를 나타내는 dist배열을 생성한다.시작노드인 5를 기준으로는.. 2025. 2. 24. [알고리즘 개념] Deque Deque란?deque는 덱이라고 불리고, 스택과 큐를 합쳐놓은 자료구조이다.스택, 큐와 달리 양 끝에서 삽입과 삭제가 모두 가능하다. 시간복잡도는 모두 O(1)이다!위와 같이 양쪽에서 push와 pop이 가능하니, 각 명령어 앞에 앞에서 빼는지, 뒤에서 빼는지를 적어두어야한다. Deque 사용법변수선언import java.util.Deque;import java.util.ArrayDeque;public class Main { public static void main(String[] args) { Deque dq = new ArrayDeque(); }}선언은 이런식으로 Deque으로 하면 된다. 값 넣고 빼기addFirst(E)맨 앞에 데이터 E를 추가합니다. addLast(E).. 2025. 2. 23. [알고리즘 개념] 객체 정렬하기 가끔 알고리즘을 풀다보면 객체를 특정 인자를 기준으로 정렬해야할 때가 온다.그럴 때는 해당 객체 클래스에서 Comparable 인터페이스를 구현하면 된다 class Student implements Comparable { int kor, eng, math; public Student(int kor, int eng, int math){ this.kor = kor; this.eng = eng; this.math = math; } @Override public int compareTo(Student student) { // 국어 점수 기준 오름차순 정렬 return this.kor - student.kor; }};오름차순 기준으.. 2025. 2. 23. [알고리즘 개념] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘은 문제에서 요구하는 값을 빠르게 구하기 위해 현재 상황에서 최선의 방법부터 탐색하는 알고리즘입니다. 예를 들어, 1,10,50,100원의 동전으로 4567원을 만들기 위한 최소한의 동전 수를 구하는 문제가 있다고 합시다. 이 때 1원으로 4567원을 만드는 방법 먼저 구하는 것 보다는 100원으로 채울 수 있는한 가득 채우고, 그 다음 50원, 10원, 1원을 차례로 메꾸면 훨씬 빠르게 답을 구할 수 있겠죠? 그리디 알고리즘은 최적의 답을 구하기 힘든 복잡한 문제에 대해 실제 답에 근사한 결과를 빠르고 간결하게 구하고 싶을 때 자주 사용됩니다. 어떤 배열이 주어지고, 해당 배열속의 특정 구간의 합 중 가장 큰 값을 구하라는 문제가 있다고 가정합시다. 이 문제에서 그리디를 사용하는 방법은 .. 2023. 9. 11. [알고리즘 개념] 이진탐색 이진탐색은 원하는 수를 배열에서 탐색하고자 할 때, O(logN)으로 효율적인 탐색을 할 수 있게 해주는 알고리즘이다. 이진탐색은 배열의 처음과 끝을 직접 수정해나가며 원하는 값을 찾는 과정을 거친다. 이진탐색의 기본적인 과정 배열을 오름차순으로 정렬한다. 탐색할 배열의 처음과 끝을 의미하는 변수를 설정한다.(left, right) left와 right의 가운데 값(mid) 과 탐색하는 값을 비교한다. 크다면 -> left를 mid + 1로 수정한다.(mid보다 작은 쪽에는 원하는 값이 없는게 확실하니까) 작다면 -> right를 mid - 1로 수정한다.(mid보다 큰 쪽에는 원하는 값이 없는게 확실하니까) 만약 mid값과 탐색중인 값이 동일하면 index를 출력하고 종료한다(탐색 성공) 위 과정을 w.. 2023. 9. 10. [알고리즘 개념] Map, Set, Queue HashMap TreeMap HashSet TreeSet PreorityQueue HashMap HashMap는 해싱을 기본으로 데이터를 저장한다. HashMap에는 (Key,Value) 형태로 데이터가 저장된다. HashMap은 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)이라는 장점이 있다. HashMap는 TreeMap과는 다르게 데이터의 순서는 고려하지 않는다. 1. HashMap 선언하기 HashMap hashmap이름 = new HashMap(); 2.HashMap에 데이터 넣기 m.put(Key, Value) 3.HashMap에 있는 데이터 제거하기 m.remove(Key) 4.HashMap에서 특정 key의 value값 받기 m.get(Key) 5. 특정 key가 HashM.. 2023. 9. 6. 이전 1 2 다음
