반응형

2024/09/29 3

[TIL] 그리디 알고리즘 Greedy Algorithm

그리디 알고리즘 Greedy Algorithm 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 알고리즘 설계 기법 항상 최적의 값을 보장하는 것이 아니라 최적의 값에 '근사한 값'을 목표로 한다  예시) 경로1 이 [ 1 - 1 - 1 - 100 ] 이고 경로2 가 [ 3 - 10 - 3 - 10 ] 일 때경로1 에서는 첫 세 단계에서 최적의 답을 선택했지만 최종 가중치는 103이고경로2 에서는 각 단계에서의 선택이 더 나은 결과를 가져와 최종 가중치가 더 작아진다이 때 경로1 에서의 선택이 그리디 방법론의 예시 그리디 알고리즘 주요 속성탐욕 선택 속성 Greedy Choice Property각 단계에서 '최선의 선택' 을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 ..

TIL/Python 2024.09.29

[정글] Week03 진행 내용

Week03 기간 2024.09.27 FRI - 10.03 THU 조원 ㅎㅇ ㅅㅈ  1. 문제 풀이No문제 알고리즘 분류난이도진행 여부 12748 피보나치수2동적 프로그래밍하진행21904 01타일동적 프로그래밍하진행39084 동전동적 프로그래밍중 49251 LCS동적 프로그래밍중진행512865 아주 평범한 배낭 동적 프로그래밍중 611049 행렬 곱셈 순서동적 프로그래밍중 711053 가장 긴 증가하는 부분 수열동적 프로그래밍중 82098 외판원 순회동적 프로그래밍상 92253 점프동적 프로그래밍상 1011047 동전 0그리디하 111541 잃어버린 괄호그리디하 121931 회의실 배정그리디중 131946 신입사원그리디중 141700 멀티탭 스케줄링그리디상 159249 최장 공통 부분 문자열도전?상   ..

[백준] 11726 2xn 타일 Python

1. 문제2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오 2. 요구사항시간 제한 1초메모리 제한 256 MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식이것도 n = 7 까지 모든 경우의 수를 계산해 봤는데 아니나 다를까 피보나치였고n= 1 는 1, n = 2 는 2 를 초기값으로, n = 3 이상은 n-1 과 n-2 합으로 계산했다4. 코드 구현# 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 # 10,007 로 나눈 나머지를 출력한다 # 1

알고리즘 2024.09.29
반응형