알고리즘57 [ 알고리즘 ] 동적 계획법 @ 왜 궁금한가? 맨날 DP DP 하는데 뭔지 해서,,, 그리고 알고리즘 문제에서 많이 나와서 한번 정리 하고 싶다는 생각,,, @ 공부 ## 동적 계획법이란 ( Dynamic Programming ) - 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결 작은 문제를 해결해서 큰 문제를 해결 > 재귀 호출 def getFibo(n) if n == 0 or n == 1 : return 1; else : return getFibo(n-1) + getFibo(n-2); 문제점: 값을 중복해서 계산 한다. 소문제를 여러번 계산 하는 경우가 많다. 분할정복법을 이용한 풀이가 아님 > 문제를 독립적으로 나누지 않았기 때문 이건 단순히 작은 나를 해결한 결과를 계속해서 써먹는다. F(n) 을 알기 위해서는 F(n.. 2019. 9. 27. [ 알고리즘 ] 분할정복법 @ 궁금한 이유 문제 풀이 방법중에 하나로 완전 탐색이 안될 경우 사용하는 방법중에 하나라서 공부하고 싶었다. @ 공부 분할 정복법( Divide & Conquer ) > 문제를 소문제로 분할 > 각각의 소문제를 해결 > 소문제의 해결 결과를 이용하여 전체 문제를 해결 # 대표적인 정렬 ## 합병정렬 ( Merge Sort ) > 재귀 호출을 이용한 대표적인 정렬 정확히 가운데를 나누고 나서 각각을 다시 합병정렬 해서 합친다. T(N) : N 개의 숫자를 정렬하는데 걸리는 시간 T(N) = 2* T(N/2) + O(N) > O(N log N) ## 퀵정렬 ( Quick Sort ) > 재귀호출을 이용한 대표적인 정렬 > 피벗 기준으로 작은 것은 왼쪽에 큰 것은 오른쪽으로 나누고 > 작은 문제 2개를 다시.. 2019. 9. 26. [ 알고리즘 ] 문제풀이 방법 @ 무엇인가? 수업을 듣던중 내용 정리 알고리즘은 문제 해결을 위한 절차 1. 문제를 정확히 이해해야 한다. ( 예제를 통해서 이해하려고 하지 말고 문제를 천천히 읽는 습관!! ) 2. 문제를 해결하는 알고리즘을 개발한다. - 알고리즘 설계 > 모든 경우 생각 > 어떻게 줄일수 있지? 꼭 전부 고려해야 하나? 3. 알고리즘이 문제를 해결한다는 것을 증명한다. ( 수학적으로 -> 뭐 이렇게 하면 되지 않나요? 이렇게 말하면 안된다. ) 4. 알고리즘이 제한시간 내에 동작한다는 것을 보인다. ( 시간 복잡도를 물어본다. ) 5. 알고리즘을 코드로 작성한다. 6. 제출 후 만점을 받고 매우 기뻐한다. 코딩 도중에 다시 풀어보고 왔다 갔다 한다면 3,4 번이 문제가 되서 그렇다. @ 연속 부분 최대합 연속된 부.. 2019. 9. 24. [ 알고리즘 ] 스택, 큐 의미 @ 왜 궁금한가 정말 많이 사용하는데 그럼 왜 사용하는지 그리고 어떤 의미이길래 이렇게 매번 중요하게 이야기를 하는지 알고 싶어서 확 정리 하고 싶어서 @ 공부 [ 내 의도에 맞게 쓸 줄 아는 능력이 중요하다. => 문제를 많이 풀어봐야 실력이 향상됨 ] ## 스택이란? 스택? 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 > 선형 자료 구조 - 스택과 큐가 대표적 ( 선 형태로 들어가기 때문에 ) > 스택은 자료구조 : 자료를 저장하는 구조 예) 올바른 괄호 찾기 스택에 넣는 괄호는 : 아직 짝을 찾지 못한 괄호 > 그럼 어떤 자료를 저장하는가? > "상태"가 들어간다. > 발자취를 기억하는 용도!! 이 말이 컴퓨터 공학에서 굉장히 중요하다. > .. 2019. 9. 23. 이전 1 2 3 4 5 6 ··· 15 다음
