본문 바로가기

알고리즘/백준

 (263)
[백준] 5052번 : 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 해당 문제는 문자열의 접두사를 찾는 문제로 문자열을 찾는 시간복잡도 O(m)과 전화번호 목록의 개수 O(n)으로 임으로 O(m*n) 문제로 해결 할 수 있습니다. 트라이 자료구조 활용하였습니다. class Node(object): def __init__(self, key, data=None): self.key = key self.data = data self.children..
[백준] 5582번 : 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net ABCD, ACDB 일때 dp 테이블을 다음과 같이 만들 수 있다. ACD와 ABCD의 값을 구할때, AC, ABC의 최대 길이를 +1 해준다. 즉 점화식을 다음과 같이 세울 수 있다. str[i]==str[j] 일때 , dp[i][j] = dp[i-1][j-1] + 1 str1 = input() str2 = input() length1 = len(str1) length2 = len(s..
[백준] 9935번 : 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 해당 문제를 처음에는 파이썬 내장함수로 문제를 풀었지만, 시간복잡도가 o(n^2)으로 시간초과가 발생한다. 해당 문제를 해결하기 위해서 스택 자료구조 를 활용하여 O(n)으로 문제를 풀 수 있다. 개선 이전 ( 내장함수 in , replace 함수 사용 ) char = input() bumpchar = input() while bumpchar in char: char = char.r..
[백준] 1932번 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 해당 문제는 다이나믹 프로그래밍에 기본 문제로 탑다운 방식과 바톰업 방식을 둘다 풀어보겠습니다. 브루트포스 방식으로 문제를 해결 할 경우 모든경우의수를 탐색해야함으로 O(n^2) 이라는 시간복잡도를 갖게 됩니다. 1) 탑다운 방식 # 탑다운 방식 n = int(input()) # 삼각형의 크기 triangle = [] for _ in range(n): triangle.append(list(map(int, input().split()))) dp = [[0 for _ in..
[백준] 11660번 : 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net dp 테이블을 i번째부터 j번째까지의 누적합을 구하는 테이블을 만든다. 해당 테이블을 초기화하고 x1,y1, x2,y2의 좌표값을 받아 해당 구간의 합을 구하는 공식을 생각하여 풀었습니다. 누적합은 점화식 dp[i][j] = dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] + table[i-1][j-1] x1, y1, x2,y2가 주어졌..
[백준] 11057번 : 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 해당 문제의 아이디어는 가장 끝에있는 수에따라서 오르막의 경우의 수가 정해진다는 것입니다. N= 1 일때 0일때 1개 1일때 1개 2일때 1개 3일때 1개 4일때 1개 5일때 1개 6일때 1개 7일때 1개 8일때 1개 9일때 1개 총합 : 10개 N=2 일때 0일때 10개 (00, 01,02,03,04,05,06,07,08,09) 1일때 9개 (11,12,13,..
[백준] 14003번 : 가장 긴 증가하는 부분 수열 5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 해당 문제는 ans 테이블을 역추적하여 문제를 해결 할 수 있다. 단일 for문에서 ans테이블을 해당 원소를 삽입하였을때 자기자신의 위치를 기록한다. 자기자신의 위치를 기록해두어 dp테이블을 역 순회 하여 해당 길이가 증가되었을때의 원소를 찾는다. 1. arr[i]가 현재 배열의 마지막 원소보다 클 경우 - arr[i]는 현재 lis의 길이를 저장 2. arr[i]..
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 위의 문제는 https://bigkwangs.tistory.com/28 [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) w b..

티스토리툴바