정리 노트

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 해결 과정 분할(Divide): 문제를 2개 이상의 같은 형식의 작은 문제들로 나눕니다. 정복(Conquer): 나눠진 작은 문제들은 재귀적으로 해결합니다. 나눠서 문제를 해결할 필요가 없을 때까지 계속 분할해 나갑니다. 통합(Combine): 풀어낸 작은 문제들의 해답들을 합쳐서 원래 문제의 해답으로 만듭니다. 위에 적은 과정이 주로 분할 정복 기법을 사용해 문제를 풀어나가는 과정입니다. 정복 과정에서 문제들을 재귀적으로 해결해 나가기 때문에 재귀를 이용해서 구현하게 됩니다. 따라서 재귀에 대해 어느 정도 아셔야 합니다. ..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 수학에서 얘기하는 재귀 어떤 함수를 정의하는데 자기 자신의 함수를 이용하는 것을 재귀라고 합니다. 재귀를 흔히 점화식의 형태로 나타낼 수 있습니다. 예를 들어 자연수 n에 대한 함수 f(n) = n! 가 있다고 합시다. 이를 아래와 같이 정의할 수 있습니다. 이 정의를 보면 n! 를 정의하는데 다시 (n - 1)!로 정의합니다. n > 0일 때 식을 풀어써봅시다. n * (n - 1)! = n * (n - 1) * (n - 2)! = n * (n - 1) * (n - 2) * (n - 3)! =... = n * (n - 1) * ..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 레벨 1 문제들만 풀다가 오랜만에 레벨 2 문제를 건드려봤다. 대놓고 분류가 DFS/BFS로 되어있었으니 망정이지 아니었으면 풀이 방향도 잡지 못했을 것 같다... 풀어내고 다른 사람의 풀이를 보니 200여 명이 열광하는 코드가 떡하니 나와있었다. 그 코드는 정말... 아름다웠다! 재귀를 정말 아름답게 사용했다고 나는 생각한다. 그래서 일..