본문 바로가기

Algorithm9

Knapsack - 제한 용량에 최대 가치 채우기 Knapsack 문제 일반화10kg 배낭에 넣을 수 있는 물건이 4개가 있고 각 물건의 무게와 가치는 다음과 같다.무게 : 5, 4, 6, 3가치 : 10, 40, 30, 50여기서 각 물건은 넣거나 넣지 않을 수 있다. 최대 가치를 구해야 하므로 가장 작은 문제 부터 최대 가치를 만들어서 10kg 문제까지 해결해보자여기서 가장 작은 문제는 1kg 배낭에 채울 수 있는 최대 가치라고 정의하자. 1. (5, 10) 의 물건1 ~ 4kg 배낭엔 채울 수 없으므로 가치는 05kg 배낭으로 가치는 10 2. (5,10) (4,40) 의 물건1 ~ 3kg 배낭엔 채울 수 없으므로 가치는 04 ~ 8kg 배낭엔 (4, 40)을 채울 수 있으므로 가치는 409 ~ 10kg 배낭엔 (4, 40), (5, 10) 추가할.. 2024. 8. 23.

[알고리즘] 개미 전사 (DP-이코테) 문제 유형 : 다이나믹 프로그래밍 문제 설명(요약) : 최소한 한 칸 이상 떨어진 인덱스의 요소들을 합하여 나가는 과정 후 최댓값을 구하는 문제 접근 : {3, 5, 4, 5, 6, 8, 4} 예제 케이스 만들기 현재 인덱스의 요소는 -2칸 or -3칸 떨어진 인덱스의 요소로부터 올 수 밖에 없음 최댓값을 구하기 위해선 -2칸 or -3칸 떨어진 인덱스와 현재 값과의 합중 최댓값으로 갱신되어야 함 점화식 추론 : A[i] = max(A([i-2] + A[i]),(A[i-3] + A[i])) 결론 : dp 리스트의 마지막 인덱스와 그 전 인덱스 중 최댓값을 구하면 원하는 답을 구할 수 있음 코드 구현 : n = int(input()) dp = list(map(int,input().split())) dp[2.. 2023. 4. 18.

[알고리즘] 치킨 배달 (Brute force-GoldⅤ) 📘 알고리즘 노트 문제를 해결하기 위해 구현해야되는 로직 정리 필요한 로직 ✨ m개의 치킨집을 무작위로 선택할 combination 로직 ✨ 선택된 치킨집과 집의 최소 치킨거리계산 ✨ 치킨거리를 누적하면서 조합이 바뀔때마다 최소 누적치킨거리로 갱신 문제 설명 최대 M개의 치킨집을 골라 치킨거리의 합의 최솟값을 구하는 문제 조건 집과 치킨집의 좌표를 (r1,c1) (r2,c2)라고 했을 때 두 점사이의 거리는 | r1 - r2 | + | c1 - c2 |로 계산 제한사항 N : (2 2023. 3. 22.

[알고리즘] 자물쇠와 열쇠 (Brute force-LV3) 📘 알고리즘 노트 문제를 풀기위해 구현해야되는 기능 정리 필요한 기능 ✨ 2차원 리스트를 회전하는 기능 ✨ 자물쇠의 요소가 1로만 채워져 있는지 확인하는 기능 ✨ 자물쇠 배열확장 후 중앙부분에 기존의 자물쇠 넣기 문제 설명 주어진 조건으로 자물쇠를 풀수 있는지 없는지 확인하는 문제 자물쇠 N X N 그리고열쇠 M X M 는 2차원 행렬 조건 열쇠는 회전과 이동이 가능 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 정답 제한사항 key = (3 MxM # 열쇠는 회전과 이동 가능 # 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 정답 def rotate_a_matrix_by_90_degree(a): n = len(a) # 행 길이 m = len(a[0]) # 열 길이 result = [[.. 2023. 3. 21.

[알고리즘] 최대점수구하기 (DFS-재귀) 목적: DFS 알고리즘의 재귀적 특성을 이해하기 위해서 문제 설명(요약): N개의 문제에 대한 각 점수와 각 문제를 풀기 위한 시간이 주어졌을 때, 정해진 M시간 내 에서의 최대 점수를 찾는문제 해결전략: 노드를 탐색하며(L++) 주어진 입력(점수,시간)을 쓴다 안쓴다 (sum++ or sum, time ++ or time) -> 재귀 함수로 구현 재귀함수에 대한 이해: arr = [[점수,시간],[점수,시간],,,,,,[점수,시간]] DFS(L+1,sum+arr[L][0],time+arr[L][1]) # 노드를 사용한다 1번 DFS(L+1,sum,time) # 노드를 사용하지 않는다 2번 1번 함수를 호출 했을 때 -> 만약에 시간이 초과되면 return 후 돌아와서 2번함수 호출 (stac.. 2023. 3. 18.

[알고리즘] 적록색약 (BFS-GoldⅤ) 목적: BFS 알고리즘의 Queue 자료구조를 이해하기 위해서 문제 설명(요약): N*N 행렬에 R,G,B 문자열(색상) 요소가 들어있다. 상하좌우를 탐색하며 인접하고 같은 색상끼리 구역을 나누어 총 구역의 개수를 구하는 문제 이때 적록색약인 사람은 R,G를 구분하지 못한다. 해결 전략: 1. 적록색약인 Case와 아닌 Case를 나누어 노드를 탐색 (적록색약인 경우는 'G'요소를 'R'로 할당해줌) 2. 주변의 인접한 노드를 탐색하기 위하여 BFS(너비 우선 탐색) 알고리즘을 사용 3. 방문했던 요소는 탐색하지 않는다. 4. BFS가 한번 돌때마다 cnt +=1 Queue자료구조에 대한 이해: queue 안의 모든 요소가 없어질 때 까지 while문을 돌림 상하좌우로 탐색한 모든 요소가 co.. 2023. 3. 18.

이전 1 2 다음

티스토리툴바