본문 바로가기

백준

(2)
[백준 BOJ] C++) 1605번: 반복 부분 문자열 문제 링크 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분문자열'의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 예제 이해 예제) tellmetellmetetetetetetetellme 의 부분문자열의 길이가 11이라고 한다 길이 11의 부분문자열을 찾는데 애를 먹었다 찾은 부분 문자열은 etetetetete 이다. 그 이유는? 풀이 접근 방식 길이 L의 부분 문자열을 찾는다. 부분 문자열을 찾고 없으면 길이 L-1의 부분 문자열을 찾는다. 소스 코드 (1차..
[BOJ] (C++14) 2458번 문제) 키 순서 문제 링크 누가 누구보다 크다는 키 순서 쌍을 받아오면 이 키 순서 쌍을 토대로 누가 몇번째로 큰지 확실히 알 수 있는 사람의 수 힌트 플로이드-워셜 알고리즘을 쓰면 노드에서 다른 노드를 거쳐 가는 길까지 다 구할 수 있다 순서를 확실히 알 수 있는 사람: 자기보다 큰 노드의 수 + 자기보다 작은 노드의 수 = 모든 노드의 수 - 1 을 구할 수 있는 사람 플로이드-워셜 알고리즘 // vertex가 N개 있을 때 // i부터 j까지 edge의 유/무 및 weight 값은 matrix로 저장됨 // int graph[i][j]가 존재 한다고 가정 for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ..