풍선 터트리기 2020 월간 코드 챌린지 9월에 나왔던 문제로 1시간 동안 시간초과로 못 푼 문제 ㅜㅜ 대회 당일 작은 값을 가진 풍선을 터트릴 수 있는 기회는 1번이라는 조건을 잘 활용하지 못했다. // 삭제하고자 하는 위치 : index //재귀 호출 내 로직 if //풍선 하나 남은 경우 그 값을 저장 else /** index - 1과 비교하여 큰 값을 제거하고 재귀 호출 --- 1 만약 작은 값을 제거 할 수 있다면 작은 값을 제거하여 재귀호출 --- 2 //위와 로직 같음 index + 1과 비교하여 비교하여 큰 값을 제거하고 재귀 호출 --- 3 만약 작은 값을 제거 할 수 있다면 작은 값을 제거하여 재귀호출 --- 4 */ 로직을 보면 최대 4개의 재귀호출을 진행하므로 log(N^4) 인 ..
애니메이션의 프레임과 비슷하게 안드로이드의 화면도 여러 개의 프레임들이 순차적으로 그려지고 완성되어 사용자에게 보이는 과정을 거칩니다. 초당 프레임 수가 많아질수록 사용자는 부드럽게 느낍니다. 그런데 이상하게 유명한 앱과 달리 자신이 만든 앱이 버벅거린다는 느낌을 받은 적이 있나요? 답은 뷰를 그리는 과정 속에서 여러분들의 불필요한 코드와 로직에 의해 하나의 프레임을 그리는 속도가 느려지게 되는 것입니다. 결과적으로 초당 프레임 수가 낮아지고 사용자는 버벅거린다는 느낌을 받게 됩니다. 이번 포스팅에서는 한 픽셀을 여러 번 그리는 오버드로에 대해서 알아보겠습니다. 문제점들 View Groub의 중첩으로 발생할 수 있는 오 버드로 LottoLike 일부분 코드입니다. 자세히 보시면 자식인 RelativeLa..
문제본문 문제해설 문제에서의 N의 범위는 100,000 이하입니다. 따라서 N^2 인 완전탐색으로는 시간초과가 발생할 수 있습니다. 분할 정복은 문제의 범위를 2이상으로 나누어 부분적으로 정복하여 푸는 방법입니다. 최대의 점수를 갖는 부분배열을 구하는 이 문제에 적용하여 중앙 값을 기준으로 3가지 경우에서 최대값을 구하면 됩니다. 1. 중앙값을 포함하는 부분 배열 이 경우는 중앙 값을 포함하는 부분 배열의 점수를 구하는 방법입니다. 히스토그램 풀이법과 유사하고 처음 중앙값하나 존재하는 배열에서 왼쪽, 또는 오른쪽으로 하나씩 요소들을 포함시키면서 최대값을 찾는 방법입니다. 왼쪽이나 오른쪽으로 이동하는 기준은 부분배열의 점수 공식을 참고하면 큰 요소를 포함하는 것이 무조건 최대 점수로 가는 길이 됩니다. 그..
문제본문 문제 해설 가능한 빨리 시작하는 강의를 우선으로 진행하고, 시작하는 시간이 같다면 끝나는 시간이 빠른 강의들을 우선적으로 강의실을 배정합니다. 위의 기준으로 입력으로 들어오는 배열을 정렬합니다. //O(nlong) Arrays.sort(room, new Comparator() { @Override public int compare(int[] o1, int[] o2) { int result = o1[0] - o2[0]; if (result != 0) return result; else return o1[1] - o2[1]; } }); 첫번째 강의가 3시에 끝나고, 두 번째 강의가 3시에 시작한다면 강의실을 새로 배정하지 않고 기존 강의실에서 수업을 진행할 수 있습니다. 따라서 정렬된 배열에 대해 ..
문제본문 들어가기 전 parametric search는 이진색의 원리를 이용해서 최적의 해를 구하는 방법입니다. 공부하기 위해 참고한 사이트에서는 이렇게 설명하기도 합니다. 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 정렬된 어떠한 리스트에서 탐색 기준을 결정해 놓고 특정 위치에서 기준에 만족하지 않는 다면 그 아래있는 위치들도 모두 기준에 통과하지 못할 것이라는 확신으로 문제를 해결하는 것입니다. O(logN + a)의 시간 복잡도를 가진 parametric search 알고리즘은 이진색과 마찬가지로 정렬된 연속적인 값들에 대해서 탐색의 범위를 1/2 씩 줄여나가며 최적의 답을 찾는 알고리즘입니다. 알고리즘의 개념이 궁금하다면 참고 링크에 더 자세히 나와있습니다. 문제 해석 탐색 범위 설정 long..
문제 본문 문제 해설 곱셈이라는 문제는 A의 수를 B번 거듭제곱하여 C로 나눈 값을 반환하는 문제입니다. 보통 N의 알고리즘인 재귀 호출로 구하는 방법이 가장 쉽지만 A, B, C의 입력 범위가 장난 아니게 큽니다. 1
나의 코드를 공유하는 것은 좋은 경험입니다. Github Repository의 Pull Request는 팀원 서로에게 코드 리뷰는 받을 때 사용할 수도 있지만, 모드는 사람의 Repository에서도 경험해 볼 수 있습니다. 예를 들면, 특정 라이브러리를 사용중인데 나는 이런 기능이 더 추가 되었으면 좋겠다! 라는 생각이 든다면 해당 기능을 구현한 후, 원본 Repository에 PR을 날리는 겁니다. 나의 기능이 반영이 될 수도, 거절이 될 수도 있지만 기능을 구현하는 과정에서 상대방이 작성한 코드를 이해하는 시간도 될 수 있고 나의 코드의 문제점 또한 객관적으로 바라볼 수 있는 경험이 되기도 합니다. 필자는 android open source를 모아놓은 유명한 Repository를 fork 한 후, ..
안녕하세요 점냥입니다:) 이번 포스팅에서는 JitPack을 사용해 Android 라이브러리를 배포해보는 방법에 대해 설명하겠습니다. 라이브러리를 배포하기 위해서는 모듈을 생성해야 하는데요. 만약 모듈에 대해 궁금하신 분들은 아래 링크를 확인해주세요. 라이브러리 생성 Step 1. JitPack 배포하기 위한 준비 Github 홈페이지 JitPack은 Github Repository의 최신 Release를 가져와서 배포하는 형식입니다. 따라서 Github 계정이 없다면 시작조차 할 수 없어요. 따라서 GIthub 계정을 미리 만드셔야 합니다. 계정이 있으시면, 자신이 개발한 라이브러리를 Github Repository에 올리시면 됩니다. 이 부분으로 인해 라이브러리의 코드를 공개하기 어려운 경우 다른 방식..
이제까지 색상별로 Drawable를 생성했었는 데 너무 비효율적이더라구요 코드상으로 color를 변경할 수 있습니다. 코드로 Drawable 속성 변경하기 val drawable : Drawable = imageview.drawable val color = ContextCompat.getColor(mContext,R.color.colorToSet) if (drawable is ShapeDrawable) { drawable.paint.color = color } else if (drawable is GradientDrawable) { drawable.setColor(color) }
