ComputerScience/Algorithm concepts (13) 썸네일형 리스트형 [Algorithm/Swift] 문자열 탐색. KMP 알고리즘 파해치기!! 부분 일치 테이블 pi 채우는 방법 요즘 문자열 알고리즘을 공부하고 있습니다. 문자열 탐색에 많이 사용되는 kmp 알고리즘에 대해서 공부한 개념을 정리하려고 합니다.ctrl + f를 통해 trans라는 단어를 찾아봤습니다. 주어진 text에서 "trans"라는 pattern을 찾았습니다. 문자열 탐색이란 주어진 text에서 특정한 단어 pattern을 찾는 것을 의미합니다. Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘이 문자열 탐색에 유명합니다. 그 전에 먼저 문자열 탐색의 가창 기초적인 방법을 설명한 후에 kmp 알고리즘을 통한 문자열 탐색 알고리즘을 소개하려고 합니다. 1. 기본적인 문자열 탐색 방법 Naive string search주어진 문장에서 특정한 문자열을 찾을 수 있는 방법이 뭐가 있을까요? 주어진 .. [Algorithm] 플로이드 와셜(Floyd-Warshall) 개념 뿌수기!! 1. What is Floyd Warshall? 플로이드 와샬 알고리즘은 '모든' 정점 사이의 최단 경로를 구할 때 사용하는 알고리즘 입니다. 한 정점->인접한 다른 정점으로 갈 때 비용을 전부 2차원 배열에 저장합니다. 모든 정점을 포문으로 탐색하게 되는데 이때 특정 한 정점일 때 해당 정점을 거쳐서 갈 수 있는 경로가 원래 2차원 배열에 저장된 경로의 비용보다 낮다면 2차원 배열의 cost를 갱신합니다. 2. Floyd Warshall's algorithm 인접 정점 간 갈 수 있는 비용을 2차원 배열 visited에 저장했다고 가정한다면 점화식은 visited[v][w] = min(visited[v][w], visited[v][k] + visited[k][w])입니다. v : 시작 정점 w : 도착.. [Swift/Algorithm] 우선순위 큐 개념 정리, 최소 힙 개념 with 라이노님 Heap 코드 리뷰 라이노님 힙 상세 리뷰(안 까먹기 위해..) + 최소 힙 개념 정리 라이노님 힙 구조 struct Heap where T: Comparable { private var heap = [T]() let compare: (T,T) -> Bool var isEmpty: Bool { return heap.isEmpty } init(compare: @escaping (T,T) -> Bool) { self.compare = compare } init() { self.init(compare: T? { guard !heap.isEmpty else { return nil } guard heap.count != 1 else { return heap.removeFirst() } let res = heap.first! heap.. [Algorithm] 그래프의 의미 및 DFS, BFS 탐색 방법 기본 개념 완전 뿌수기!!!! [Algorithm] 그래프의 탐색 DFS, BFS 탐색 그래프란 무엇인가? 그래프의 개념 그래프 표현 방법 DFS란? BFS란? DFS와 BFS 차이 그래프란 무엇인가? 일반적으로 그래프 하면 떠오르는 개념은 통계 수치를 비교할 때 사용되는 히스토그램(histogram), 방정식 같은 이미지를 떠올린다. 알고리즘에서 그래프는 어떤 현상, 사물을 정점으로 표현하고 연관된 정보를 간선을 통해 표현한다. 이 또한 그래프의 개념에 속한다. 다시 말해 정점은 주요한 대상 정보를 나타내고 간선은 정점과 정점(정보와 정보)을(를) 이어주는 관계가 된다. 즉, 데이터가 존재할 때 각 데이터를 연관 지어 시각적으로 표현한 것을 그래프라고 한다. 위 그림은 네트워크와 연관된 이미지이다. 위에서 흰색 점들은 선으로 연결되.. [알고리즘]다익스트라 최단 경로 알고리즘 개념 부수기 / heap이 뭐야? 다익스트라 최단 경로 알고리즘 정점 한개를 기준으로(=시작 정점) 다른 모든 정점을 도착하는 단일점에서의 최단 경로 알고리즘 방향 그래프, 무방향 그래프 모두 적용 간선의 가중치가 음수면 다익스트라 알고리즘을 사용할 수 없다. 가장 가까운 정점(방문x 정점)을 선택해 추가할 때, 추가된 새로운 정점에 의해 단축되는 경로가 있다면 해당 경로로 최단 경로를 수정하는 알고리즘이다. 집합 또는 vertex방문체크를 하면서 최단 경로를 구할 경우( 원래의 알고리즘 ) 시간복잡도는 O(E + V^2) == O(V^2)이다. 우선순위 큐를 활용할 경우 시간 복잡도는 O(ElogV)이다. Algorithm 1. set distance 2.시작 정점 방문 체크 3. 방문하지 않은 정점 중 시작점과 최소거리인 정점을 찾아.. [알고리즘] LIS 최장 증가 부분 수열 파해치기!! with Swift Todo : LIS 최장 증가 부분 수열 파해치기 LIS개념을 마주한 순간.. LIS(Longest Increasing Subsequence)란? dp를 통해 LIS 길이를 구하는 방법 이분 탐색을 통해 LIS길이를 구하는 방법 이분탐색 또는 dp를 활용한 문제 LIS개념을 마주한 순간.. 관련 문제 = 14002: 가장 긴 증가하는 부분수열4 ( 포스트 ) dynamic programming문제를 한참 공부 했었을 때(지금도 공부중입니다.ㅏ..) 전깃줄 문제를 풀다 LIS라는 개념을 만나게 되었습니다. 당시에 전깃줄 문제를 풀 때 모든 경우의 수를 파악해 가며 완벽히 구현했다고 생각한 코드를 구현했을 때 문제를 풀 수 없었습니다. 그리고 제가 생각한 코드로는 도저히 해결 할 수 없는 반례들이 나타났습니.. [C언어] 점화식과 점근적 분석 방법(반복대치,추정후 증명, 마스터 정리) 쉽게 배우는 알고리즘 책을 참고했습니다. 안녕하세요!! 점화식 점화식이란? 어떤 함수를 자신과 똑같은 함수를 이용해서 나타내는 것입니다. 다시말해 재귀함수의 구조를 갖는 알고리즘만!! 점화식으로 표현할 수 있다 이말입니다. 재귀함수란? F(n) = n * F(n - 1) ; // 팩토리얼 F(n) = F(n - 1) + F(n - 2) ; // 피보나치 수 F(n) = F(n/2) + C ; //데이터를 두가지로 나누는 정렬! 등.. 자기자신을 호출하는 형식을 갖는 것은 재귀함수라고 표현할 수 있습니다. F(n) = n^2 + n + 1 이런 형식은 쉽게 시간 복잡도를 구할 수 있지만, 자기 자신을 갖는 점화식일 경우에는 점화식의 점근적 분석 방법을 통해서 F(n) = F(n-1)+ ...의 형태를 F(.. [c언어/자료구조] 스택과 순차 큐의 특징, 원형 큐의 특징(삽입 삭제시 빅오 표기법) ,일상에서 큐의 사용 순차 Queue 초 1. 선입선출 FIFO 2.지정된 첫번째 원소 마지막 원소를 Front, rear를 통해 지목할 수 있습니다. -> 데이터가 들어올 경우 rear를 증가시킨 후,그 자리에 데이터가 들어갑니다. => 가장 최근에 들어간 데이터가 가장 마지막에 삭제됩니다. 3. 지정된 front, rear위치를 통해서만 삽입(rear)과 삭제(front)가 이루어집니다. 4. 큐에있는 첫 번째 원소의 이전자리는 front가 해당됩니다.(front==-1시작이므로,) 초기상태 : front==rear==-1 공백상태: front==rear 포화상태 : rear= n-1( n =마지막index) 삽입연산시 ++rear; 삭제 연산시 ++front; 삽입연산 해당위치 삭제연산 해당위치 Stack push to.. 이전 1 2 다음
