Algorithm/BOJ(백준)
-
백준 7576 토마토Algorithm/BOJ(백준) 2018. 9. 30. 19:26
문제 링크 : https://www.acmicpc.net/problem/7576※선행해야 할 알고리즘 : BFS/DFS Algorithm : BFS/DFS 를 활용하여 행렬에서 -1을 제외한 모든 0을 1로 만들 때 걸리는 최단 횟수를 구하여라. (단, 모든 0을 1로 만들지 못할 시엔 -1 출력) 1. 토마토가 익은 index를 입력 시, 1일 때 바로 queue에 삽입한다.BFS를 실행할 시, 토마토가 익은 구간을 queue에 삽입하여야 한다. 이 때, 모든 index를 입력 후에 1을 찾게 된다면 n*m만큼의 시간복잡도가 추가되기에 복잡도 단축을 위해 입력하면서 바로 queue에 삽입할 수 있도록 한다. 2. 또한, visit 배열을 초기화 할 때 모두 false로 처리하는 것이 아니고 queue에..
-
백준 1697 숨바꼭질Algorithm/BOJ(백준) 2018. 9. 28. 23:49
문제 링크 : https://www.acmicpc.net/problem/4354※선행해야 할 알고리즘 : BFS, DFS Algorithm : N에서 K까지 갈 때 count를 센다. 1. 미로찾기로 따지면 N이 시작점, K가 출구가 된다. 즉, 현재 위치값을 순간이동(*2), 오른쪽(+1), 왼쪽(-1)을 통해 바꿔가며 찾는다. 즉, 입력 예제를 통해 본다면 1 2 3 4 5 6 7 8 9 1011 12 13 14 1516 17 18 19 20 빨간색은 시작점 -> 노란색은 이동거리 -> 파란색은 도착점 이 되는 것이다. 2. queue를 활용하여 BFS를 진행하면 다음과 같다. //kuklife.tistory.com #include#include#include#includeusing namespace..
-
백준 4354 문자열 제곱Algorithm/BOJ(백준) 2018. 9. 6. 23:43
문제 링크 : https://www.acmicpc.net/problem/4354※선행해야 할 알고리즘 : KMP Algorithm 1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음. 2. 다음 예제 입력 문자열들의 patterntable값을 구하면 다음과 같다.string patterntable[string.size()-1] abcd 0 aaaa 3 ababab 4 하지만, 문제가 원하는 값은 패턴 문자열들의 개수를 구하는 것임으로 다음과 같다.string패턴 문자열패턴 문자열의 개수 abcd abcd1aaaaa4abababab3 첫번째와 두번째는 패턴 문자열이 없거나 ..
-
백준 1305 광고Algorithm/BOJ(백준) 2018. 9. 6. 21:23
문제 링크 : https://www.acmicpc.net/problem/1305※선행해야 할 알고리즘 : KMP Algorithm Algorithm : 문자열의 pattern table을 구한 후 그 해당하는 pattern table값을 문자열 길이에서 빼준다. 1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음. 2. 예를 들어aabaaa에서 보면 pi=2, prefix suffix가 같은 최대의 부분 문자열이 aa이다. 길이가 N인 광고가 계속 이어져 있는 것을 생각하면 prefix aa는 앞 광고의 suffix aa로 볼 수도 있을 것이다. 즉, baaa가 원래 광고..
-
백준 1701 CubeditorAlgorithm/BOJ(백준) 2018. 9. 6. 16:28
문제 링크 : https://www.acmicpc.net/problem/1701※선행해야 할 알고리즘 : KMP Algorithm Algorithm부분 문자열마다의 pattern_table을 생성하여 그 중 값이 가장 큰 것을 return 한다.(해당 내용 : KMP Algorithm 참고) 1. 여기서 말하는 "부분 문자열" 마다의 의미는 예제 입력 "abcdabcabb"을 기준으로 다음과 같다. (1) abcdabcabb (부분 문자열 1) (2) bcdabcabb (부분 문자열 2) (3) cdabcabb (부분 문자열 3) . . . (10) b (부분 문자열 10) 2. "pattern_table"의 의미는 다음과 같다.문자열의 모든 부분 문자열의 접미사와 접두사가 같은 문자열의 문자 개수들을 ..