전체 글
-
[알고리즘] 완전탐색 / 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..
-
[Python]백준 1309/동물원/dpalgorithm/문제 2022. 3. 3. 22:16
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net ⚡️ 문제 설명 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램 ⚡️ 해결 방법 #왼쪽에 있는 경우 dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901 #오른쪽에 있는 경우 dp[i][1]=(dp[i - 1][0] + dp[i - 1][2])%9901 #둘다 없는 경우 dp[i][2]=(dp[i - 1][0]+ dp[i - 1][1] + dp[i - 1][2])%9901 🟢 왼쪽에 있는 경우 = 전단계에서 오른쪽에 있는 경우 ☑️ + 그 전단계에서 둘다 없는 경우 dp[i][0]=(dp[..
-
[Python]백준 2579/계단오르기/dpalgorithm/문제 2022. 3. 3. 00:30
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ⚡️ 문제 설명 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램 ⚡️ 해결 방법 dp[..
-
[Python]백준 2644/촌수계산/dfs/bfsalgorithm/문제 2022. 2. 27. 12:05
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net ⚡️ 문제 설명 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. ⚡️ 해결 방법 visited 배열은 촌수를 계산할 때 사용할 것이다. 입력받은 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때는 -1을 출력해야 한다. 그러므로 초기 배열을 -1로 해준다. 그리고 처음시작하는 자기자신을 0으로 바꿔준..
-
[Python]백준 11726번/2×n 타일링/dpalgorithm/문제 2022. 2. 23. 17:16
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ⚡️ 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. ⚡️ 해결 방법 ⚡️ 코드 import sys input=sys.stdin.readline n=int(input()) dp=[0]*(n+1) for i in range(1,n+1): if(i==1): dp[i]=1 elif(i==2): dp[i]=2 else: dp[i]=dp[i-1]+dp[i-2] pri..