본문 바로가기

알고리즘

 (233)
백준 1700 멀티탭 스케줄링 파이썬 풀이, 반례 난이도 : 골드1 풀이일 : 2404077 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 캡쳐 아이디어 비어있는 플러그가 있다면, 현재 사용할 제품을 그냥 연결한다. 비어있는 플러그가 없다면, 현재 연결 되어있는 제품의 플러그를 한 개 제거하고 제거 횟수를 센다. 사용이 끝나 더이상 사용하지 않을 제품을 우선적으로 제거한다. 사용이 끝난 제품이 없다면, 다음 사용순서가 가장 많이 남은 제품을 제거한다. 전체 풀이코드 import sys ..
백준 2294 동전 2 파이썬 풀이 난이도 : 골드5 풀이일 : 2404066 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 풀이코드 import sys n, k = map(int, sys.stdin.readline().split()) coins = [] dp = [float('inf')] * (k + 1) # 초기값 무한 dp[0] = 0 # 0 만드는 동전 개수 for _ in range(n): coins.append(int(sys.st..
백준 1106 호텔 파이썬 풀이 난이도 : 골드5 풀이일 : 2404055 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys C, N = map(int, sys.stdin.readline().split()) ad = [] # 비용 정보 없음, 고객의 수 최대 100명 dp = [int(1e9)] * (C + 100) dp[0] = 0 # 0 초기화 for _ in range(N): cost, peop..
백준 9935 문자열 폭발 파이썬 풀이 난이도 : 골드4 풀이일 : 2404044 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 오답코드 -> 시간초과 import sys string = sys.stdin.readline().strip() target = sys.stdin.readline().strip() N = len(target) result = [] for alphabet in string: result.append..
백준 2293 동전 1 파이썬 풀이 난이도 : 골드5 풀이일 : 2404033 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys n, k = map(int, sys.stdin.readline().split()) coins = [] # 동전 종류 for _ in range(n): coin = int(sys.stdin.readline()) coins.append(coin) dp = [0] * (k + 1) # 경..
백준 1939 중량제한 파이썬 풀이 난이도 : 골드3 풀이일 : 2404022 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys, heapq N, M = map(int, sys.stdin.readline().split()) loads = [[] for _ in range(N + 1)] # 다리 연결 및 중량제한 for _ in range(M): # ..
백준 14267 회사 문화 1 파이썬 풀이 난이도 : 골드 4 풀이일 : 2404011 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys sys.setrecursionlimit(10 ** 9) # 내 자식들에게 나의 칭찬 점수 누적합산 def DFS(x): for nx in tree[x]: result[nx] += result[x] DFS(nx) return n, m = map(int, sys.stdin.read..
백준 2109 순회강연 파이썬 풀이 난이도 : 골드3 풀이일 : 2403295 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys, heapq n = int(sys.stdin.readline()) order = [] # 마감일 정렬 들어온 제안 choice = [] # 강연료 정렬 선택한 제안 for _ in range(n): p, d = map(int, sys.stdin...
백준 1595 북쪽나라의 도로 파이썬 풀이 난이도 : 골드4 풀이일 : 2403284 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys from collections import deque def BFS(n): queue = deque([n]) visited = [-1] * 10001 # 방문 확인 및 거리 저장 visited[n] = 0 # 현재 노드까지의 거리 설정 while queue: x = queue.pop..
백준 1240 노드사이의 거리 파이썬 풀이 난이도 : 골드5 풀이일 : 2403273 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys from collections import deque def sol(n, m): queue = deque() queue.append(n) while queue: x = queue.popleft() for nx, add in tree[x]: if nx == m: ..
백준 17836 공주님을 구해라! 파이썬 풀이 난이도 : 골드5 풀이일 : 2403262 https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제캡쳐 풀이 코드 import sys from collections import deque N, M, T = list(map(int, sys.stdin.readline().split())) castle = [list(map(int, sys.stdin.readline().split())) for _ in..
백준 1135 뉴스 전하기 파이썬 풀이 난이도 : 골드2 풀이일 : 2403251 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys def dp(n): # 이전에 검사한 적이 있다면 검사 결과 반환 종료 if time[n] > -1: return time[n] # 해당 노드의 자식이 없다면 0 저장 후 0 반환 종료 if not children[n]: time[n] = 0 return 0 # 모든 자식 노드 방문 소..
백준 1202 보석 도둑 파이썬 풀이 난이도 : 골드2 풀이일 : 2403247 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 오답 코드 -> 3% 틀렸습니다. import sys, heapq N, K = list(map(int, sys.stdin.readline().split())) jewels = [] bags = [] value = [] for _ in range(N)..
백준 13904 과제 파이썬 풀이 난이도 : 골드3 풀이일 : 2403192 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys, heapq N = int(sys.stdin.readline()) queue = [] # 마감일 우선 과제 정보 정렬 total = [] # 점수 낮은순 정렬 for _ in range(N): limit, score = map(int, sys.stdin.readline().split()) heapq.heappush(queue..
백준 9466 텀 프로젝트 파이썬 풀이 난이도 : 골드3 풀이일 : 2401281 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys from collections import deque # 사이클 확인 def iscycle(n): # 지목된 학생들 team = dict() team[n] = 0 queue = deque([(n, 0)]) check[n] = True while queue: x, idx = queue.p..
백준 10815 숫자 카드 자바스크립트 풀이 난이도 : 실버5 풀이일 : 2403166 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 let input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); const N = parseInt(input[0]); // 카드를 저장할 배열 const set = new Set(); // 가지고..
백준 2845 파티가 끝나고 난 뒤 자바스크립트 풀이 난이도 : 브론즈4 풀이일 : 2403144 https://www.acmicpc.net/problem/2845 2845번: 파티가 끝나고 난 뒤 파티가 끝나고 나면, 사람들은 누가 파티에 왔는지와 얼마나 많은 사람들이 왔는지를 궁금해한다. 보통 파티는 매우 크게 열리기 때문에, 정확하게 몇 명이 참가했는지 알 수가 없다. 지난주 토 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 let input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); var [L, P] = input[0].split(' ').map(Number); var people = L * P; var news = input[1]...
백준 1520 내리막 길 파이썬 풀이 난이도 : 골드3 풀이일 : 2403133 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys sys.setrecursionlimit(10**9) def sol(i, j): # 목적지 도착 시 1 반환 if i == N - 1 and j == M - 1: return 1 # 방문한 적이 있다면 dp[i][j] 반환 if dp[i][j] != -1: return dp[i]..
백준 15665 N과 M(11) 자바 풀이 난이도 : 실버2 풀이일 : 2403096 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import java.util.Scanner; import java.util.Arrays; import java.util.Set; import java.util.LinkedHashSet; public class Main { static int N, M; static int[] nums, resu..
백준 11437 LCA 파이썬 풀이 난이도 : 골드3 풀이일 : 2403122 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 -> 0% 시간초과 import sys from collections import deque def find(n, m): if parent[n] == m: return print(m) temp = deque([n]) while temp: i = temp.popleft() for ni in..

티스토리툴바