알고리즘19 문자열 겹치기(구현, KMP) 단순한 문젠데 구현하는데 시간이 좀 걸렸던 것 같다. KMP를 통해 구현하면 좀 더 편하고 성능좋게 구현할 수 있지않을까 생각이 들었다. s1,s2의 길이가 100이라 일단 구현으로 풀었으나 KMP 문제 또한 풀어보며 해당 방식으로 구현해봐야겠다. def solution(s1, s2): answer = '' pre = "" post = "" for i in range(len(s2)-1): pre+="!" post+="!" first = pre+s1+post lst = [] for i in range(len(first)-len(s2)+1): s3 = "" t = 0 fin = True left = False right = False for j in range(len(s2)): if first[i+j]!=".. 2021. 6. 18. 숨바꼭질(다익스트라) bfs로도 풀수있는 문제지만 다익스트라의 연습을 위해 다익스트라를 사용하였다.사용알고리즘은 대부분 올바르게 구현하는 편인데 graph의 설정이라던지 구현에서는 다른 사소한 문제들에서 실수가 있는 편인것 같다. 해당부분은 graph를 n^2으로 구현해서 메모리초과가 처음에 났었고, 출력부분에서 distance를 mx로 처리하지않고 mx_idx를 설정해놓는등 실수가 있었다. (그런데 테스트케이스는 맞았다..) 프로그램 구현이라는게 원래 버그를 찾기 힘든 것이기도 하고 사소한 구현에서 실수가 나오기 쉽지만 이런 오류들을 빨리 잡을 수 있거나, 구현하기 전에 미리미리 생각을 다해보고 구현하려는 습관이 필요할 것 같다. 또한 사용알고리즘의 시간복잡도를 보다 정확히 알고 있어야겠다. import heapq impo.. 2021. 6. 18. 화성탐사(다익스트라) 우선순위큐를 통해 스타트지점부터 n-1,n-1 지점까지의 최단거리를 확인합니다.최단거리를 기준으로 한 거리를 큐에 계속 삽입시켜 주고 해당 노드들은 distance를 통해 방문했는지 안했는지를 파악하거나 기존 distance보다 현재 노드를 거쳐서 가는 거리가 더 작을 경우 갱신과 동시에 큐에 삽입해줍니다. import heapq import sys input = sys.stdin.readline INF = int(1e9) dx = [-1,1,0,0] dy = [0,0,1,1] # for tc in range(int(input())): n = int(input()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) dis.. 2021. 6. 17. 최종순위 (위상정렬) indegree[x] 가 0인 노드들을 순서대로 넣어주고 만약 큐가 비게된다면 cycle이 발생한 것, 큐의 사이즈가 2개이상이라면 경로가 2개이상인 개수가 발생한다는 것입니다. from collections import deque t = int(input()) while t: n = int(input()) indegree = [0]*(n+1) graph = [[False]*(n+1) for _ in range(n+1)] datas = list(map(int,input().split())) for i in range(n): for j in range(i+1,n): graph[datas[i]][datas[j]]=True indegree[datas[j]]+=1 m = int(input()) for i in .. 2021. 6. 17. 이전 1 2 3 4 5 다음