본문 바로가기

코딩

 (102)
[python3] 백준 1786 찾기 KMP알고리즘으로 풀면 된다. http://deque.tistory.com/78 text = input() pattern = input() pi = [0 for i in range(0, len(pattern))] result = list() count = 0 j=0 for i in range(1,len(pattern)): while(j > 0 and pattern[i] != pattern[j]): j = pi[j - 1] if(pattern[i] == pattern[j]): j+=1 pi[i] = j j = 0; patternLength = len(pattern) textLength = len(text) for i in range(0, textLength): while(j > 0 and text[i] !..
KMP 알고리즘 http://mygumi.tistory.com/61http://bowbowbow.tistory.com/6 text = input() pattern = input() pi = [0 for i in range(0, len(pattern))] result = list() count = 0 j=0 for i in range(1,len(pattern)): while(j > 0 and pattern[i] != pattern[j]): j = pi[j - 1] if(pattern[i] == pattern[j]): j+=1 pi[i] = j j = 0; patternLength = len(pattern) textLength = len(text) for i in range(0, textLength): while(j > 0..
백준 1015 수열 정렬 //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include using namespace std; vector sortArr; vector prevArr; vector isFill; int main() { int N; scanf("%d", &N); int temp; for (int i = 0; i < N ; i++) { scanf("%d", &temp); sortArr.push_back(temp); prevArr.push_back(temp); isFill.push_back(false); } sort..
백준 1016 제곱 ㄴㄴ수 에라토스테네스의 체 문제이다 만약, "min에서 max까지 순회하면서 각 값이 2~백만의 값의 제곱수로 나누어 떨어질경우 pass" 하는 식으로 알고리즘을 짜면 n^2이 되기때문에 시간초과가 난다. 따라서 백만짜리 배열을 선언하고 # "i"는 2~max까지 순회하며 다음을 반복 ## (i*i) * j 는 제곱 YES수이므로 배열[(i*i) * j]를 true로 바꾼다. 다만 (i*i) * j의 값을 min~max 사이로 해싱한다 민다 j+=1. ## # 마지막에 배열에서 false가 몇개인지 샌다 # 와 같은 알고리즘은 배열의 값을 중복해서 체크하는 경우가 거의 없기 때문에 시간복잡도를 n으로 봐도 되므로(즉, 백만) 시간 안에 해결 가능하다. #include using namespace std; boo..
백준 10217 KCM Travel 분명 풀기는 다풀었는데어이없이 몇번이고 시간초과가 났다.원인은 cmp.....템플릿에 cmp를 넣다보니 뒤죽박죽으로 섞여서 cmp가 제대로 구현이 안됐는데, 예제는 잘돌아가서 문제인지도 모르고 막 제출했다..이거 하나때문에 2시간을... 알고리즘을 할땐 내가 뭘 만들려고 하지말고 조용히 pair를 애용하자 다익스트라알고리즘을 수행하되, 다음과 같이 memo를 한다.memo[i][j] = i번째 노드에 j의 cost로 도달 할 수 있는 최소의 거리그리고if (memo[now][edge.Cost] M) continue;등으로 적당히 가지를 쳐주면 된다. //..
백준 11657 타임머신 벨만포드 알고리즘을 수행하면서, 음수사이클이 있을 경우 -1 출력 참고 : 벨만포드 알고리즘 http://deque.tistory.com/72백준 1865 웜홀 http://deque.tistory.com/71 //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include using namespace std; template class triple { public: FIRST first; SECOND second; THIRD third; triple(FIRST a, SECOND b, THIRD c) { first = a; secon..
벨만 포드 알고리즘 모든 간선을 탐색하면서 A->B 보다 A->V[i]->B가 더 빠를때 갱신.한편 dist[A]가 INT_MAX일 경우 계산해봤자 어차피 false일테니까 컨티뉴.위의 계산을 V-1번 반복하여 최적화된 답을 찾음.한편 마지막 V번 반복을 하였을 때 만약 값이 갱신되는 Vertex가 있다면 음수 사이클이 있다는 것을 의미한다. template class triple { public: FIRST first; SECOND second; THIRD third; triple(FIRST a, SECOND b, THIRD c) { first = a; second = b; third = c; } }; bool BellmanFord(vector &dist, vector &edge, int V, int E, int Star..
백준 1865 웜홀 밸만포드 알고리즘을 시행하고 음수사이클이 있으면 YES를 출력하면 된다. triple이란 클래스를 하나 만들어봤다. 그래프 알고리즘 풀때마다 매번 이것저것 하는것도 귀찮아서 pair처럼 하나 만들었다. //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include using namespace std; template class triple { public: FIRST first; SECOND second; THIRD third; triple(FIRST a, SECOND b, THIRD c) { first = a; second = b..

티스토리툴바