728x90 알고리즘3 DP 개념과 문제풀이 방식 이 DP 아님🌟DPDynamic Programming동적 계획법문제를 작은 문제들로 쪼개어 이전에 구해놨던 값을 현재의 풀이에 활용할 수 있을 때 이를 동적계획법이라고 함.📌응용 예시경우의 수(동전들로 금액 만드는 모든 경우의 수) 조합, 순열모든 경우로부터 최대 최소(가장 적은 동전으로 금액 만들기, LIS(O^N), 냅색 문제)수열 문제(피보나치, 카탈린.. 수열의 응용도 결국 경우의 수로 들어가지만)📌구현 방식1. Bottom-up (for문 구현)현재 상태 값의 갱신을 위해, 현재 상태가 될 수 있는 이전 상태들의 값을 본다.바텀업으로 값을 채워주는 것을 Tabulation 이라고 함2. Top-down (재귀함수 구현)현재 상태 값의 갱신을 위해, 현재 상태로부터 될 수 있는 다음 상태들의.. 2024. 8. 20. 포인터, alias 개념과 직접 구현 해시 새내기 때 나를 괴롭히던 포인터&&*보는 이에 따라 별보는 사람 혹은 참조와 포인터로 보일 수 있다.🌟포인터와 Alias📌포인터선언과 초기화포인터는 자료형 뒤에 *를 붙여서 선언한다.p라는 포인터는 int형 변수의 주소를 담을 수 있다.변수의 주소는 변수명 앞에 &를 붙여서 가져온다.int* p; // 포인터 선언int a = 5;p = &a; // a의 주소를 담기printf("%d", p); // a의 주소가 출력됨printf("%d", *p); // 5 (a의 값이 출력됨)값을 가져오는 방법asterisk(*)을 포인터 변수 앞에 붙이면 포인터에 담긴 주소를 가지는 변수의 값을 가져올 수 있다.*p를 print하게 되면 5가 출력된다.📌별명(Alias)alias는 어떤 변수의 주소를 똑같이 가.. 2024. 8. 20. 외판원 순회(TSP) 알고리즘 옥장판 파는 세일즈맨...?🚶🏻♂Traveling Salesman Problem외판원순회는 대표적인 CS 문제 중 하나이다.다항 시간에 풀 수 없는 NP 문제로 유명하다. (NP는 다항시간에 풀 수 없으나 다항시간에 검산이 가능함.)최소 비용을 가지는 원순열 을 찾는 문제이다.결론부터 말하자면,💡외판원 순회는 DP + DFS이다.📌조건외판원은 모든 도시를 최소비용으로 한 번씩만 방문하여 처음 도시로 돌아와야 한다.*이는 해밀턴 경로(Hamilton circuit) 라고 부르며, 한붓그리기와 같다.각각의 도시 간의 경로는 방향성이 있고, 비용이 존재하며 어떤 도시들 간에는 경로가 없을 수도 있다.항상 최적의 경로가 존재한다.📌알 수 있는 사실최적의 경로는 어떤 정점에서 시작하든 사이클을 만들어 .. 2024. 8. 20. 이전 1 다음 728x90
