algorithm
-
[Python]백준 13335번/트럭/queuealgorithm/문제 2023. 3. 29. 11:45
https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net ⚡️ 문제 설명 다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램 ⚡️ 해결 방법 bridge에 모든 트럭이 지나갈 때 까지 ( while bridge) 반복한다. 기다리고 있는 truck 이 있다면 현재 bridge 위에 있는 트럭의 무게 합 sum(..
-
[Python]백준 11441/합 구하기 / 누적합algorithm/문제 2022. 3. 14. 16:01
https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net ⚡️ 문제 설명 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램 ⚡️ 해결 방법 처음에 for _ in range(m): i,j=map(int,input().split()) print(sum(A[i-1:j])) 이렇게 코드를 작성하여 더하였더니 시간초과가 발생하였다. 시간초과를 해결하..
-
[Python]백준 11053/가장 긴 증가하는 부분 수열/LIS/dpalgorithm/문제 2022. 3. 13. 13:01
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ⚡️ 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. ⚡️ 해결 방법 가장 긴 증가하는 부분 수열 Logest Increasing Subsequence (LIS) 는 전형적인 dp의 문제이다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에..
-
[알고리즘] 완전탐색 / itertools / 순열 중복순열 조합 중복조합algorithm/개념 2022. 3. 12. 17:37
itertools 모듈 순열 permutations(list, r=None) 중복순열 product(list, repeat=1) 조합 combinations(list, r) 중복조합 combinations_with_replacement(list, r) # 순열 : permutations(list, r=None) from itertools import permutations random_list=['A','B','C'] resultA=permutations(random_list) resultB=permutations(random_list,2) print(list(resultA)) print(list(resultB)) 결과>> [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A',..
-
[Python]백준 14502/연구소 / 조합 / 배열 복사 copyalgorithm/문제 2022. 3. 12. 16:18
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ⚡️ 문제 설명 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램 ⚡️ 해결 방법 ex) 1 단계 : 빈칸인 위치 모두 찾기 empty_list = [] for empty_x in range(n): for empty_y in range(m): if initGraph[empty_x][empty_y] =..
-
[Python]백준 15649/N과 M(1)(2)(3)(4) / itertoolsalgorithm/문제 2022. 3. 12. 01:19
https://www.acmicpc.net/problem/15649 https://www.acmicpc.net/problem/15650 ⚡️ 문제 설명 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성 ⚡️ 해결 방법 파이썬 내장 모듈 itertools를 이용한다 2022.03.12 - [algorithm/개념] - [알고리즘] 완전탐색 / itertools / 순열 중복순열 조합 중복조합 [알고리즘] 완전탐색 / itertools / 순열 중복순열 조합 중복조합 itertools 모듈 순열 permutations(list, r=None) 중복순열 product(list, repeat=1) 조합 combinations(list, r) 중복조합 combi..
-
[Python]백준 9184/신나는 함수 실행/dp정리/top-downalgorithm/문제 2022. 3. 10. 19:04
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net ⚡️ 문제 설명 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c..