[백준] 12865 <DP> 평범한 배낭 - python
* 핵심 아이디어 : K까지 모든 무게의 최대가치 저장하기 * 기본 식 https://badassdev.tistory.com/20 [백준] 12865번: 평범한 배낭( 파이썬, 쉬운 설명, 코린이 버전 ) *비범한 배낭 주의 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤.. badassdev.tistory.com https://suri78.tistory.com/2 [백준알고리즘] 12865번: 평범한 배낭 -Python [백준알고리즘] 12865번: 평범한 배낭 -Python https://..
- .index() 함수로 인덱스를 찾아가면서 풀었더니 시간초과가 나왔다. - 딕셔너리로 바로바로 접근해야 시간내에 해결할 수 있다. - POINT : dict(zip(enroll, referral)) from math import trunc # 1.아이디어 # - seller 순서대로 amount연결해 이익 값 구하고, enroll에서의 순서값을 구해, referral순서로 추천인 찾아 10%배분. # - 이익값 저장할 List 초기화.(순서는 enroll) # - 종료조건 : referral 이'-' or total 의 10%가 1미만인 경우 total그대로 salary에 저장후 종료 def solution(enroll, referral, seller, amount): salary = dict(zip..
문제 https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 풀이방법 https://tooo1.tistory.com/579 [프로그래머스] 코딩테스트 연습 : 양과 늑대 - PYTHON[파이썬] https://programmers.co.kr/learn/courses/3..
- 2중for문이 있다. 최대한 줄이는게 좋겠다. - 딕셔너리 사용법 import math n_time = {} def car_f(n,f): global n_time if n in n_time: n_time[n] = n_time[n] + f else: n_time[n] = f def solution(fees, records): answer = [] at, af, at2, af2 = fees for i in range(len(records)): record = records[i] t, n, w = record.split() h, m = map(int,t.split(':')) if w == 'IN': for j in range(len(records)): record2 = records[j] t2, n2, w..
1 - 2 - 4 : 1~2까지의 최단거리, 2~4까지의 최단거리 구하기 * 2에서 모든노드까지의 최단거리 구하여, dist[1], dist[4] 합치기. 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하..
문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영..
플로이드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 38042 15405 10975 41.891% 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타..
[백준] 1753 <다익스트라> 최단경로 - python
[ 최단경로 알고리즘 ] 1. BFS - 간선의 가중치가 모두 같을때 2. 다익스트라 - 간선의 가중치가 다르고, 한 노드에서 모든 노드까지의 최단거리 3. 플로이드 - 간선의 가중치가 다르고, 모든 노드에서 모든 노드까지의 최단거리 그리디한 방법으로 동작하는 최단거리 알고리즘이다. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 먼저 선택해 연산을 해나가기 때문에 최단거리 가장 짧은 노드 선택시 그 노드까지의 거리는 더이상 바뀌지 않기 때문이다. 즉 각 노드를 거쳐가는 경우를 확인해 테이블을 갱신할지 안할지 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 ..