전체 글 37 썸네일형 리스트형 Divide and Conquer Algorithm Design Pattern에 대해서 기본적으로 문제를 해결 가능할 적도로 작은 부분들로 나누어 각각을 공략하여 결국은 최초의 문제를 해결한다는 방법이다. 기본적으로 recursive한 패턴이 알고리즘 설계에 편하지만 경우에 따라 call stack overflow를 초래할 수 있으므로 interative한 패턴도 생각해 두는 것이 좋다. 예시를 보면서 패턴에 대해서 이해해보자. 아주 큰 정수 2개를 곱하는 연산을 하는 알고리즘을 만들어보도록 하자. 먼저 23 * 14를 다음과 같이 표현해보자. 23=2∗101+3∗100 14=1∗101+4∗100 23∗14=[2∗101+3∗100]∗[1∗101+4∗100] =[2∗1]∗102+[2∗4+1∗3]∗101+[3∗4]∗100 그리고 2*1과 3*4란 곱하기 연산의.. Greedy Algorithm에 대해서 Greedy 알고리즘 디자인 패턴은 최적의 해결책을 얻을 때까지 일련의 행동을 따르며 각 순간 가장 최적의 해답을 찾음으로써 최적의 해에 근사하는 알고리즘이다. MST [minimum spanning tree] 문제 해결 알고리즘 Prim Greedy Algorithm을 보자. 공집합 F, Y를 준비한다. MST를 찾으려고 하는 그래프 G [V, E]에서 vertex 하나를 집합 Y의 원소로 한다. 집합 X = V - Y의 vertex들에서 Y의 원소들과 연결된 것 중 edge weight가 가장 낮은 것을 선택한다. 해당 vertex를 Y원소로 한다. 그리고 해당 edge를 F의 원소로 한다. 2, 3, 4번을 Y = V가 될때까지 반복한다. MST G[Y, F]를 구한다. 처음 선택한 vertex에 .. [Android] Composable과 suspend의 유사성 코트린 suspend method는 suspend method 안에서 부를 수 있다. 이는 코틀린 코드를 자바 코드로 바꾸어 보면 이유를 유추해 볼 수 있다. suspend fun a { b } suspend fun b { } 위 코드를 자바 코드로 바꾸어 보면 @Nullable public static final Object a@NotNull Continuation $completion { Object var10000 = b$completion; return var10000 == IntrinsicsKt.getCOROUTINE_SUSPENDED ? var10000 : Unit.INSTANCE; } @Nullable public static final Object b(@NotNull .. [Android] Java Native Interface[JNI] - local reference table overflow error 알고리즘 연산의 성능 개선을 위하여 JNI를 사용하는 중에 문제가 발생했다. extern "C" JNIEXPORT void JNICALL operate JNIEnv* env, jobject thiz, jobject nodes, jobject edges { jobject* ithNode = jobject* malloc4; whileop { for jint i = 0; i CallObjectMethod(nodes, java_util_ArrayList_get, i; /** 생략 */ } } 내가 사용한 코드를 대략적으로 나타낸 모습이다. ArrayList type의 nodes를 함수의 파라미터로 받고 있고 for문 내에서 리스트를.. [Kotlin] 코틀린 Property[backing property, backing field] 자바 클래스에서 필드를 생성하고 getter와 setter를 사용하여 외부에서 값을 가져오거나 변경할때 사용하였다. 코틀린에서 말하는 property는 자바에서의 필드, getter, setter를 모두 묶어 있는 것을 말한다. 자바에서 필드를 생성하는 것과 같은 방법으로 프로퍼티를 만들게 되지만 코틀린에서 자동으로 기본 getter, setter를 생성해 준다. class A { var a: Int = 0 } 위 코틀린 클래스를 자바 클래스로 변경해 주면 다음과 같은 결과를 확인할 수 있다. public final class A { private int a; public final int getA { return this.a; } public final void setAint var1 { thi.. [Android] Visualize Sorting Algorithm App - jetpack compose[2][Tim Sort] 위키피디아에 있는 정렬알고리즘을 비교한 표에서 일부를 확인해 보겠다. 위의 자료에서 여러 정렬 알고리즘의 시간복잡도를 확인할 수 있다. 마치 큰 수의 법칙처럼 정렬하고자 하는 배열의 크기가 충분히 크면 시간복잡도의 비교로 실제 정렬 시간을 비교할 수 있겠다. 하지만 주사위를 6번 던졌을 때 각 숫자가 한 번씩 나오지 않을 경우가 있는 것처럼 표본의 크기가 작을때는 얘기가 다를 수 있다. 예를 들어 Insertion sort를 보자. 해당 알고리즘의 평균 시간 복잡도는 O=n^2로 평균 시간 복잡도가 O=n*logn인 Quick sort보다 크다. 하지만 시간 복잡도가 n^2라는 것은 실제 값은 C_i*n^2+R_i이며, n*logn라는 것은 C_q*n*logn+R_q이다. 즉, n이.. [Android] Visualize Sorting Algorithm App - jetpack compose[1] 어느 때와 같이 구현되어 있는 sorting method를 사용하다가 갑작스럽게 내가 사용하고 있는 정렬알고리즘이 뭔지 궁금해졌다. 오잉? 처음 보는 녀석이 있네? 그래서 다른 정렬 알고리즘을 처음 봤을 때처럼 정렬 알고리즘을 시각화 한 유튜브https://youtu.be/kPRA0W1kECg?si=0FDdt9e72b3w3YVc를 봤다. 코드만 보는 것보다 이렇게 과정을 시각화해준 것과 함께 보는 것을 좋아하기 때문에 역시 좋다. 여기서 갑자기 안드로이드 어플리케이션으로 나만의 것을 한번 만들어 보자는 생각이 들었다. 일단 안드로이드 프로젝트를 만들고 라이브러리 추가를 해주었다. dependencies { implementation("androidx.lifecycle:lifecycle-viewmodel-.. SOLID - OOP design principle[5] - DIP In object-oriented design, the dependency inversion principle is a specific methodology for loosely coupled software modules. When following this principle, the conventional dependency relationships established from high-level, policy-setting modules to low-level, dependency modules are reversed, thus rendering high-level modules independent of the low-level module implementation details. Depend.. 이전 1 2 3 4 5 다음 목록 더보기
