왠지 오늘은 뿌요뿌요 게임을 구현해 보고 싶어졌습니다. 구현 문제로, 고전 게임들을 구현하라는 문제가 생각보다 많이 나오는데요. 뿌요뿌요 역시 구현력을 보기 위한 좋은 문제 중 하나입니다. 문제는 아래와 같습니다. 16768번 문제를 단순화 시키면 위와 같습니다. 일단, 이 문제가 구현력으로 cover가 되는지, 아니면 optimize를 해야 하는지, 아니면, 특수한 알고리즘을 써서 시간 복잡도 자체를 낮춰야 하는지부터 보도록 하겠습니다. 먼저 문제를 간단하게 분석해 보도록 하겠습니다. 먼저 칸의 수는 최대 1000개입니다. 그러면 각 칸이 하나씩 연쇄적으로 없어진다고 했을 때, 1000 연쇄까지 일어날 수 있을 거에요. 정말 극단적으로 생각했을 때요. 그러면, 1연쇄가 일어날 때 어떤 일이 일어날까요?..
구현 검색 결과
코딩 테스트를 보기 위해서는, 기본적으로 제한 조건을 읽을 줄 알아야 합니다. 단순히 n이 30보다 작고 m이 15보다 작은 조건이 들어오는군이 아니라, 왜 출제자가 이런 조건을 주었는지 곰곰히 생각해 보자는 것입니다. 이게 그렇게 어렵지 않은 것 같지만, 저는 솔직히 쉽지 않았습니다. 문제를 읽고 바로 이거네? 하고 들어가는 습관이 있다 보니, 이런 세세한 조건을 놓치는 경우가 다반사였습니다. 코테에서 이런 일이 발생했다면 탈락하실 확률이 높아집니다. 왜 제가 코테에서 물을 많이 먹었는지 단박에 알 수 있는 무서운 말입니다. 사실 조언해 줄 실력도 못 되지만, 작년에 물을 많이 먹으면서 제가 부족했던 점을 복기해 보았습니다. 그렇게 생각해 주시면 좋을 듯 싶습니다. 자. 그러면 어떻게 조건을 분석해야 ..
안녕하세요. chogahui05입니다. 저번 시간에 소코반을 구현해 보았습니다. 다소 어려웠어요. 오늘은 그것보다 다소 쉬운 2048 퍼즐의 1턴을 구현해 보도록 하겠습니다. 사실 뿌요뿌요 게임도 구현해 보면 재밌긴 합니다. 그런데 그건 BFS, DFS를 알아야 하는 전제가 깔리니 쉽지 않긴 하지만요. 하튼, 구현해 봅시다. 2048은 어떠한 것을 합칠 수 있는 방향이, 위, 아래, 왼쪽, 오른쪽이 있습니다. 이 중, 퍼즐이 요렇게 있고, 우측으로 합친다고 해 봅시다. 그러면, 먼저 2와 2가 merge 될 거에요. 다음에 노란색 4와 파란색 4는 merge 되지 않아요. 단지, 파란색 4끼리만 merge가 됩니다. 이렇게 합쳐질 겁니다. 다음에 8과 4를 합치려니, 되지 않습니다. right 명령을 내..
구현 8번째 시간입니다. 실전 문제 하나를 풀면서, 여러 가지 기법들을 다뤄보겠습니다. 소코반 게임은 캐릭터와 박스가 있습니다. 이 박스들을 적절히 목표 지점에 이동시켜야 하는 게임입니다. 아. 옛날에 많이 있었던 게임 중 하나입니다. 그냥, 우리는 캐릭터를 명령에 맞게 이동시킨 다음에 맵의 상태를 출력하는 것이 목표라면 목표라고 할 수 있겠네요. 그런데, 맵의 상태를 보니까, 목표 지점에 있는 ~가 눈에 보입니다. 즉, 목표 지점이면서 박스가 있는 곳이라던지, 목표 지점이면서 캐릭터가 있는 곳이라던지. 즉, A and B 조건이 눈에 밟힙니다. 이렇게 되어버리면 경우의 수를 처리해야 할 것이 상당히 많아집니다. 이것을 적절히 분해를 해서 처리를 하는 방법을 고민해 봅시다. 물론, 제 코드를 조금 더 응..
구현 카데고리 7번째 글입니다. 오늘은 상태를 어떻게 나타내는지에 대한 이야기를 해 보도록 하겠습니다. 켜졌다와 꺼졌다. 이것은 각각 1과 0으로 표현이 가능합니다. 울타리가 있다. 울타리가 없다. 또한 1과 0으로 표현이 가능합니다. 즉, 어떠한 상태가 2개만 있을 때, 우리는 bit operation을 이용할 수 있습니다. 이걸 어떻게 써야 할까요? 예제를 다소 어려운 문제로 잡아보겠습니다. 백준 1200번, BOI 2008 #5번 문제인 기상 예측 문제를 봅시다. 이 문제는 가로선 n개와 세로선 m개로 영역을 적절히 나눌 때, 부분합의 최대를 최소로 하는 문제입니다. 예를 들어, 2 by 3짜리 영역에, 가로선 1개, 세로선 1개를 그을 수 있다고 해 봅시다. 그러면 이렇게 그을 수 있습니다. 이 ..
최근댓글