목록전체 글 (327)

오늘도 더 나은 코드를 작성하였습니까?

Algorithm(알고리즘) 기본 정렬(sort) 정리 feat. kotlin

1. selection sort(선택정렬) /* 선택 정렬. 가장 작은것 선택하여 앞으로 이동 시킨다. 직관적이고, 구현이 쉽다. 비효율적이다. 시간복잡도 O(N^2) */ val arr = intArrayOf(1, 10, 5, 3, 2, 4, 7, 9, 8, 6) fun swap(a: Int, b: Int) { val temp = arr[a] arr[a] = arr[b] arr[b] = temp } fun selectionSort() { for (i in 0 until arr.size) { var selectedIdx = i for (j in i until arr.size) { if (arr[selectedIdx] > arr[j]) { selectedIdx = j } } swap(i, selectedI..
Algorithm/개념 2023. 8. 17. 02:05
Algorithm(알고리즘) 기본 수학(조합, 순열, 소수 등) 정리 feat. kotlin

1. 조합(★★★★★) 정의 - 서로 다른 n개의 원소가 모인 집합에서 r개로 이루어진 집합을 뽑는 경우의 수 컴퓨터의 데이터를 다룰때 기본적으로 자료구조(배열, 리스트...등) 데이터를 담아서 조합을 이용한다. 즉, 그래서 index를 선택함으로 구현한다. 완전탐색 문제에서 자주 사용된다. * n C r = n C n-r 구현 r이 3이하인 경우 반복문으로 구현. fun main() { val arr = Array(4){ it } // n = arr.size r = 3 일때 for (i in 0 until arr.size){ for (j in i+1 until arr.size){ for (k in j+1 until arr.size){ println("i:$i j:$j k:$k") } } } } r이 4..
Algorithm/개념 2023. 8. 16. 18:50
펜윅트리 (Binary Index Tree) feat. kotlin

Fenwick 트리 또는 BIT(Binary Indexed Tree)는 요소를 "효율적으로 update"하고, 숫자 테이블에서 "prefix sum"을 계산할 수 있는 데이터 구조입니다. 구조는 1989년에 Boris Ryabko가 제안했으며, 1992년에 추가 수정본이 발표되었습니다. 이후 그의 1994년 기사에서 이 구조를 설명한 Peter Fenwick의 이름을 따서 Fenwick 트리라는 이름으로 알려지게 되었습니다. *이진법 비트연산 성질을 이용한다. 컴퓨터에서 정수를 저장하기위 사용되는 타입은 Int입니다. int 자료형은 4byte(32bit)이다. 정수 15는 00000000 00000000 00000000 00001111 정수 -15는 *2의 보수( ~15 + 1) 11111111 111..
자료구조 2023. 7. 3. 17:04
세그먼트 트리(Segment Tree) feat. kotlin

CS에서 statistic tree라고도 하는 세그먼트 트리는 간격 또는 세그먼트에 대한 정보를 저장하는 데 사용되는 트리 데이터 구조입니다. 주어진 포인트를 포함하는 저장된 세그먼트에 대해서 쿼리할 수 있습니다. n개의 원소에 대하여 구성된 세그먼트 트리는트리를 생성하는 비용은 O(n)이다. 원소를 update 하는데 O(log n)의 시간 복잡도가 필요하고, 쿼리 또한 O(log n)의 시간 복잡도가 요구된다. 1. 초기화 1차원 배열을 통해 구현한다. * 0번째 idx는 사용하지 않는다. 원본 배열의 Size의 2배 크기의 배열을 Tree로 사용한다. * 크기를 2배로 잡는 이유는 원본 배열로 세그먼트 트리의 리프 노드를 구성하게 되면, 세그먼트 트리가 2진트리이기 때문에 (리프 노드 개수/ 2)면..
자료구조 2023. 7. 2. 17:50
이전 Prev 1 ··· 13 14 15 16 17 18 19 ··· 82 Next 다음