본문 바로가기

알고리즘18

백준 5052 전화번호 목록 파이썬 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 모든 문자열 비교를 해야 하나.. 그치만 시간초과가 날텐데... 하면서 고민했다. 그런데 정렬을 하게 되면 접두사가 같은 것끼리 뭉치게 된다. 이렇게 되면 n*n이 아니라 n번의 비교로 끝낼 수 있다. "정렬"을 잘 활용하자 import sys def solve(n, arr): for i in range(n - 1): l = min(len(arr[i - 1]), len(ar.. 2023. 8. 11.
백준 12886 돌그룹 파이썬 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 세 그룹이 같은 돌 개수를 가져야 한다. -> 전체 돌 개수가 3의 배수가 아니라면 불가능하다. (a, b, c) == (a, c, b) == (b, a, c) == (b, c, a) == (c, a, b) == (c, b, a) -> 순서는 상관없다. visited[a][b] : (a, b, total - a - b) 방문했다 표시 아래 코드와 같이 (a,b,c)의 경우, 추가적으로 6가지.. 2023. 8. 11.
백준 1577 도로의 개수 파이썬 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 처음에는 중학생 때인가 배웠던 것처럼 대각선으로 올라가면서 구해야 하기 때문에 그대로 구현해야 한다고 생각했다. 그런데 N*M이기 때문에 행렬이 ㅁ자라고 생각했을 때 ㄴ자로 시작하여 대각선으로 올라가면서 구했다. import sys N, M = map(int, sys.stdin.readline().split()) K = int(sys.stdin.readline()) working .. 2023. 8. 11.
백준 2157 여행 파이썬 dp풀이 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 기존에 풀지 못하고 dfs + dp 조합 해설을 확인했었다. import sys N, M, K = map(int, sys.stdin.readline().split()) # N: 1-N까지의 도시가 있다. # M: M개 이하의 도시를 지나는 여행을 계획 중이다 # K: 항로 개수 INF = -sys.maxsize def solution(.. 2023. 8. 10.
백준 2098 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스킹 + dp + dfs 1. 출발 도시는 어느 지점이든 상관없다. 어차피 구한 경로는 사이클을 이루기 때문. 2. 방문한 도시는 비트마스킹으로 표시한다. 3. dp에는 현재 도시에서 남은 도시들을 거쳐 다시 출발점으로 돌아오는 비용이 저장된다. dp[row][visit] = 현재 row 도시이며, 방문현황은 visit와 같고, 아직 방문하지 않은 도시들.. 2023. 8. 2.
[백준] 1039 교환 파이썬 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제가 bfs라고..? 하면서 풀이를 봤다 숫자이긴 하지만 어쨌든 문자열이고, 교환을 통해 완전 탐색을 진행해야 한다는 점에서 bfs를 사용한 것으로 보인다. 풀이를 보고 나니, 어렵지 않은 코드였다. 그냥 알고리즘 자체가 생각이 안 났음..ㅠ 그런데 풀이를 보다가 시간복잡도에 대한 의문이 들었다. import sys from collections import deque N, K = map(int, sys.stdin.readline().split()) def bf.. 2023. 7. 11.

티스토리툴바