Alien Dictionary 문제 내용 의미를 알수 없는 Alien의 Dictionary 가 alien 기준의 알파벳 오름차순 기준으로 주어진다면, alien 기준의 알파벳 순서를 사용해서 사용된 chars의 순서로 word를 만들어라 접근 방법 words = ["wrt","wrf","er","ett","rftt"] 라는 입력이 들어왔을 때, 알파벳 순서임으로 w < e e < r r < t t < f 을 추측할 수 있다. 예를 들자면 wrf보다 er이 더 작음으로 w보다 e가 알바펫 순서상으로 더 크다고 볼수 있다. 여기서 주의를 해야할 것은 wrf와 er사이에 w와 e의 관계가 성립되었다면, rf와 r 사이에 관계는 더이상 무의미 하다 2번째로 주의해야 할 것은 edge 케이스 인데, "abcd" ..

안드로이드에서 펌웨어 flashing을 하기 위해서 adb root adb shell reboot bootloader 로 android 단말을 재부팅 처리 해도 fastboot devices 로 device가 나오지 않을 때 난감하다. 이경우에는 제어판 > 컴퓨터관리 를 가서 보면 기타장치에 Android 에 노란색 느낌표로 정상 작동하고 있지 않다고 표시가 나올 경우가 있다. 이경우에는 Android Universal Driver를 업데이트 해야한다. developer.android.com/studio/run/win-usb 여기에서 driver를 다운받고 노란색으로 떠있는 안드로이드 driver를 update 처리해 줘야 한다. 여기서 android_winusb.inf를 선택해서 드라이버를 업데이트 해..

Maximum Profit in Job Scheduling 문제 내용 주어진 Job List를 이용해서 가장 높은 Profits를 계산 하시오 접근 방법 질문을 Knapsack 으로 변경해도 문제가 동일하다. 가방에 최대한 많은 양의 물건을 담고자 한다. 얼마의 무개까지 담을 수 있는가? 와 동일하다. DP를 이용한 최대 Profits를 계산하면 된다. 문제가 [starttime, endtime, profit]으로 아래와 같이 주어졌다고 생각해 보겠다. [1,3,20] [2,5,20] [3,10,100] [4,6,70] [6,9,60] 이런 문제가 있다고 했을 때 DP는 Profit을 확정짓는 endtime 기준으로 해당 시점의 최대 Profit을 유지하면 된다. 우선 endtime을 기준으로 주어진 문..

원본은 아래 링크다 www.mathelounge.de/509545/mathjax-latex-basic-tutorial-und-referenz-deutsch 웹에서 링크하는 javascript url은 다음과 같다. LaTex 스타일로 어떻게 수식 입력이 가능한지 여기에 참조를 남기고자 한다. Inline Editing \$ ... \$ \$ \sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6} \$ 글자와 함께 $ \sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6} $ 인라인 에디팅 독립적으로 한 줄을 쓰고 싶을때 \$\$ ... \$\$ \$\$ \sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6} \$\$ 글자와 별도로 $$ \s..

앞서 Segment Tree를 알아 보았다. 2021.05.02 - [Problem Solving] - Segment Tree 그런데 생각보다 개발량도 많고 필요할때 바로 만들어서 쓴다는게 쉽지 않다. 그래서 Binary Indexed Tree를 알아보고자 한다. Binary Indexed Tree는 크게 2개의 Array가 필요하다. N+1 Size의 오리지널 Array N+1 Size의 Fenwick Tree Array 오리지널 Array는 입력하고자 하는 Array 그 자체라고 생각하면된다. [1,3,5,7,9,11,13,15] 라는 배열이 있다면 이것을 Original Array = [NA,1,3,5,7,9,11,13,15] 로 유지 하는 것이다. NA가 들어가는 이유는 첫번째 Value를 1이라..

어떤 Integer가 주어졌을 경우 해당 Integer의 가장 우측에 존재하는 1의 위치를 찾고자 한다면 다음과 같이 하면 된다. N & -N 6을 예로 들어보겠다. 6의 2진수는 0000 0110 이 된다. 해당 값을 음수로 변환하면 (보수 처리 하고 마지막 1을 더하면 음수이다.) 1111 1010 이 된다. And 처리를 하면 0000 0010 이 되고 가장 우측 위치 값은 2가 된다.

Segment Tree 특정 범위의 Array 의 Sum을 빠르게 하기 위해 만들어진 기법이다. 만약 [3,5,8,1,3,9] 라고 하는 Array가 주어 졌다고 생각해 보자. 이를 Tree로 만들면 다음과 같다. 이 Tree에서 주의해서 봐야할 점은 우측에 '0' 이다. 반듯이 Tree의 Balance를 맞춰줘야 한다. 이렇게 Tree가 만들어지면 다음과 같이 Query가 가능하다. [3,5,8,1,3,9] 에서 0 ~ 5까지의 Sum은? 상기와 같이 Index 0과 5 즉 Left Index < Right Index인 관계에서 Left Index가 짝수이면 상위 노드로 올라간다. Right Index 가 홀수이면 상위 노드로 올라간다 라는 개념을 만들 수 있다. 그런데 상위 노드의 Index는 몇인가..

Create Sorted Array through Instructions 문제 내용 빈 Array nums[]가 있고 이곳에 입력할 값 Array 인 instructions가 있다고 할때 instructions Array의 왼쪽에서 오른쪽으로 nums[] Array에 값을 추가해 나간다. 단, nums[]의 Array는 정렬이 되어야 한다. 정렬을 위한 cost는 다음과 같이 정의한다. Min( 현재 있는 nums 중 insturction[i] 보다 작은 숫자의 갯수, 현재 있는 nums 중 instruction[i]보다 큰 숫자의 갯수 ) 예를 들자면 [1,2,3,4,5]의 nums가 주어졌을 때 3을 넣기 위한 최소의 cost 값은 1,2 => 2개, 4,5 => 2개 min(2,2) 임으로 cost..

Employee Free Time 문제 내용 종업원들의 스케쥴이 주어진다 모든 스케쥴을 확인한 후 모든 종업원들이 쉬는 시간을 구하라 접근 방법 모든 종업원들이 쉬는 시간, 즉 업무를 진행 하지 않는 시간을 찾으면 된다. 예를 들자면 [[[1,2],[5,6]],[[1,3]],[[4,10]]] 이라는 스케쥴이 주어졌다고 생각하자 상기의 그림처럼 `3~4`를 찾는게 문제이다. 이 그림을 보면 예상이 되겠지만, 어떤 사람별 스케쥴은 의미가 없다. 즉 모든 스케쥴을 한사람의 스케쥴이라고 생각하고 쉬는 시간을 찾으면 된다. 보이는 것처럼 단 2개의 스케쥴만 확인하고 해당 스케쥴 사이의 거리를 찾으면 되는 것이다. 그럼 어떻게 스케쥴이 겹치지 않는지 확신 할 수 있는가? 이것을 이벤트로 보면 다음과 같이 정리 할 ..