[백준 파이썬] 1786 찾기

문제 문자열에 대해 원하는 패턴이 존재하면 패턴이 몇번 나타나는지 또 패턴이 나타나는 위치를 출력하는 문제이다. 풀이 KMP알고리즘을 활용하면 해결할 수 있다. KMP알고리즘의 아이디어는 다음과 같다. 패턴에 대해 반복되는 부분이 있다면, 모든 문자열을 비교할 필요 없이 반복되는 부분은 건너뛸 수 있지 않을까? 그걸 구체적으로 구현하면 아래와 같이 된다. 먼저 패턴을 이용하여 Lps배열을 만든다. Lis배열이란 패턴이 얼마나 중복된 패턴을 가지고 있는지 나타내는 배열이다. abcdabc패턴에 대해서는 다음과 같이 lps배열이 만들어진다. 해당 과정을 코드로 나타내면 다음과 같다. def makeLps(p): #Lps 배열을 만든 후 리턴 tmpTable = [0] * len(p) j = 0 for i ..

• format_list_bulleted 카테고리 없음
• · 2024. 4. 11.
• textsms

[프로그래머스 파이썬] 올바른 괄호

문제 풀이 스택을 이용하여 간단하게 해결할 수 있다. 먼저 "("의 경우와 ")"의 경우를 나눠서 생각한다. for i in s: if i == "(": stack.append("(") 반복문을 사용하여 s(여기서는 전체 괄호)중 하나씩 뽑아 진행한다. 만약 "("가 들어올 경우 스택에 그대로 추가시켜준다. else: if not stack: answer = False break if stack.pop() == ")": answer = False break ")"가 들어온 경우도 두가지 경우로 나누어 생각한다. 만약 )가 들어왔지만 스택이 비어있는 경우 이전에 "("가 없이 ")"가 들어온 경우이므로 괄호가 짝지어지지 않은 경우이다. 따라서 정답이 아니므로 False로 설정하고 break한다. 또한 po..

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

[코드트리 파이썬] 삼 오 무

문제 풀이 이분탐색을 이용해 해결하였다. 임의의 숫자 하나를 정한 후 해당 숫자가 우리가 구하려는 답보다 큰지 작은지만 판별하면 된다. 주어진 N은 Moo값을 건너뛴 숫자이므로 1, 2, Moo, 4, Moo, Moo, 7 의 순서로 진행하였을 때 N이 4라면 답은 7이된다. 따라서 N이 주어졌을 때 내가 가진 숫자가 N이 가리키는 숫자보다 큰지 작은지 판별한다. 판별법은 다음과 같아 Moo는 3과 5의 배수로 진행한다. 임의의 값이 주어졌을 때 해당값을 3으로 나눈 나머지는 1부터 해당 값까지의 숫자 중 3의배수의 숫자의 개수이므로 임의의 수를 3으로 나눈 나머지와 5로 나눈나머지를 뺀 후 공통된 15로 나눈 나머지를 더한 뒤 나온 수를 N값과 비교하여 판단하면 된다. 예를들어 주어진 N은 4 즉 7을..

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

[백준 파이썬] 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