1. 문제 설명 (1) 아래의 그림처럼 NxN 크기의 격자에 1부터 9까지의 정수를 쓴 게임판이 있다. (2) 이 게임의 목적은 게임판의 왼쪽 위칸에서 시작해서 게임판의 맨 오른쪽 아래칸 "끝" 쪽으로 도착하는 것이다. (3) 이때 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있으며, 중간에 게임판 밖으로 벗어나면 안 된다. (4) 문제는 게임판이 주어질 때 시작점에서 끝점까지 도달하는 방법이 존재하는 지를 확인하는 것이다. (5) 예를 들어, 아래의 그림처럼 위의 그림에서 마지막 2를 3으로 바꾸면 방법이 없다. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C(1

1. 개념 - 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. - 동적 계획법과 분할 정복의 차이는 문제를 나누는 방식에 있다. - 동적 계획법에서의 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. - 그렇게 하기 위해서는 이미 계산한 값을 저장해 둘 수 있는 캐시를 사용한다. * 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다. 2. 이해하기 - 동적 계획법 알고리즘을 이해하기 위해서 가장 유명한 이항 계수(binomial coefficient)의 계산을 예로 들어보겠다. - 이항 계수..

1. 문제 설명 (1) 팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 포옹합니다. (2) 아래의 그림은 행사 과정 일부를 보여줍니다. a~c는 세 명의 하이퍼시니어 멤버이고, 0~4는 다섯 명의 팬들입니다. (3) 하지만 하이퍼시니의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 합니다. (4) 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹 하는 일이 몇 번이나 있는지 계산하는 프로그램을 만드시오. 2. 입출력 조건 및 예제 입력 조건 (1) 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성한다. (2) M은 남자, F는 여자를 ..

1. 문제 설명 (1) 카라츠바 알고리즘은 정수 두 수를 절반으로 쪼개는 것으로부터 시작됩니다. (2) 다음 문제 설명은 아래의 그림을 보고 이해합니다. ( 이때, 카라츠바는 a x b를 네 개의 조각을 이용해 표현하면 위와 같이 표현할 수 있습니다. ( 이 방법에서는 두 큰 정수를 한 번 곱하는 대신 네 번 곱합니다. ) ( 이때, 10의 거듭제곱은 시프트 연산으로 구현하므로 곰셈으로 치지 않습니다. ) ( 이해를 돕기 위해 아래의 사진을 참고하세요. ) ( 그러나, 위 방법대로 네 번 곱하는 시간 복잡도를 구해보면 결국 O(N^2)이 됩니다. ) ( O(N^2) = 덧셈과 시프트 연산(O(N)) x 2/n길이 조각들의 곱셈 네 번 by 마스터 정리 ) ( 여기서 카라츠바가 발견한 것은 아래와 같이 네..