❒ Description이분 탐색의 동작과정을 정리하자.     ❒ Binary Search 이진 검색이란 정렬된 배열에서  타깃을 찾는 검색 알고리즘이다. 어떠한 경우에는 O(logN)의 시간복잡도를 갖는다. 동작 방식은 아래와 같다.      ❒ 효율적인 중앙 찾기만약 아래와 같이 중앙 위치를 찾는면 중앙 값은 0이 나오게 된다.int start = Integer.MAX_VALUE;int end = Integer.MAX_VALUE;int mid = (start + end) / 2;그 이유는 start와 end의 합이 자료형의 최댓 값을 넘어가기 때문이다.  이런 경우를 방지하기 위해서 다음과 같이 중앙 값을 찾아야 한다.int start = Integer.MAX_VALUE;int end = Integ..

❒ Description[LeetCode#75] Sort Colors 문제를 풀면서 알게된 Dutch National Flag 알고리즘을 정리해보자.     ❒ DNF 알고리즘1. DNF란?Dutch National Flag Problem(네덜란드 국기 문제)은 컴퓨터 과학자 다이크스트라가 제안한 알고리즘문제로, 배열 내의 요소들을 세 개의 범주로 나누는 문제다. 네덜란드 국기의 색깔(빨강, 하양, 파랑)에 비유해서이름이 붙여졌다. 이 문제의 목표는 배열에 세 가지 다른 값이 있을 때, 이를 특정 순서대로 배열하는 것이다. 보통 이 문제는 0, 1, 2로이루어진 배열을 다루며, 0은 왼쪽에, 1은 중간에, 2는 오른쪽에 배치하는 것을 목표로 한다.  2. 동작 방식mid가 2이면 mid와 high의 값을..

❒ Description날짜2024.09.30 (월)레벨Medium제목Sort Colors링크https://leetcode.com/problems/sort-colors/description/?envType=problem-list-v2&envId=sorting알고리즘Dutch National Flag, Insertion-sort시간 복잡도O(N)     ❒ 문제 및 로직 분석이번 문제는 in-place 알고리즘을 사용해서 풀이해야 하는데, 그 중에서는 시간복잡도가 O(N)인 네덜란드 국기 (Dutch National Flag) 알고리즘을 구현해야 하는 문제이다. 물론 삽입 정렬로도풀이가 가능하지만 삽입정렬은 input의 크기가 커질수록 성능이 저하되기 때문에 여기서는 제외다.     ❒ Solution1..

❒ Description날짜2024.09.29 (일)레벨Easy제목Valid Anagram링크https://leetcode.com/problems/valid-anagram/description알고리즘정렬시간 복잡도O(N)     ❒ Solution1. Map counterpublic boolean isAnagram(String s, String t) { // 예외 if (s.length() == 1) { return s.equals(t); } // create counter map Map counter = new HashMap(); for (int i = 0; i entry : counter.entrySet()) { if (entry.getVal..

❒ Description날짜2024.09.29 (일)레벨Medium제목Largest Number링크https://leetcode.com/problems/largest-number/description/알고리즘삽입 정렬시간 복잡도O(NlonN)    ❒ 문제 및 로직 분석요구사항 : 주어진 배열을 가장 큰 하나의  숫자로 반환하라. 주어진 두 수 a,b를 더해서 비교해야 한다. ab 와 ba를 비교 후 내림차순 정렬     ❒ Solutionpublic String largestNumber(int[] nums) { String[] numsStr = new String[nums.length]; for (int i = 0; i { @Override public int compare(S..

❒ Description삽입 정렬의 구현방법을 정리하자.     ❒ Insertion sort 1. 동작 방식삽입 정렬은 target 값과 그 이전 요소들을 비교하면서, `target 인 경우에 swap하는 방식이다.   2. 특징내부 정렬 : 추가적인 배열을 사용하지 않고 원래 배열 내에서 정렬이 이루어진다.안정 정렬 : 같은 값의 원소들 간의 순서가 보존된다.온라인 정렬 : 정렬 과정 중 새로운 데이터를 처리할 수 있다. 3. 장단점장점거의 정렬된 데이터에서 매우 효율적이다.적은 데이터에 적합하다.추가 메모리 사용이 없다.단점비효율적 : 대규모 데이터에서는 비효율적이다.데이터가 역순의로 정렬된 경우 성능이 저하된다. 4. 시간 복잡도BestO(n)AverageO(n²)WorstO(n²)     ❒ ..

❒ Description날짜2024.09.27 (금)레벨Medium제목Insertion Sort List링크https://leetcode.com/problems/insertion-sort-list/description/알고리즘정렬시간 복잡도O(NlonN) 이번 문제는 삽입 정렬을 구현하면 되는 문제이다. 하지만 기본적으로 Linked List가 주어지기 때문에 까다롭다.     ❒ 문제 및 로직 분석먼저 삽입 정렬은 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠야 한다.sorted : 정렬을 끝낸 대상head : 정렬을 해야 할 대상그리고 몇가지 특이 케이스를 고려해야 한다. 1. 정렬된 결과 사이에 삽입해야 할 경우위 경우와 같이 `sorted.next.val = 3` 이 정렬되어야 할 ..

❒ Description날짜2024.09.27 (금)레벨Medium제목Merge Intervals링크https://leetcode.com/problems/merge-intervals/description/알고리즘정렬시간 복잡도O(NlonN)      ❒ 문제 및 로직 분석이번 문제는 겹치는 구간을 판단하는 아이디어가 필요한 문제이다.int[][] intervals = { {1, 3}, {8, 11}, {2, 6}, {15, 18} }i번 째 배열의 1번 째 요소와 i + 1 번째 배열의 0번 째 요소를 비교하면 겹침 여부를 판단할 수 있다.※ 겹치는 경우i 번째 배열의 1번 째 요소 >= i + 1 번째 배열의 0번 째 요소Range1과 Range2가 겹치는 범위인지 판단겹치는 경우라고 판단이 됐다면, ..