본문 바로가기

종만북3

[종만북] 6.5 재귀호출과 완전탐색[게임판 덮기] 게임판 덮기 문제는 3칸짜리 블록을 H x W 의 보드에 몇 가지의 방법으로 맞출수 있는지 구하는 경우의 수 문제이다. 블록은 총 4가지 모양인데 ㄱ, ㄴ, ┌, ┘ 이런 모양으로 되어있다. 사고 과정 0. 블록이 들어가는 갯수가 3의 배수가 아니면 0을 리턴 1. 특정 지점 row와 col에서 위 4가지 모양에 대한 위치를 구하는 배열을 구한다. 2. 해당 모양에 대한 조건이 일치하면 블록을 그리고 일치하지 않으면 다음을 진행 3. 기존 상태를 복구하여 다른 모양일때를 구한다. 4. 모든 맵이 블록으로 꽉차면 리턴한다. 이렇게 사고과정을 하였고 구현을 진행했다. 그런데 구현중에 값이 너무 크게 나와 뭔가 잘못됐다는 걸 느꼇다. 나는 한 블록을 그리고 다음 블록을 그릴 위치를 구할때 i와 j를 0부터 시.. 2021. 9. 29.
[종만북] 6.4 재귀호출과 완전탐색[소풍] 소풍 문제는 서로 친구들끼리 짝을 지어주는 경우의 수를 만드는 문제이다. 입력은 학생 수 와 친구 쌍의수가 주어지고 그 다음줄은 서로 친구인 두학생의 번호가 주어진다. 예를 들면 학생수는 4명 친구 쌍은 6쌍일때 0 1 1 2 2 3 3 0 0 2 1 3 0과 1은 친구이고, 1과 2는 친구이고.... 이렇게 숫자 2개씩 한쌍을 이룬다. 그리고 학생수는 항상 짝수이다 사고 과정 1. 문제를 잘못이해 했는데 친구가 아예 없는 경우까지 생각해서 고민을 했다. 2. 이때 생각난건 순열이었는데 중복되는 경우를 어떻게 처리할지 고민했다. 예를 들면 (1,2) (0,3)과 (2,1) (3,0)은 같은 경우인데 순열로 나열하면 다른 경우로 들어가기 때문이다. 결국 순열에 집착해 옳바른 방향으로 생각하지 못하여 데이터.. 2021. 9. 29.
[종만북] 6.2 재귀호출과 완전탐색[보글게임] PS를 풀다보면서 재귀와 완전탐색에 대한 사고력이 부족하다고 느껴서 종만북을 사게 되었다. 앞부분에 대한 내용은 PS를 어떻게 잘 풀지에 대한 사고력의 전환과 관련된 내용인데 내 레벨이 부족해서 크게 와닿지 않는다. 그래서 앞부분 조금 읽다가 가장 빠르게 느낄수 있는 6장 부터 시작했다. 6장 첫 번째 문제는 보글게임이라는 문제인데. 알파벳 배열이 입력으로 주어지고 해당 배열에서 원하고자 하는 단어를 맞출수 있는지를 재귀적으로 푸는 문제이다. 예를 들면 'U', 'R', 'L', 'P', 'M' 'X', 'P', 'R', 'E', 'T' 'G', 'I', 'A', 'E', 'T' 'X', 'T', 'N', 'Z', 'Y' 'X', 'O', 'Q', 'R', 'S' 이라는 인풋이 들어올때 PRETTY라는 .. 2021. 9. 22.

티스토리툴바