알고리즘/알고리즘 이론 정리10 구현(Implementation) 구현의 정의 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. (구현 관련 설명을 찾다보면 이그림은 무조건 있다) 구현 유형의 문제? 알고리즘은 간단하나 코드가 길어지는 문제 실수 연산을 다르고 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 2차원 배열(행렬Matrix)에서의 이동, 회전 등 까다로운 문제 특정한 라이브러리를 찾아서 사용해야 하는 문제 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 완전 탐색 유형 모든 경우의 수를 주저없이 다 계산하는 해결 방법이다. 시뮬레이션 유형 문제에서 제시한 알고리즘들을 한 단계의 차례대로 직접 수행해야 하는 문제이다. 코딩테스트에서의 구현 문제를 풀 때 알아야 할 것 메모.. 2023. 4. 11. 그리디(Greedy) 알고리즘 그리디 알고리즘의 정의 단어 그대로 번역하면 탐욕법인데 말 그대로 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 현재 상황에서지금 당장 좋은 것만 고른다. 지금 당장 가장 좋은 것만 고르기 때문에 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않은 풀이를 한다. 그리디 알고리즘 원리 여러 경우 중 하나 선택한다. 선택시 마다 최적이라고 생각되는것을 선택한다. 최종적인 해답에 도달한다. 그리디 알고리즘의 특징 한번 선택된 것은 번복하지 않는다. → 대부분의 탐욕 알고리즘들은 단순하며, 제한적인 문제들에 적용한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이다. → 하지만 선택들을 계속 수집해 최종적 해답을 만들었다고 해서, 최적이라는 보장은 없다. 따라서 사용 가능유무를 잘 알아야 한다.. 2023. 4. 11. 동적 계획법(다이나믹 프로그래밍, DynamicProgramming), 다른 알고리즘들과의 비교 재귀함수와 비교해 함께 공부하면 좋다. 동적 계획법의 정의 큰 문제를 작은 문제로 나누어 푸는 문제를 말한다. → 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 동적 계획법 사용 조건 DP는 항상 사용할 수 없기에 아래 사용 조건을 만족할 때 사용한다. 1. 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있다. → 최적 부분 구조(Optimal substructure) 2. 동일한 작은 문제를 반복적으로 해결한다. → 중복되는 부분 문제(Overlapping subproblem) Memoization 기법 이전에 풀었던 문제의 정답이나 결과 값을 저장하여, 이후의 문제를 풀 때 다시 계산하지 않고, 미리 계산된 값을 불러와서 문제를 해결하는 방법이다. →.. 2023. 4. 11. 재귀함수(Recursion) 동적 계획법(DP)와 비교해 함께 공부하면 좋다. 재귀함수의 정의 함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다. 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다. ➕분할 정복(Divide and Conquer) 방식의 하나로 재귀함수를 활용한다. 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘을 분할 정복 알고리즘이라고 한다. 재귀함수를 활용해 Top-Down(하향식 접근)해결 방식을 사용하는 특징이 있다. 재귀함수를 구현하는 두가지 방법 1. 재귀함수를 호출하는 부분을 상단에 두고 표현할 수 있다. # if문에서 보이는 것과 같이 일정한 조건을 만족하지 않으면 # 계속해서 자기 자신의 함수로 .. 2023. 4. 11. 이전 1 2 3 다음
