본문 바로가기

brute force7

[Python]보이어무어 알고리즘 본 코드는 text안에 찾는 pattern 이 있으면 1 없으면 0 을 출력해주는 코드이다 보이어무어 알고리즘을 적용했다. 보이어무어 알고리즘이란 다음과 같다 pattern의 오른쪽 끝 문자와 text의 현재 위치의 문자가 일치하는지 검사 끝이 일치하면 pattern과 text를 다 검사한다. 마지막까지 일치하지 않으면 패턴길이만큼 skip 끝이 일치하지않으면 text의 현재위치 문자가 skip배열에 있는지 확인. 있으면 인덱스만큼 skip, 없으면 패턴길이만큼 skip 텍스트 끝 도달할 때까지 반복 text = 'a pattern matching algorithm' pattern = 'rithm' s = pattern[::-1] skip = list(range((len(pattern)))) i = le.. 2019. 4. 27.
[Python]14889. 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제는 0*n//2 와 1*n//2 로 이루어진 n 길이의 순열을 만들어서 이중포문에 넣으면 되는 간단한 문제이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243def next_perm(a): i = len(a)-1 while i > 0 and a[i-1] >= a[i]: i -= 1 if i = a[j]: j -= 1 a.. 2019. 4. 22.
[Python]2529. 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738def recur(idx): if len(tmp) == k+1: result.append(tmp[:]) return for i in range(10): if idx == -1 and candi[i]: tmp... 2019. 4. 16.
[Python]16985. Maaaaaaaaaaze https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다. www.acmicpc.net Step1. 순열 생성 -> 블록이 쌓이는 순서를 생성해준다. 여기서는 5! 경우의 수 Step2. 회전 -> 각 층에 있는 블록은 독립적으로 회전한다. 블록당 4번 회전할 수 있으므로, 4^5 의 경우의 수 Step3. 탐색 -> (0,0,0) 부터 (4,4,4) 까지 BFS탐색으로 최단거리를 리턴한다. 최악일때 5*5*5 3차원 큐브에 있는 1칸짜리 블록은 상하.. 2019. 4. 12.
[Python]17070. 파이프 옮기기1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 처음엔 DFS형태로 check배열 생성한다음 모든 경로를 다 탐색했으나.. 계속 60% 쯤에서 계속 시간초과가 발생했다. 다.. 2019. 4. 12.
[Python]6064. 카잉 달력 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net 그냥 브루트포스로 구현하면 최대 경우의 수가 40000^2 으로 제한시간내에 통과할 수 없다. 규칙을 찾아서 연산해서 값을 구해야 한다. 전체 경우의 수를.. 2019. 4. 9.
[Python]1107. 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러번 주어지는 경우는 없다. www.acmicpc.net 브루트포스로 접근 Step1.먼저 0~1,000,000 까지 수를 생성한다 Step2.생성된 수 중에서 고장난 숫자를 포함하고 있으면 버린다. 고장난 수를 포함하지 않으면 channels 에 추가한다. Step3.channels에서 가장 최소값을 구한다 Step4.현 위치(100)에서의 눌러야 하는 값과 Step3에서 구한 최.. 2019. 4. 8.
728x90
반응형

티스토리툴바