[백준 파이썬] 1701 Cubeditor

문제 문자열이 주어지고 반복되는 문자열이 2개이상 있는 부분 문자열중 가장 긴 길이를 출력하면 된다. 풀이 주어진 문자열을 하나하나 탐색하면 당연히 시간초과가 나게된다. 따라서 Failure 함수를 사용하여 문자열이 존재하는지 파악해야한다. Failure함수의 아이디어는 다음과 같다. 문자열에 반복되는 부분은 다시 검사할 필요가 없다라는 것이다. 다음과 같이 s1과 s2를 비교할 때 s2는 abab이므로 앞에 ab는 한번 비교해놓으면 두번째는 비교할 필요가 없다. 이 때 abab를 몇칸 이동해야하는지에 대한 정보를 담은게 fail 배열이다. abcabcacab에 대한 문자열에 대해 fail배열은 다음과 같이 나오게 된다. 이때 최대 숫자인 4가 겹치는 문자열의 최대 길이가 된다. 다음을 구현하는 코드는..

• format_list_bulleted 알고리즘
• · 2024. 4. 4.
• textsms

[코드트리 파이썬] 1이 K개 이상 존재하는 부분 수열

문제 풀이 투 포인터를 이용하였다. 1이 K개 이상 존재하는 가장 짧은 수열의 길이를 구하여야 한다. j = 0 oneCnt = 0 먼저 투포인터의 두번째 포인터인 j와 1의 개수를 세어줄 oneCnt를 선언하였다. 1의 개수를 세어주기 위하여 다음과 같은 방법을 사용하였다. 먼저 첫 번째 포인터인 i를 순회시킨다. 이 때 i가 1을 만난다면 두 번째 포인터를 순회시킨다. for i in range(n): if arr[i] == 1: while j < n and oneCnt != k: if arr[j] == 1: oneCnt += 1 j += 1 두 번째 포인터는 끝까지 도달했거나 1을 k만큼 카운트할 때까지 순회한다. 순회 중 1을 만나면 oneCnt값을 1 증가시킨다. if oneCnt != k an..

• format_list_bulleted 알고리즘
• · 2024. 4. 1.
• textsms

[코드트리 파이썬] 정수 두 개의 합2

문제 풀이 투 포인터를 이용하면 된다. n, k = map(int, input().split()) arr = [] for i in range(n): arr.append(int(input())) arr.sort() 두 개의 합이 k이하가 되어야 하기 때문에 입력받은 배열을 정렬해준다. res = 0 valSum = 0 j = n - 1 for i in range(n): while j != 0 and arr[i] + arr[j] > k: j -= 1 if j k: j -= 1 if j

• format_list_bulleted 알고리즘
• · 2024. 3. 30.
• textsms

[코드트리 파이썬] 바구니 안의 사탕

문제 1차원 그래프에 바구니가 놓여있고 해당 바구니에 사탕이 놓여있다. 이 때 한 지점을 잡아 주어진 범위에 사탕이 가장 많은 경우를 구한다. 풀이 N = 100000, K = 2000000 이기 때문에 이중 이상의 루프를 돌면 시간이 초과된다. 따라서 투포인터를 이용하여 해결하였다. N, K = map(int, input().split()) maxSize = 1000001 arr = [0] * maxSize basket = set() for i in range(N): a, b = map(int, input().split()) arr[b] += a basket.add(b) 배열의 최대 크기를 정의하고 해당 크기만큼의 배열을 만든다. 그 후 좌표와 사탕의 개수를 입력받아 배열에 더해준다. 이렇게 하는 이유..

• format_list_bulleted 알고리즘
• · 2024. 3. 28.
• textsms

[코드트리 파이썬] 가장 짧은 부분합

문제 풀이 투포인터 기초가 부족하여 풀게 된 문제이다. 특정 구간을 잡았을 때 합이 s보다 커야하고 그 구간들 중 가장 짧은 구간을 구하는 문제이다. 완전탐색으로 해결하면 n^2의 시간복잡도가 나오지만 투포인터는 n이기때문에 해결할 수 있다. n, s = map(int, input().split()) arr = [0] + list(map(int, input().split())) res = 4e9 sumVal = 0 j = 0 먼저 필요한 정보들을 입력받는다. 편의상 배열의 0번째는 0으로 채워넣었다. for i in range(1, n + 1) : while j + 1

• format_list_bulleted 알고리즘
• · 2024. 3. 25.
• textsms

[코드트리 파이썬] 팀으로 하는 틱택토

문제 풀이 일반적인 틱택토이지만 2개의 숫자가 한팀이 되었을 때만 이긴걸로 간주한다. 즉 1 1 1 과 같이 한 숫자로만 이루어진 줄은 이긴걸로 간주되지 않는다. 틱택토는 항상 3X3의 배열이므로 이를 이용하여 문제를 해결하였다. team = set() for i in range(3): tmp = set() for j in range(3): tmp.add(graph[i][j]) if len(tmp) == 2: team.add(tuple(sorted(graph[i]))) 배열의 가로를 검사하는 코드이다. 3X3배열에서 두 숫자가 팀이되어서 이길 경우는 한 줄에 2개의 숫자만 있으면 된다. 따라서 set자료형을 이용하여 중복을 제거했을 때 길이가 2개일 경우 tuple로 정렬된 줄을 team에 넣는다 fo..

• format_list_bulleted 알고리즘
• · 2024. 3. 21.
• textsms