1. KMP(Knuth-Morris-Pratt Alogorithm) 알고리즘이란?흔히 발견자 Knuth, Morris, Pratt의 앞글자를 딴 KMP로 읽히는 이 알고리즘은 전체 문자열에서 특정 문자열을 찾는 방식으로 오토마타(Finite-state automaton based search) 알고리즘과 비슷한 형식을 가지나 메모리와 시간 양측에서 모두 이득을 볼 수 있어 문자열 검색 알고리즘에서 브루트포스 외에 흔히 사용되는 알고리즘이다. 시간복잡도는 O(N + M)이다. 2. 구현 방식예를 들어, "ABABABCD" 라는 문자열과 "ABABC"라는 패턴이 존재할 때 KMP 알고리즘으로 문자열을 검색하면 다음과 같은 방식으로 이루어진다. ABABABCDABABC           ABABABCD  AB..

정렬 알고리즘이란? 말그대로 정렬을 위한 것으로, 정렬은 일종의 조건에 맞게 요소들을 나열하는 것을 의미한다. 이 정렬 알고리즘은 종류가 다양한데 대표적인 것들을 하나씩 짧게 알아보도록 하자. 1. 선택 정렬(Selection Sort) 선택정렬 알고리즘은 앞 인덱스부터 시작하여 마지막 인덱스까지 값을 확인하며 최솟값을 비교하는 방식이다. 마지막에 도착했을때 최솟값을 앞 인덱스에 넣어 앞 쪽부터 정렬되도록 만든다. 시간복잡도는 O(n ^ 2)이다. var min_idx = 0 for (i in 0..arr.lastIndex-1) { min_idx = i for (j in i+1..arr.lastIndex) { if (arr[min_idx] > arr[j]) min_idx = j } val term = a..

1. 라빈 카프 알고리즘이란?특이한 문자열 매칭 알고리즘으로, 항상 빠르진 않으나 일반적인 경우 빠르게 작동하는 간단한 문자열 매칭 알고리즘이다. 해시(Hash) 기법을 사용하는데, 이 해시란 일반적으로 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸는 기법이다. 상징하는 데이터로 바꾸어 처리한다는 점에서 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다는 장점이 존재한다. 단순히 문자열을 비교하는 Native Search의 경우, 시간 복잡도가 O(NM)이 발생하나, 라빈 카프 알고리즘을 사용하면 평균적으로 O(N)으로 시간 복잡도를 단축시킬 수 있다. 2. 구현방식우선, 해시 계산법은 다음과 같다.문자열 AACBDDABC에서 패턴 ACB가 발견되는지를 라빈카프 알고리즘을 통해 탐색한다. 검색 ..

DIP(Dependency Inversion Principle)의 줄임말로 의존 역전 원칙이라는 뜻이다.이 원칙은 고수준 모듈이 저수준 모듈에 의존하는 것이 아닌, 저수준 모듈이 고수준 모듈에 의존하게 해야한다는 것이다.고수준 모듈이란, 어떠한 의미 있는 단일 기능을 제공하는 모듈이다.저수준 모듈이란, 고수준 모듈의 기능을 구현하기 위해 필요한 기능들을 구현한 모듈이다. 이 DIP 원칙을 다시 말하자면, 사용자가 상속 관계로 이뤄진 모듈을 사용할 때 하위 모듈을 직접 인스턴스하여 쓰지 말라는 것이다. 이 경우 사용자는 하위 모듈을 사용하는 것 기준으로 짜여져있기 때문에 하위 모듈의 내용에 변화가 생길 경우 사용자의 코드나 상위 모듈의 코드를 수정하게 되기 때문이다. 그래서 여러 코드들을 보면 사용자가 접..

객체지향 프로그래밍 (Object-Oriented Programming)은 프로그램 설계방법론의 일종으로, 명령형 프로그래밍에 속한다. 프로그램을 객체 단위로 나누어 상호작용을 서술하는 방식이다. 다음과 같은 예시가 있다고 가정하자fun main() { Cloth("헤비웨이트 반팔 티셔츠", "이너 웨어", "L").description() OuterWear("오버핏 가디건", "아우터 웨어", "XL", 34500, "가디건").also { it.description() it.price() } output(Cloth("헤비웨이트 반팔 티셔츠", "이너 웨어", "L")) output(OuterWear("오버핏 가디건", "아우터 웨어", "XL", 3..

테스트 중인 대쉬보드앱의 플로우는 다음과 같다. 로고 스플래쉬 UI 로그인 UI 회원가입 UI 메인 UI 프로필 UI 로그인 시스템을 Firebase Auth를 사용해 구현하였다. 물론 Firebase Auth- Google Cloud를 사용해 유저 정보를 관리하는 것은 Google에 매우 의존적이므로 기업이 사용하기엔 좋지 못한 점이 많으리라 생각되지만 개인이 테스트용, 가볍게 다룰 프로젝트에 적합하다고 생각했기에 이를 통해 구현하였다. Firebase & Auth - Androidstudio에 관하여선 인터넷에 많은 자료들이 존재하기 때문에 넘어가겠다. https://firebase.google.com/docs/auth/android/google-signin?hl=ko Android에서 Google로..

이전글 : https://small-stepping.tistory.com/603 날씨 앱 기록 02 이전글 : https://small-stepping.tistory.com/596 날씨 앱 기록 01 https://small-stepping.tistory.com/586 다시 개발 중... 다시 앱쪽을 만질 때가 됐다, 더 손 놓고 있으면 기억 하나도 안나겠다 싶어서 기초를 다시 잡 small-stepping.tistory.com 중간에 절취선처럼 잘리는 건 캡처 문제다. 스크롤 캡처를 하니 저렇게 화면이 이상하게 나온다. 신기하게도 글을 작성하는 23.10.20 오후 9시 20분경 중기 예보 데이터가 이상하다. 앱 자체 에러가 아니라 기상청 api 들어가서 제대로 데이터 하나하나 수기로 넣어봐도 데이터가..

1. 트라이 자료구조란? 문자열의 집합을 표현하는 트리 자료구조. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색들은 원소를 찾는데 O(logN)의 시간이 걸린다. 문자열의 길이가 길수록 더욱 오래 걸리게 되고, 원하는 문자열을 찾는데 O(MlogN)의 시간이 걸리게 될 것이다. 이는 반복수행하게 된다면 더더욱 오래 걸리게 된다. 이를 해결한 것이 문자열 특화 자료구조, 트라이(Trie)이다. 문자열을 빠르게 탐색할 수 있는 자료구조 트라이 자료구조의 시간복잡도는 다음과 같다. 제일 긴 문자열을 L, 총 문자열의 수를 M이라고 할 때 생성시 시간 복잡도는 O(M*L)이다. 탐색시 시간복잡도는 O(L)이다. 2. 작동 원리 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다..

이전글 : https://small-stepping.tistory.com/596 날씨 앱 기록 01 https://small-stepping.tistory.com/586 다시 개발 중... 다시 앱쪽을 만질 때가 됐다, 더 손 놓고 있으면 기억 하나도 안나겠다 싶어서 기초를 다시 잡고자 간단하게 포트폴리오, 튜토리얼 강좌 등으로 많 small-stepping.tistory.com 다음글 : https://small-stepping.tistory.com/610 날씨 앱 기록 03 이전글 : https://small-stepping.tistory.com/603 날씨 앱 기록 02 이전글 : https://small-stepping.tistory.com/596 날씨 앱 기록 01 https://small-st..