알고리즘/알고리즘 개념5 [알고리즘 개념] 그리디 알고리즘(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. [알고리즘 개념] iterator iterator이란?ArrayList, Stack, Queue, Deque 등과 같이 Colletion이 정의되어 있는 자료구조들을 컨테이너라고 부른다. 이 컨테이너 내에 있는 원소들을 순회하기 위해 사용하는 것이 iterator이다. 예를 들어, ArrayList를 순회하는 iterator을 만든다고 하자. 1. iterator 선언하기 ArrayList v = new ArrayList(); Iterator iterator = v.iterator(); 2. iterator 사용하기 iterator에 다음 노드가 있는지를 리턴하는 함수이다. iterator.hasNext() iterator의 다음 데이터를 리턴하는 함수이다. iterator.next() iterator 사용 예시 //iterator을 l.. 2023. 9. 5. [알고리즘 개념] Shorten time technique 누적합 좌표압축 LR Technique +1-1테크닉 전처리 투포인터 누적합 배열이 주어지고, n번 인덱스부터 m번 인덱스까지 더한 값을 구하라는 문제가 있을 때, 브루트포스로 풀면 하나하나 더해야 하므로 시간복잡도가 O(n)이 된다. 하지만, (위와 같이 현재 인덱-스의 값 + 이전 인덱스를 모두 더한 값을 저장하는 배열)을 만들면, m번 인덱스에서 n번 인덱스를 빼면 문제에서 원하는 값이 바로 나온다. 이렇게 누적합을 사용하면 시간복잡도가 O(1)이 된다. 이차원 배열에서는 조금 더 복잡하다. 이러한 배열이 있고, (a,b)에서 (c,d) 만큼 더한 값을 구하라고 하였을 때, 부분합을 이용해서 구하면 빠르다. 위 배열이 부분합이다. 각각의 인덱스는 (0,0)에서 해당 인덱스까지의 합을 의미한다. 각각.. 2023. 8. 23. 이전 1 다음
