자료구조 스터디10 자료구조 여름방학 4주차 섹션 9동적 계획법(DP, 다이나믹 프로그램)복잡한 문제를 여러개의 간단한 문제로 분리하여 해결하는 것 point..큰 문제를 작은 문제로 나눌 수 있어야함작은 문제들의 결과값이 항상 같아야함작은 문제들을 최초의 한번만 계산하고 DP 테이블에 저장다시 같은 작은 문제가 발생했을 때 다시 계산하는 것이 아니라 테이블에 저장 된 값을 활용 ex(피보나치 수열) a(n+3)=a(n+1)+a(n+2)수열을 구하기 위해 모든 값을 계산하는게 아니라 점화식을 이용하여 계산함동적 계획법으로 풀이할 수 있는가?== 작은 문제로 나눌 수 있나? 값이 항상 같은가? 6번째 피보나치 수열의 값은 5번쨰 피보나치 수열의 값+4번쨰 피보나치 수열의 값수열의 값은 항상 같음 동적 계획법으로 풀이 가능하고 수열의 값은 항상 같은 .. 2024. 7. 25. 자료구조 여름방학 3주차 조합조합 자체로 코딩테스트에 많이 등장함점화식, 동적 계획법을 이해하는데 기초가 되는 내용임 순열: n개의 숫자에서 r개를 뽑아 나열하는 경우의 .조합: 순열과 다르게 순서를 고려하지 않음. 분모에 추가된 r!부분은 순서를 제거하는 역할. 조합의 점화식1. 특정 문제 가정 5개중에 3개 선택2. 모든 부분 문제가 해결된 상황이라 가정하고 지금 문제 생각 5를 선택했을 때->앞에서 2개의 수가 선택된 상황 4C2 5를 선택하지 않음-> 앞에서 3개의 수가 선택된 상황 4C3 따라서 5C3 = 4C3+4C23. 일반화 점화식 도출 백준 11051 이항계수: 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. 2024. 7. 18. 자료구조 여름방학 2주차 보호되어 있는 글 입니다. 2024. 7. 14. 자료구조 여름방학 1주차 트리 그래프의 특수한 형태로 노드와 엣지로 연결된다. 순환 구조가 없고 1개의 루트노드가 존재한다. 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 노드: 데이터의 인덱스와 값을 표현엣지:노드사이의 연결루트: 최상위 노드리프노드:최하위에 존재하는 노드자식노드: 두 노드 사이에서 하위노드에 해당하는 노드 tree 문제:1) 그래프 풀이 dfs, bfs 문제2) tree만을 위한 문제 이진트리, 세그먼트 트리,lca (최소 공통 조상) 1차원 배열로 트리를 표현 (자식으로 이동할 때는 index*2 or index*2+1 부모로 이동할 때는 index/2...) [백준 11725] 인접리스트 자료구조 사용일반적으로 dfs, bfs사용dfs를 사용해 쉽게 해결 가능 깊이우선 탐.. 2024. 7. 7. 이전 1 2 3 다음
