반응형 개발48 DFS, BFS 스터디용 DFS, BFS 정리 DFS, BFS는 그래프에 속하는 알고리즘이다. 코딩테스트에서 경로를 찾는 문제에서 많이 출제가 된다. DFS Root Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack 혹은 재귀함수(Recursion)으로 구현된다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) Java Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 .. 2021. 2. 5. 트라이(Trie)알고리즘 트라이(Trie) 트라이란 문자열 검색을 빠르게 할 수 있는 알고리즘이다. 예를 들어 영어사전이 있을 때 특정 단어가 있는 지 빠르게 찾을 수 있다. 문자열을 특정 키값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있다. 불완전한 해시 테이블의 최악의 검색속도는 모든 데이터를 다 확인하는 것으로 O(N)이지만 트라이를 사용하게 되면 문자열 길이 만큼의 O(M)의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있다. 보통 트라이 알고리즘을 사용할 때 고려해야할 점이 단어의 길이, 그리고 파생되는 노드 child개수다. 위에 영어사전으로 예를 들었는데 영어는 알파벳이 26가지로 child 노드는 26개를 갖고 있을 수 있다. 전화번호 목록같은 경우도 0부터 9가지.. 2020. 4. 7. ANR 로그 분석 방법 - /data/anr/traces.txt ANR 로그 분석 방법 - /data/anr/traces.txt 1. ANR이란?Application Not Responding (ANR)의 줄임말로 어플리케이션이 일정시간 동안 응답이 없을 경우 발생하는 현상을 말합니다.무한루프가 돌거나 UI 쓰레드에서 오래 걸리는 작업을 할 경우 발생하는 다이얼로그가 바로 ANR dialog입니다.ANR이 발생하면 안드로이드 파일 시스템에 data/anr/ 위치에 traces.txt라는 ANR발생 시점의 프로세스 상태에 관한 로그가 기록됩니다.이건 모든 안드로이드 폰 공통이지만 안타깝게도 루트권한에서만 접근이 가능합니다.보통은 synchronized가 걸려서 독점하고 있거나 혹은 생각없이 sleep을 처리해서 발생할 가능성이 큽니다.traces.txt에 held by.. 2018. 10. 15. 윈도우에서 Battery Historian 사용 윈도우에서 Battery Historian 사용해보기.롤리팝 이상부터 지원하는 앱 전력소모 분석툴인 Battery Historian 설치법에 대해 간략히 정리합니다. 뭐 다운 사이트에 설명이 잘 되어 있긴 한데 리눅스 기반으로 설명되어 있어서 경로가 조금 틀려서 (Ctrl+C,V가 그냥 안되서) 제 컴에 맞게 여기에 정리해봅니다. 이전버전은 그냥 파이썬으로 만들었는데 2.0부터는 Golang+Python으로 만들어져있더군요. 1. Golang을 설치한다 (https://golang.org/doc/install) 속편하게 설치파일(MSI) 방식으로 받으셔서 설치하세요. 2. Golang 설정을 한다. 그냥 설치파일로 설치하면 GOROOT랑 PATH만 설정됩니다.환경변수란에 GOPATH를 지정해줘야 합니다... 2018. 10. 12. GPS용어 해설 GPS 용어 해설AlmanacGPS 위성의 항법 메시지에 포함되어 있는 일련의 변수묶음으로, 수신기가 위성들의 대략 적인 위치를 계산하는 데에 쓰인다. 여기에는 모든 GPS 위성의 위치에 대한 정보가 들어있음Ambiguity임의의 Cycle수로 관측된 반송파 위상의 초기 Bias. 초기의 위상 관측치는 GPS 수신기가 GPS 신호를 처음 잡았을 때 만들어지는데, 이때 위성과 수신기간에 정확한 cycle수를 알 수가 없으므로 cycle정수에 대한 모호성분이 생긴다. 수신기가 위성의 신호를 잡고 있는 동안 상수로 유지되는 이 모호성분은 반송파 위상자료처리를 할 때 만들어진다. 위성과 수신점간의 거리를 반송파의 수신 장치로 측정한 결과에 포함되는 파장의 정수배의 오차AS(Antispoofing)P 코드를 암호.. 2016. 4. 21. Android app의 memory 사용량 확인 Java에서는 명시적으로 Heap을 할당하고 해제하는 과정이 없지만, 그렇다고 해서 Memory를 아무런 제한 없이 사용할 수 있는 것은 아니다. 특히 제한된 RAM에서 동작하는 Android app을 작성할 때는 이 부분을 신경 써야 한다. 할당된 Heap 이상으로 Memory 할당을 하게 되면, Garbage collection이 일어나는데, App이 잠시 멈추는 현상이 발생한다. adb tool을 사용해서 다음과 같이, 전체 Package의 Memory 사용량을 확인할 수 있다.adb shell dumpsys meminfoApplications Memory Usage (kB): Uptime: 16492740 Realtime: 29717020 Total PSS by process: 108110 kB:.. 2016. 4. 5. 이전 1 2 3 4 5 6 7 8 다음 반응형
