본문 바로가기

코딩문제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.
[백준 15663번] N과 M (9) {Python 풀이} 이 문제는 itertools 모듈의 permutations 함수를 이용하여 해결할 수 있습니다. permutations 함수는 주어진 iterable에서 지정된 길이의 순열을 구하는 함수입니다. from itertools import permutations import sys input = sys.stdin.readline n, m = map(int, input().split()) numbers = list(map(int, input().split())) # 주어진 수열을 사전순으로 정렬합니다. numbers.sort() # permutations 함수를 이용하여 길이가 M인 순열을 구합니다. # set을 이용하여 중복되는 수열을 제거합니다. result = set(permutations(numbers,.. 2023. 5. 2.

티스토리툴바