문제 해결 알고리즘 기초/완전 탐색10 [알고스팟] 소풍 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 소풍(링크) 재귀적으로 생각하기 학생의 명단이 주어지면 둘 씩 짝 짓는 경우의 수를 계산한다. 두 학생을 짝 짓는 작업을 하나의 작업 조각으로 보면 재귀 함수는 아직 짝을 찾지 못한 학생의 명단이 주어질 때 두 학생을 짝 지어주는 작업을 반복한다. 중복으로 세는 문제 1번 3번을 짝 짓는 것과 3번 1번을 짝 짓는 것은 별개의 경우로 세면 안 된다. 이처럼 중복으로 세는 문제를 다루는 한가지 방법은 항상 특정 형태의 답만을 세는 것이다. (조합을 구할 때 동일한 원소들이 순서가 다르게 선택되어 별개의 경우가 되지 않도록 고르는 순서를 강제하는 것과 같다.) 무식하게 풀 수 있을까? 이 문제가 가장 많은 답을 가지는 입력은 열 명의 학생이 모두.. 2020. 7. 30. [알고스팟] 보글 게임 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 보글 게임(링크) 재귀적으로 생각하기 주어지는 단어를 게임판의 알파벳으로 만들 수 있는지 판별하므로 단어의 알파벳 하나와 게임판의 알파벳이 일치하는지 검사하는 작업 조각을 단어의 알파벳 개수만큼 반복해 문제를 해결한다. 단어의 맨 앞 알파벳과 현재 게임판 위치의 알파벳을 비교해 일치하면 나머지 글자로 이루어진 단어를 넘기며 재귀 호출한다. 즉, 재귀 함수는 인자로 받는 단어의 첫 알파벳과 게임판의 알파벳이 일치하는지 확인하는 동일한 작업을 반복한다. 재귀 호출에 필요한 입력 찾아야 할 단어와 현재 검사해야 할 게임판의 좌표를 인자로 받는다. 시간 복잡도 시간 안에 동작하는지 확인하기 위해 최악의 경우를 고려해보자. 길이가 n 인 단어가 주어질.. 2020. 7. 21. 완전 탐색으로 n 개 중 r 개 고르기 (조합) ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 조합 서로 다른 n 개 원소를 가지는 집합에서 순서에 상관없이 r 개의 원소를 선택하는 경우의 수를 계산한다. 이는 n 개 원소를 가지는 집합에서 길이가 r 인 부분 집합을 고르는 문제 그리고 이항 계수와 같다. 완전 탐색으로 풀 수 있을까? 이항 계수의 공식은 n choose r = n! / (r! * (n - r)!) 이고 이는 n 개 원소 중 r 개를 고르는 조합의 가짓수와 같다. 따라서, 주어지는 n 과 r 을 통해 수행 가능성을 짐작해 볼 수 있다. 재귀적으로 생각해보기 재귀 호출을 통해 문제를 해결하려면 동일한 형태의 작업으로 나누어 해결해야 하므로 여러개의 유사한 작업 조각으로 나눈다. r 개를 골라야 하므로 원소를 고르는 작업을.. 2020. 7. 21. 완전 탐색 알고리즘에 대해서 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 완전 탐색 간단한 문제를 복잡하게 푸는 것은 효율적이지 않다. 따라서, 문제를 마주하면 가장 먼저 "무식하게 풀 수 있을까?" 를 고민해야 한다. 무식하게 푼다는 것은 컴퓨터의 연산 능력에 기대어 가능한 경우의 수를 일일이 나열하며 답을 찾는 것이다. 완전 탐색의 절차 (재귀 호출) 주어지는 조건의 최대 크기로 입력했을 때 시간 내에 계산이 되는지 짐작한다. 가능하면 풀어야 할 문제를 유사한 형태의 작업 조각으로 나눈다. 그 중 하나로 답의 일부를 만들고 나머지 답을 재귀 호출을 통해 완성한다. 작업 조각이 하나 남거나, 하나도 남지 않은 경우 답을 생성한 것이므로 이를 기저 사례로 선택해 처리한다. (재귀 호출을 언제 멈출지 결정.) 예제:.. 2020. 7. 21. 이전 1 2 다음