알고리즘 문제 풀이 검색 결과

해당 글 5건

[LeetCode] Java 448. Find All Numbers Disappeared in an Array

448번 문제 : 배열에서 사라진 모든 숫자 찾기 (풀이 소스) 1차 접근은 정렬을 먼저하고, 중복된 값을 제거하여 list로 담은 다음, 1부터 증가한 값부터 비교하여 값이 다르면 그 값을 담으려고 했으나 구현상 문제가 있었다. 고민끝에, 방법을 찾는 도 중 Arrays API에 이분탐색 함수에서 Arrays.binarySearch() API가 제공 되는걸 알게 되었다. 아이디어는 '정렬시켜놓고 자기 자리 인덱스와 값을 비교해서 다른 숫자들 모두 후보군으로 둔다. 후보군에서 배열에 값이 없는 숫자가 진짜 없는 숫자' 입니다. 따라서 해당 알고리즘을 위해 정답 리스트를 선언하고 배열을 정렬하고 배열을 순회하며 후보군을 찾습니다. 후보군을 찾은 뒤에는 빠른 검색을 위해 binarySearch 메소드를 사용..
알고리즘 문제 풀이 2021. 5. 9. 18:12

[Algorithm] 힙 정렬

안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입, 병합) 불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택, 퀵, 힙) 📌힙 정렬 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기본으로하는 정렬. 불안정 정렬(unstable sort)에 속하며 평균, 최선, 최악 시간 복잡도 모두 O(n log n)임. 가장 크거나 작은 값을 구할 때 유용 완전 이진 트리(complete binary tree)? 이진 트리의 한 종류로서 왼쪽 부터 차례대로 노드를 삽입하는 트리(왼쪽부터 채움, 왼쪽이 비어있는데 오른쪽이 채워져있을 수 없음) 시간복잡도 log₂n(완전 이진 트리) 과정 최대 힙을 구성 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나..
알고리즘 문제 풀이 2021. 4. 15. 21:12

[Algorithm] 퀵 정렬 / 병합(합병) 정렬

안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입, 병합) 불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택,퀵) 📌퀵 정렬 퀵 정렬은 특정한 값을 기준으로 해당 값보다 큰 숫자와 작은 숫자를 서로 교환하면서 정렬을 수행합니다. 퀵 정렬은 대표적인 분할 정복 알고리즘으로 평균적으로 선택 정렬, 버블 정렬, 삽입 정렬보다 월등히 빠르다는 특징을 가지고 있습니다. 위 세가지 정렬이 O(N2)인것에 비해 퀵 정렬은 O(N*logN)의 속도를 가지고 있기 때문입니다. 비교의 기준이 되는 특정한 값을 피봇(Pivot)이라고 부르며 보통 가장 앞에 있는 숫자를 Pivot으로 사용합니다. 작동 원리 배열을 왼쪽에서 오른쪽으로 순회하면서 Pivot 보다 큰 수를 찾습니다. 배열을 오른쪽에서 왼쪽으로 순회..
알고리즘 문제 풀이 2021. 4. 15. 18:28

[Algorithm] 선택정렬 / 버블정렬 / 삽입정렬

안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입) 불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택,퀵) 📌선택정렬 선택정렬(Selection Sort)은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다. 선택정렬(Selection Sort)와 삽입정렬(Insertion Sort)이 종종 헷갈릴 수 있는데, 선택정렬은 배열에서 해당 자리를 이미 선택하고 그 자리에 오는 값을 찾는 것이며, 삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 것입니다. - 선택정렬은 제자리 정렬(in-place sorting) 알고리즘의 하나 제자리 정렬이란, 입력 배열(정렬되지 않은 값들)..
알고리즘 문제 풀이 2021. 4. 15. 17:26

[Algorithm] 알고리즘 시간복잡도에 대하여

시간복잡도에 대해 정리하려고 합니다. (참고 블로그 : 코딩팩토리) 시간복잡도란? 시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 수 있습니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다. 특히 최근 알고리즘 문제 해결에서 대부분 실행시간을 정해놓고 그 시간안에 소스가 돌아가야 정답으로 체크하기에 시간복잡도의 중요성이 더더욱 커졌다고 볼 수 있습니다. 빅-오 표기법 시간 복잡도에는 여러 개념이 있지만 그중에서 ‘아무리 많이 걸려도 이 시간 안에는 끝날 것‘의 개념..
알고리즘 문제 풀이 2021. 4. 15. 15:42