그래프 vs 트리 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드 없음 루트 노드 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 그래프의 구현 방법 1) 인접 행렬 : 2차원 배열을 이용하는 방식 노드 개수 V, 간선 개수 E인 그래프에서 인접 행렬을 이용할 때는 간선 정보를 저장하기 위해 O(V2)만큼의 메모리 공간이 필요하다. 또한, 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있다. ex : 플로이드 워셜 알고리즘 2) 인접 리스트 : 리스트를 사용하는 방식 노드 개수 V, 간선 개수 E인 그래프에서 인접..
전체 글
최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 ('길 찾기' 문제) 다양한 유형에 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 '음의 간선(0보다 작은 값을 가지는 간선)'이 없을 때 정상적으로 동작한다. 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘 으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘 -> 기본적으로 그리디 알고리즘으로 분류 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복 원리 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을..
다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 조건) 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션 기법 (캐싱) 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 # 피보나치 수열 소스코드 - 메모이제이션의 예 [탑다운] # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x ==..
ANR (Activity Not Response) 액티비티가 응답하지 않는 오류 상황 액티비티를 작성할 때 ANR을 고려하지 않으면 앱이 수시로 종료될 수 있다 액티비티로 구성한 앱화면은 사용자 이벤트에 빠르게 반응해야 한다. 그런데 액티비티가 사용자 이벤트에 5초 이내에 반응하지 않으면 ANR 오류가 발생한다. 시스템에서 액티비티를 수행하는 수행 흐름을 메인 스레드 또는 UI 스레드라고 한다. 메인 스레드가 오래 걸리는 작업을 실행한다고 해서 그 자체로 오류가 발생하지는 않는다. 아무리 오래 걸려도 사용자가 액티비티 화면을 터치하지 않는 등 이벤트가 없다면 오류가 발생하지 않는다. 그러나 사용자가 언제 화면을 터치할 지 모르므로 액티비티를 작성할 때는 항상 ANR 오류를 고려해야 한다. 액티비티에서 시..
생명주기 Life Cycle 액티비티가 생성되어 소멸하기까지의 과정 onCreate() - 전체 수명주기 동안 한번만 발생해야 하는 기본 애플리케이션 시작 로직 실행 (초기화, viewModel 연결 등) - savedInstanceState 매개변수를 수신하는 단계 onStart() - 이 시점부터 사용자가 Activity를 볼 수 있음 onResume() - 앱이 사용자와 상호작용하는 단계. 어떤 이벤트가 발생하여 앱에서 포커스가 떠날 때까지 앱이 이 상태에 머무름 - 활동이 onPause()에서 onResume() 상태로 돌아오면 시스템이 onResume() 메소드를 다시 한 번 호출 - 활동이 onResume() 상태로 전환될 때마다 필요한 다른 초기화 작업도 수행 onPause() - 다른 Ac..
인텐트란? 컴포넌트를 실행하려고 시스템에 전달하는 메시지 기능을 수행하는 함수를 제공하는 클래스가 아니라 데이터를 담는 클래스 이 때, 데이터는 컴포넌트를 실행하는 정보이며 이 정보가 담긴 인텐트 객체를 시스템에 전달하면 컴포넌트가 실행된다 * 액티비티는 매니페스트 파일에 등록해야 한다. 액티비티 클래스 하나당 태그 하나로 등록해야 하며, name 속성은 생략 불가능하다. * 액티비티뿐만 아니라 서비스, 브로드캐스트 리시버, 콘텐츠 프로바이더도 매니페이스 파일에 등록해야 한다. 그 이유는 시스템에 컴포넌트를 알려야 하기 때문이다. 시스템은 런타임 때 매니페스트 파일의 정보를 참조하여 앱을 실행한다. val intent: Intent = Intent(this, DetailActivity::class.jav..
안드로이드 리눅스 커널을 기반으로 구글에서 제작한 모바일 운영체제 안드로이드의 특징 - 안드로이드는 공개 운영체제인 리눅스를 기본으로 한다 - 안드로이드 앱은 자바나 코틀린 언어를 이용해 개발한다 - 안드로이드 운영체제의 주요 부분과 라이브러리, 구글에서 만든 앱 등의 코드는 대부분 공개되어 있다 - 안드로이드 스마트폰은 구글뿐 아니라 여러 제조업체에서 만들 수 있다 - 안드로이드 앱은 구글의 플레이 스토어뿐만 아니라 다양한 방법으로 사용자에게 배포할 수 있다 - 안드로이드 플랫폼에서는 모든 응용 프로그램이 평등하다는 사상을 바탕으로, 모바일에 기본으로 탑재된 앱과 개발자가 만든 앱이 똑같은 환경에서 똑같은 API를 이용한다 안드로이드 운영체제의 구조 리눅스 커널(Linux Kernel) 안드로이드는 리..
이진탐색 : 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 찾는 과정 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서 수행된다. # 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): ..