브루트포스 알고리즘2 [백준/12094/C] 2048(Hard) 필독 : https://eigenarea.tistory.com/68 [백준/12100/C] 2048(Easy)크게 3개의 파트로 나누어서 생각해보아야한다.1. 좌/우/상/하의 이동을 어떻게 구현할 것인지?2. 탐색알고리즘을 어떻게 전개할것인가?3. 최댓값을 판단하는 알고리즘은? 2,3은 문제의 태그를 보eigenarea.tistory.com Easy문제와의 차이점은 실행횟수가 10번으로 늘어 브루트포스만으로는 해결해야할 분기가 기하급수적으로 늘어버렸다는 것이다.(대충 Easy문제의 1024배정도..?) 그래서 우리는 이러한 점에 착안해보아야한다.1. 움직여서 이동하지 않는 분기는 pruning(가지치기)해준다.2. 아무리 증가해도 max가 될 수 없는 분기도 pruning해준다. 1번은 단순하다. 그냥 .. 2025. 6. 28. [백준/12100/C] 2048(Easy) 크게 3개의 파트로 나누어서 생각해보아야한다.1. 좌/우/상/하의 이동을 어떻게 구현할 것인지?2. 탐색알고리즘을 어떻게 전개할것인가?3. 최댓값을 판단하는 알고리즘은? 2,3은 문제의 태그를 보면 알 수 있다싶이 브루트포스로 해결할 수 있다.처음에 시간복잡도가 브루트포스를 커버해줄 수 있는지 의문을 가졌지만 GPT님이 계산해주셔서 그냥 그런갑다 납득했다.. 1.에 대한 해결로는 좌/우로 이동할 때는 temp배열에 변동된 각 행을, 상/하로 이동할 때는 temp배열에 변동된 각 열을 저장해줄 것이다. 좌측으로 미는것을 구현해보자면 이러하다 : board[i][j]가 0이 아닐때 temp에 받을 것인데,a) 만약에 temp[idx]가 0이면 그냥 입력받고(게임을 생각해보자, 아무것도 없는 부분은 그냥 스.. 2025. 6. 28. 이전 1 다음 반응형