본문 바로가기

알고리즘

 (4)
[Algorithm/Swift] 문자열 탐색. KMP 알고리즘 파해치기!! 부분 일치 테이블 pi 채우는 방법 요즘 문자열 알고리즘을 공부하고 있습니다. 문자열 탐색에 많이 사용되는 kmp 알고리즘에 대해서 공부한 개념을 정리하려고 합니다.ctrl + f를 통해 trans라는 단어를 찾아봤습니다. 주어진 text에서 "trans"라는 pattern을 찾았습니다. 문자열 탐색이란 주어진 text에서 특정한 단어 pattern을 찾는 것을 의미합니다. Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘이 문자열 탐색에 유명합니다. 그 전에 먼저 문자열 탐색의 가창 기초적인 방법을 설명한 후에 kmp 알고리즘을 통한 문자열 탐색 알고리즘을 소개하려고 합니다. 1. 기본적인 문자열 탐색 방법 Naive string search주어진 문장에서 특정한 문자열을 찾을 수 있는 방법이 뭐가 있을까요? 주어진 ..
[백준/Swift] 2470 : 두 용액 문제 뿌수기!! BOJ_2470.swift 2470 : 두 용액/ 문제 소개 풀이 과정 코드 구현 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 2470 : 두 용액 / 문제 소개 간단하게 문제를 소개하자면 연구소에는 많은 산성 용액과 알칼리성 용액을 보유하고 있는데 용액별로 특성값이 존재합니다. 산성 용액 특성값의 경우 1 ~ 1,000,000,000 알칼리성 용액 특성값의 경우 -1,000,000,000 ~ -1 로 존재..
[백준/Swift] 7562 : 나이트의 이동 여러분 안녕하세요 최근에 dfs&bfs 문제에 빠져서 계속 풀다가 시험기간이라.. 3주간 공부를 못해서 복습할 겸 풀어봤습니다. https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 간단한 문제 설명부터 시작하겠습니다!! 체스판 크기가 주어져야 하고, 그위에 처음 나이트 위치가 주어집니다. 나이트가 이동할 수 있는 칸은 가운데 점을 시작점으로 총 8번 움직일 수 있습니다! (튜플로 쉽게 ㅎㅎ,,) let direction =[(1번 칸 좌표),(2번 ..
[C언어]알고리즘 (Time Complexity)시간 복잡도와 빅오 표기법 우선, Algorithm 알고리즘 이란? 어떤 문제를 해결하고자, 구현하고자 하기 전에, 문제의 해결을 위한 절차 또는 단계를 명시적이고, 논리적으로 표현한 것을 알고리즘이라고 합니다. (추상적으로 표현된 알고리즘은 특정한 프로그래밍 언어로만 작성된 것이 아니기에 다른 언어를 사용하는 프로그래머들이 자신이 알고있는 언어를 통해 알고리즘의 해답을 구현할 수 있습니다.) 문제를 해결하기 위한 방안으로 여러 알고리즘이 있을 것인데,, 이중에서 가장 좋은 알고리즘. 효율적인 알고리즘을 판별하기 위한 대표적인 알고리즘의 성능 분석 방법은 시간복잡도와 공간복잡도입니다. 시간 복잡도 알고리즘을 프로그램으로 수행되는데(실행->완료시점)까지 사용된 총 저장공간을 분석하는 방법은 공간복잡도이고, 알고리즘이 수행되는데 실행..

티스토리툴바