1. 개념 - 알고리즘에서의 탐욕법은 우리가 원하는 답을 얻기 위해서 재귀 호출과 똑같이 여러 개의 조각으로 쪼갠 후 각 단계마다 답의 한 부분을 만들어 간다는 점이다. ( 이 부분은 완전 탐색과 DP(동적계획법)와 똑같다. ) - 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 완전 탐색과 DP(동적계획법)와는 달리, 탐욕법을 사용하는 알고리즘은 지금 바로 가장 좋은 방법만을 선택한다. 2. 이해하기 - 예를 들어, 외판원 문제에서 사용한 DP(동적계획법)는 다음에 도착할 수 있는 도시들을 하나하나 검사해 보고, 남은 도시들을 모두 순회하는 데 필요한 거리의 합을 최소화하는 답을 찾았지만, 탐욕적인 알고리즘은 당장 다음 도시까지의 거리만을 최소화한다. - 그러므로, 탐욕적인 알고리즘은 ..

1. 문제 설명 (1) 위험한 살인마 두니발 박사가 감옥에서 탈출했다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 쉽사리 잡히지 않았다. (2) d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수를 찾았고, 그는 감옥에 남겨둔 노트를 분석하여 아래와 같은 가설을 세웠다. 1 두니발 박사는 검문을 피해 산길로만 이동한다. 2 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다. 3 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다. (3) 이 3개의 가설을 검증하기 위해 교도소로부터 산길로 연결된 N개 마을들의 지도를 아래의 그림과 같이 구했다. * ex) 지도의 3번에 교도소가 있다고 가정하면, 두니발 박사는 0번, 1번, 2번, 4번, ..

1. 문제 설명 (1) 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부른다. (2) N개의 정사각형으로 구성된 폴리오미노들을 만들려고 하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶다. * 세로로 단조라는 뜻은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 것이다. (3) 예를 들어, 아래의 그림 (a)는 정상적인 세로 단조 폴리오미노이지만, (b)는 파란색 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아니다. * (c)는 맨 오른쪽 아래 사각형이 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아니다. (4) N개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작..

( 아래의 사이트에 나오는 알고리즘을 먼저 보는 것을 추천합니다. ) 타일링 방법의 수 세기 (난이도: 하) (tistory.com) 타일링 방법의 수 세기 (난이도: 하) 1. 문제 설명 (1) 2xN 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제가 있다고 하자. (2) 타일들은 서로 겹쳐서는 안 되고 90도로 회전해서 쓸 수 있다. (3) 예를 들어, N=5라고 kind-coding.tistory.com 1. 문제 설명 (1) 아래의 그림과 같이 2xN 크기의 직사각형을 2x1 크기의 타일로 채우려고 한다. (2) 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있다. * 단 이 타일링 방법은 좌우 대칭이어서는 안 된다. (3) 위의 그림은 2x5 크기의 직사각형을..