본문 바로가기

파이썬15

[백준 30805번] 사전 순 최대 공통 부분 수열 (Python) import sysinput = sys.stdin.readlinen = int(input())a = list(map(int, input().split()))m = int(input())b = list(map(int, input().split()))ans = []while a and b: # a와 b 모두 항목이 있는 동안 실행 max_a = max(a) max_b = max(b) if max_a == max_b: ans.append(max_a) # 최댓값이 같은 경우, 최댓값 이후의 요소만 남기기 a = a[a.index(max_a)+1:] b = b[b.index(max_b)+1:] elif max_a > max_b: .. 2024. 7. 9.
[백준 11404번] 플로이드 (파이썬 풀이) https://www.acmicpc.net/problem/11404 문제 문제 이해 Dijkstra로 풀려고 했는데, 시간초과가 났다. 문제의 이름처럼 플로이드 - 위셜 알고리즘을 써서 풀어야 하나보다. chatGPT 에게 그게 뭐냐고 물어봤다. 대답은 잘한다. 코드로 나타내면 이해가 쉽다. 모든 노드 쌍간의 최단경로를 한번의 구할 수 있고 음의 가중치도 가능하다는 장점이 있다. graph는 어떻게 나타내느냐 하면, graph = [ [0, 1, 1, inf, inf], [1, 0, 1, 1, inf], [1, 1, 0, inf, 1], [inf, 1, inf, 0, 1], [inf, inf, 1, 1, 0] ] 이런식으로 나타낸다고 한다. 문제에 적용해 보자. 문제 풀이 import sys input .. 2023. 5. 5.
[백준 1753번] 최단경로 (Python 풀이) https://www.acmicpc.net/problem/1753 문제 문제 이해 먼저, 문제의 제목처럼 최단경로를 구하는 문제이다. 선뜻, BFS (너비우선탐색)이 생각나지만, 이 문제는 가중치가 있다. 1, 0 으로 이루어진 가중치라면 BFS풀이가 가능하나, 1을 초과하는 가중치가 있기 때문에 이 문제는 BFS로 풀지 못한다. 즉, Dijkstra (다익스트라) 알고리즘을 사용한다. 첫째 줄에는 노드 수, 간선 수가 나온다. 여기서 간선이라고 하는 것은 가중치가 있고 방향이 있는 화살표이다. (양쪽을 향하는 화살표가 아니란 말이다.) 예제 입력을 그림으로 나타내면 저런 형태를 가진다. 풀이 방법 1. 먼저 간선(v)과 가중치(e)가 들어가는 edge 배열을 만든다.위의 예제 입력의 edge 배열은ed.. 2023. 5. 4.
KMP 알고리즘 KMP 알고리즘은 빠른 문자열 검색을 돕는 알고리즘이다. 찾고자 하는 문자열을 pattern 이라고 하고 모든 문장을 all string 라고 하자. KMP 알고리즘을 구현하기 위해 해야할 것이 있다. 1. Pattern 문자열을 이용해 pi(파이)배열을 만들어야 한다. 2. pi 배열을 이용해 빠른 문자열을 검색해준다. pi배열 이란, Pattern 문자열에 있는 접두사 (Prefix) 와 접미사 (Suffix)가 같아 지는 최대 길이를 나열해 놓은 배열이다. 말로 설명하지니 좀 어려우므로 아래 그림을 통해 확인해보자. 예를 들어, pattern이 "abcdabc" 라면 단어의 길이가 7인데, 1개씩 늘려가며 접두사와 접미사가 겹치는 최대 길이를 나타내 보면, pi배열은 [0, 0, 0, 0, 1, 2.. 2023. 4. 26.

티스토리툴바