string10 [Problem Solving] BOJ 7490: 0 만들기 문제 링크: https://www.acmicpc.net/problem/7490 백트래킹 + 문자열 문제이다. 1부터 N까지의 수를 순서대로 늘어놓고 인접한 수를 붙이거나 더하거나 빼서 0이 되는 경우의 수를 출력하는 문제이다.백트래킹이기 때문에 모든 함수를 재귀 호출하여 모든 경우의 수를 따져본다.식을 s에 만들어서 재귀함수에 넘겨준다. 공백이 있으면 replace함수로 공백을 제거한다음에 eval(e)로 0이면 s를 출력한다. import syssys.setrecursionlimit(10 ** 6)read = sys.stdin.readlineN = 0def is_zero(s): e = s.replace(" ", "").rstrip() if eval(e) == 0: return T.. 2025. 4. 6. [Problem Solving] BOJ 1013: Contact 문제 링크: https://www.acmicpc.net/problem/1013 정규 표현식을 사용하여 주어진 문자열이 정규 표현식에 매칭되는지 확인하는 문제이다.pattern에 ^(100+1+|01)+$ 을 컴파일하는데,여기서 ^와 &는 주어진 문자열의 전체를 매칭한다는 뜻이다. ^는 문자열의 시작을 의미하고, $는 문자열의 끝을 의미한다.주어진 문자열 전체에 대해 (100+1+|01)+이라는 패턴이 존재하는 지 확인해야한다.패턴 (100+1+|01)+은(100+1+) 이라는 패턴이 한 번 이상 존재 하거나, (01) 이라는 패턴이 한 번 이상 존재하는 패턴이다(100+1+)은 10뒤에 0이 한 번 이상 나타나야 하고, 그 뒤에 1이 한 번 이상 나타나는 패턴이다. import sysimport rere.. 2025. 3. 23. [Problem Solving] BOJ 4358: 생태학 문제 링크: https://www.acmicpc.net/problem/4358 Dictionary에 종별 개수를 카운트 한다.카운트의 합을 모두 더한다비율을 계산해서 소수점 4자리까지 출력한다. import sysread = sys.stdin.readlinenameList = []nameCnt = {}while True: name = read().rstrip() if not name: break if name not in nameList: nameList.append(name) nameCnt[name] = 1 else: nameCnt[name] += 1nameList.sort()Sum = 0for i in nameList: Su.. 2025. 3. 10. [Problem Solving] BOJ 17609 : 회문 문제 링크 : https://www.acmicpc.net/problem/17609 투 포인터를 이용해서 문자열이 회문인지, 유사회문인지, 둘다 아닌지 판별하는 문제이다. left = 0, right = len(s)로 시작해서 left와 right를 각각 오른쪽, 왼쪽으로 이동시킨다. left s[left] != s[right]가 된다면,s[left + 1 : right + 1](s의 left + 1번째 부터, right 번째를 포함하는 substring)가 회문, 또는 s[left : right](s의 left번째 부터, right - 1번째를 포함하는 substring)가 회문이라면 유사회문이므로 1을 출력하고, 둘 다 그렇지 않다면 2를 출력한다. def is_palindrome(s): lef.. 2025. 3. 1. [Problem Solving] BOJ 5582 : 공통 부분 문자열 문제 링크 : https://www.acmicpc.net/problem/5582 가장 긴 공통 부분 문자열의 길이를 구하는 문제이다.dp[i][j]는 s[j - 1]와 t[j - 1]이 같을 때, s[:i]와 t[:j]의 가장 긴 공통 부분 문자열의 길이가 된다.따라서 s[j - 1] == t[j - 1]일 때, dp[i][j]를 dp[i - 1][j - 1] + 1로 설정한다.dp테이블을 다 채우고, 테이블 내 가장 큰 값이 답이 된다. import sysread = sys.stdin.readlines = read().rstrip()t = read().rstrip()answer = 0dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]for i in range.. 2025. 2. 21. [Problem Solving] BOJ 12891 : DNA 비밀번호 문제 링크 : https://www.acmicpc.net/problem/12891 A, C, G, T로만 이루어진 문자열에서 각 문자의 최소 개수를 만족하는 부분 문자열의 개수를 구하는 문제이다. 단순한 패턴매칭으로 풀면 N은 최대 100만, M도 최대 100만이기 때문에 O(NM) 만큼이 걸려 시간초과가 발생한다. 슬라이딩 윈도우 방법을 사용하면 선형 시간 안에 해결이 가능하다.윈도우를 이동시키면서 윈도우에 포함된 A, C, G, T의 개수를 조정한다. 조정 후에 최소 개수를 만족한다면 answer를 1 증가시킨다.윈도우 이동이 끝나면 answer를 출력한다. import sysread = sys.stdin.readlineS, P = map(int, read().split(" "))DNAString =.. 2025. 2. 15. 이전 1 2 다음