알고리즘
[백준 파이썬] #1406. 에디터
풀기 전 생각해보기😮 시간초과가 발생한다면 자료구조를 사용해보기 2개의 스택 구조를 사용해보자 풀이🛫 # pypy3 채점으로 정답 # 스택을 하나 더 사용하는 방식을 사용 left = list(input()) right = [] # 임시 스택 공간 N = len(left) M = int(input()) for m in range(M): ord = list(input().split()) if ord[0] == 'L': # 커서 왼쪽 이동 if left: # inp이 존재할 때 right.append(left.pop()) # right 공간에 저장 elif ord[0] == 'D': # 커서 오른쪽 이동 if right: # temp가 존재할 때 left.append(right.pop()) # temp에서 ..
[백준 파이썬] #2430. AC
풀기 전 생각해보기😮 시간초과가 발생한다면 자료구조를 사용해보기 오류가 발생한다면? : https://www.acmicpc.net/board/view/25456 풀이🛫 from collections import deque T = int(input()) for tc in range(1, T+1): p = list(input()) n = int(input()) inp = deque(input()[1:-1].split(',')) err = False rcnt = 0 for i in p: if i == 'R': rcnt += 1 elif i == 'D': if len(inp) > 0 and inp != deque(['']): # 여기서 문제가 발생 if rcnt % 2 == 1: # 홀수 번 뒤집기가 진행되었을..
[백준 파이썬] #10799. 쇠막대기
풀기 전 생각해보기😮 stack 문항 각각의 경우를 따져서 풀 수 있다 풀이🛫 # 스택 # 모든 경우대로 조건문을 나열 arr = list(input()) stack = [] cnt = 0 for i in range(len(arr)): if len(stack) == 0 and arr[i] == '(': # stack이 아직 만들어지지 않았을 경우 stack.append('(') else: # stack이 존재할 때 # 이전에 들어온 값과 현재 입력되는 값을 비교 # 모든 경우의 수는 4가지 밖에 되지 않음 if arr[i-1] == '(' and arr[i] == '(': # case1 stack.append('(') elif arr[i-1] == '(' and arr[i] == ')': # case2 ..
[SWEA] #10989. 폭격 작전_파이썬
풀기 전 생각해보기😮 IM 시험 대비 델타 값 이용해서 방향 탐색 visited 활용해서 계산 중복 방지하기 풀이🛫 # U, R, D, L dcol = [-1, 0, 1, 0] drow = [0, 1, 0, -1] T = int(input()) for t in range(T): N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] visited = [[0] * N for _ in range(N)] kills = 0 for m in range(M): C, R, P = map(int, input().split()) # 폭탄이 떨어진 곳의 피해값 if visited[C][R] == 0: kills +=..
[알고리즘] 패턴 매칭 알고리즘 소스코드
- 한번만 찾는 경우 # 패턴이 있을 수 있는 가능한 시작 위치 for i in range(n-m+1): # 패턴의 길이 만큼 비교 for j in range(m): # 일치하지 않으면 다음으로 넘어감 if p[j] != t[i+j]: break else: # 매칭 성공 break - 모든 패턴을 찾을 때 : 방법1 i = 0 while i
[SWEA] 1959. 두 개의 숫자열
풀기 전 생각해보기😮 다중 for 구문의 구현 풀이🛫 # 1959. 두 개의 숫자열 T = int(input()) for t in range(T): N, M = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) li = [] if N M: for j in range(N-M+1): total = 0 for i in range(M): total += A[i+j]*B[i] li.append(total) ..
[알고리즘] 문자열 패턴 매칭
패턴 매칭에 사용되는 알고리즘 고지식한 패턴 검색 알고리즘(=Brute Force) 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 고지식한 패턴 검색 (Brute Force) 문자열을 처음부터 끝까지 차례대로 순회, 패턴 내의 문자들을 일일이 비교 텍스트에서 패턴이 존재하는 모든 위치를 찾는 문제 시간복잡도 : O(MN) M: 패턴의 길이, N: 텍스트의 길이 최악의 경우 텍스트의 모든 위치에 대해 패턴을 비교해야 함 패턴 매칭 알고리즘의 중요 포인트 일치하는 경우 ( t[i] == p[j] ) i, j를 증가시켜서 다음 문자를 비교 불일치하는 경우 다음 매칭의 시작위치로 i, j 값을 설정 ※ 자주 사용되는 대치어 텍스트 패턴 기본 t p 인덱스 i j 길이 m n KMP 알고리즘 불일치가 ..
[SWEA] #4831. 전기버스_파이썬
풀기 전 생각해보기😮 정답을 도출하는데 필요한 조건만 구현하기 인덱스 주의 풀이🛫 T = int(input()) for t in range(T): K, N, M = map(int, input().split()) station = [0] + list(map(int, input().split())) + [10] curIdx = 0# 현재의 위치 charCnt = 0 # 충전 횟수 for i in range(1, M+2): # 목적지에 도달할 수 없는 경우 if station[i] - station[i-1] > K: answer = 0 break if curIdx + K < station[i]: curIdx = station[i] charCnt += 1 print(f"#{t+1}", charCnt) 핵심 정리..
[SWEA] #1210. Ladder1_파이썬
풀기 전 생각해보기😮 시작점에서 출발하는게 편할까? 도착점에서 출발하는게 편할까? 특정 조건을 만족할 때까지 전진시키는 방법 풀이🛫 T = 10 for t in range(T): case = int(input()) arr = [list(map(int, input().split())) for i in range(100)] # 도착지점의 인덱스 찾기 col, row = 0, 0 for end in range(100): if arr[99][end] == 2: col = 99 row = end break # 출발점에 도착할 때까지 진행 while col != 0: # col == 0: 시작점 # 왼쪽에 길이 있을 때 if row-1 >= 0 and arr[col][row-1] == 1: while row-1 >..
[SWEA] # 11012. 사각영역들의 합_파이썬
풀기 전 생각해보기😮 영역을 벗어난 곳을 계산해야 할 경우 어떻게 처리해야 할지 이미 계산된 곳을 계산하지 않으려면 어떤 처리를 해야 할지 풀이🛫 T = int(input()) for i in range(T): # 배열 생성 N, M = map(int, input().split()) arr = [list(map(int, input().split())) for i in range(N)] carr = [[True] * N for i in range(N)] answer = 0 # 정사각형 값의 합 구하기 for j in range(M): row, col, length = map(int, input().split()) s = 0 for c in range(length): for r in range(length)..