본문 바로가기

algorithm/middle

 (21)
프로그래머스 레벨 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..
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++) 보호되어 있는 글입니다.
스택 문제 풀이2(16909, 카드 구매하기3)[Stack PS] 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 11052 - 카드 구매하기 (실버1) : https://www.acmicpc.net/problem/11052 풀이 : N개의 카드를 구매하기 위해 지불할 수 있는 금액의 최댓값을 구하는 문제. 전형적인 dp(다이나믹 프로그래밍) 문제이며, N의 범위가 10^3으로 시간복잡도가 O(N^2)일 때 10^6으로 제한시간 내에 충분히 가능하다. 가장 쉬운 방법으로는 가능한 모든 경우의 수를 구하여 값 중 최댓값을 구하는 것이다. 하지만 같은 카드를 구매하는 경우에서 굳이 적은 비용을 낼 ..

티스토리툴바