본문 바로가기

algorithm

 (35)
프로그래머스 레벨 1 ALL SOLVED, 오답정리 요약 1. 문자열 선언할 때 오타 ex) string arr[10] = {"zer","one", "two", "thr", "fou", "fiv", "six", "sen", "eig", "nin"}; 2. string 띄어쓰기 단위로 분류 https://chbuljumeok1997.tistory.com/42 3. 시간복잡도, 공간복잡도 계산 4. 전체적인 구성 생각 후 코딩 5. 중간 중간 생각대로 코딩됐는지 cout 등으로 찍어보기 6. 중간 계산값이 int형 범위를 넘는 경우 7. 문자열 변환 실수 ex) int n = 12; (char)(n +'0') 8. 테스트 케이스 추가하기 ex) 답이 없을 경우, 최솟값, 최댓값, 전부 같은 경우, 전부 다른 경우, 전부 답인 경우, 전부 답이 아닌 경우 한 ..
프로그래머스 사이트 캐시 문제 왜맞? 프로그래머스 완주하지 못한 선수(레벨 1) : https://programmers.co.kr/learn/courses/30/lessons/42576?language=cpp 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr //https://programmers.co.kr/learn/courses/30/lessons/42576 #include #include #include using namespace std; string solution(vector participant, vector..
다이나믹 프로그래밍[Dynamic Programming] 문제풀이-2 (10문제) 11048 이동하기 https://www.acmicpc.net/problem/11048 문제의 특징 1. 시작-> 도착 2. 이동방향 3가지 3. 양의 정수 이동할수록 문제의 크기가 작아진다. 위나, 왼쪽으로 이동 못하므로 -> 항상 문제가 작아지므로 다이나믹 프로그래밍이라고 알 수 있다. 풀이 1 O(NM) = NxMx1 D[i][j] = (i, j)로 이동할 때 가져올 수 있는 최대 사탕 개수 D[i][j] = Max(D[i-1][j-1], D[i][j-1], D[i-1][j]) + maps[i][j]; for(int y=1; y> w; for (int i = 1; i maps[i][j]; for (int y = 1; y w) return 0; if (dist[y][x] >= 0) return dis..
string 정리 보호되어 있는 글입니다.
문자열 매칭 알고리즘[3](트라이 & 아호 코라식)[String Searching Algorithm, Trie & Aho-Corasick] KMP : 문자열 S가 있을 때, 패턴 P를 찾는 알고리즘 Trie : 문자열 N개가 있을 때, 문자열 S를 찾는 알고리즘 ex) 출석부에서 내 이름(full name) 찾기 Aho-corasick : 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘 ex)출석부에서 나랑 성이 같은 사람, 이름이 같은 사람을 찾기 코딩테스트 비중은 KMP보다 Trie가 더 높으며 Trie는 해시로 대처 할 수 있다고 함. 아호 코라식은 자주 나오는 문제는 아니다. Trie https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85) 트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전 "A", "to", "tea", "ted..
문자열 매칭 알고리즘[2](KMP)[String Searching Algorithm, Knuth-Morris-Pratt] 먼저 이 문제(찾기, 1786)를 먼저 보고 오자. 백준에서 플5문제이고 KMP를 사용해야 되는 이유를 잘 설명해주고 있다. 문자열 매칭 알고리즘을 사용해서 문자열에서 패턴을 시간복잡도 O(|S|)으로 찾아보자. 파이썬에서는 kmp 관련 문제가 나오면 정규식(regex, re)으로 찾자^^. 1. KMP 알고리즘 정의 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. KMP 알고리즘은 Knuth, Morris, Prett가 만든 문자열 매칭 알고리즘으로 시간복잡도는 O(N+M)으로 무식한 방법 O(NM)보다 매우 빠르다. 더보기 사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다. 첫 번째는 성을..
문자열 매칭 알고리즘[1](라빈 카프)[String Searching Algorithm, Rabin-Karp] 문자열 S에서 패턴 P를 찾는다고 해보자. 기본적으로 생각나는 방법은 S의 시작 위치에서 P가 나오는지 검사하는 것이다. s[0]부터 P와 같은지?, s[1]부터 p와 같은지?, s[2]부터 p와 같은지?, ... 이 경우에 시간복잡도는 O(|S|x|P|)이다. 일번적으로 비교할 경우 너무 비효율적이어서 사용하기 어렵다. 문자열 매칭 알고리즘을 사용해서 문자열에서 패턴을 시간복잡도 O(|S|)으로 찾아보자. 1. 라빈 카프 알고리즘 정의 해쉬(Hash)함수를 사용해서 문자열에서 특정 문자열과 일치하는지 찾아주는 알고리즘이다. 2. 라빈 카프 알고리즘의 개념 해쉬함수 : 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어주는 함수(어떤 문자열을 정수로 표현하는 함수) 라빈 카프 알고리즘은 문자열을 정수로 바..
벡터의 활용(Vector, C++) 보호되어 있는 글입니다.

티스토리툴바