KMP 알고리즘 정의KMP(커누스 모리스 프랫 3명의 사람이 같이 만들어서 KMP)알고리즘이며 불필요한 비교 즉, 어차피 틀릴걸 아는 부분은 건너뛰어버리는 원리를 이용하는 대표적인 문자열 매칭 알고리즘이다. 문자열 매칭이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾아내는 것을 의미한다. 쉽게 말하면 우리가 브라우저에서 ctrl+f를 통해 찾고자하는 문자열을 검색하는 행위라고 생각하면 된다. 과정1. 패턴 내 접두사 , 접미사를 활용하자.kmp 알고리즘의 핵심은 패턴의 접두사와 접미사 개념을 적극 활용하여 '반복되는 연산을 얼만큼 건너뛸 수 있는 지'에 대해 집중한다는 것이다. 패턴 내에 존재하는 접두사와 접미사가 '일치' 한다면 접미사를 접두사로 다시 바라봄으로써 문자열 탐색을 이어서 진행할..

캐시캐시란 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 저장소이다.갑자기 iOS에서 이 개념이 왜 나올까 ??  부스트 캠프 과정 중 앱 개발을 할 때 항상 비용을 고려해야한다. 비용은 크게 2가지로 나눠진다비용 Money전원 Power전원 Power는 말 그대로 우리 서비스를 이용할 때 배터리 소모량이 된다. 비용 Money은 우리 서비스를 이용하면서 유저가 지불해야하는 금액적인 비용이다. 금액적인 비용은 우리 서비스내의 제품을 구매할 때도 역시 필요하지만앱이 네트워크가 필요하여 인터넷 비용도 있다.  우리가 컨트롤 할 수 있는 것은 바로 인터넷 비용이다.우리는 유저의 인터넷비용을 최대한 기술적으로 절감시켜 유저 이탈 수를 막야한다. 대표적인 예로 바로 캐시 데이터를 통해 불필요한 네트워크 통..

문제https://leetcode.com/problems/palindromic-substrings/description/ 입력s: String = 문자열 1 결과ans: Int = s의 부분 문자열에서 찾을 수 있는 모든 회문 개수해석회문이란 중심을 기준으로 대칭되는 문자열이다.  크게 두가지 종류가 있다.  홀수 문자열 회문abcba 중심을 기준으로 정확히 대칭왼쪽 포인터와 오른쪽 포인터가 c를 기준으로 출발하면 됨 짝수 문자열 회문abccba중심이 딱 보이지는 않음왼쪽 포인터는 2번 index , 오른쪽 포인터는 3번인덱스를 기준으로 출발하면 됨즉 중심이 2개 그렇기 때문에 중심을 하나씩 움직이며 각 기준의 홀수 회문과 짝수 회문을 모두 더해가면 s의 부부 문자열의 모든 회문을 찾을 수 있다.  코드..

문제https://leetcode.com/problems/repeated-substring-pattern/description/입력s: String = 문자1 결과ans: Bool = 반복 문자열 패턴인지 true / false해석 일단 s.count 가 2보다 작으면 반복 문자열이 될 수 없으므로 false를 리턴  1) 2s = s를 이어 붙힌 것2) 2s에서  앞과 뒤를 제거한다. 3) 이후 문자열에서 s를 찾을 수 있다면 반복가능한 문자열이다. 앞과 뒤를 제거한 이유는 원형 수열과 같이 연결해주기 위해서이다. s = abaaba 라고 가정하고 위 과정을 진행해보자. 2s 만들기  2s = abaaba abaaba앞뒤 제거최종 문자열 = baabaabaab문자열 찾기 baabaabaab  길이 3..

문제https://www.acmicpc.net/problem/11724 입력n: Int = 정점의 개수m: Int = 간선의 개수u: 간선의 정점1v: 간선의 점점21 결과ans: Int = 그래프에 존재하는 연결 컴포넌트 개수해석제공된 간선 정보를 이용해서 인접 행렬을 채운다.이후 dfs를 통해 방문여부를 갱신하여 중복하여 방문하는 문제를 해결한다.코드import Foundationlet nm = readLine()!.split{$0 == " "}.map{Int($0)!}let (n, m) = (nm[0], nm[1])var adj: [[Int]] = [[Int]](repeating: [], count: n+1)for _ in 0..

문제https://www.acmicpc.net/problem/2667입력n = 지도의 크기 (가로 세로 크기)board: [[Character]] = [] , "0"과 "1"로 구성됨 board[i] = "0" = 집이 없는 곳board[i] = "1" = 집이 있는 곳5결과ans: Int = 단지 수 단진 내 집의 수를 오름차순으로 정렬 후 한줄 씩 출력해석2중 반복문을 돌며 집이 존재하고, 아직 방문한 적이 없다면 새로운 단지 이 때 dfs로 들어가면서 연결된 모든 집을 하나의 단지로 인식하고 방문하며 count하자. 코드import Foundationlet n = Int(readLine()!)!var board: [[Character]] = []for _ in 0.. Int { visited[..