본문 바로가기

전체 글

 (88)
백준 18809 <Gaaaaaaaaaarden> 씨앗을 놓을 수 있는 위치를 조합으로 구한 다음 씨앗을 퍼트려 꽃의 개수를 구하는 시뮬레이션 문제이다. 많은 시간을 들이면 풀 수 있는 문제기 때문에 빠른시간내에 방법을 생각하고 예외사항을 처리하는 게 문제였다. 문제를 해결하면서 고려해야 할 점은 두가지가 있다. 조합을 이용해 두가지 씨앗의 종류를 겹치지 않게 선택하는 방법 씨앗을 퍼트리면서 다른종류의 씨앗이 다음 차례에 동시에 위치하게 되면 꽃이 피게 되고 진행하지 않는 것 2번 부분을 처리하는게 가장 힘이 들었는데 두 개의 씨앗이 동시에 마주치는 경우를 처리해주는 방법이 어려웠다. 기본적으로 씨앗의 종류와 위치를 나타내기위한 클래스를 선언했다. 이후에는 씨앗을 놓을수 있는 장소만 배열에 넣기 위해 2인 위치를 ArrayList배열에 담아서 나타냈다...
백준 14502 <연구소> 이 문제 또한 완전탐색의 가장 기본적인 문제라고 볼 수 있다. 가장 기본적인 틀로는 0이 있는 자리를 3가지만 뽑는 조합으로 구한 다음 DFS 또는 BFS를 통해 바이러스를 퍼트린 다음 빈칸을 세어주는 문제로 간단하게 풀 수 있다 . 예전에는 다른 방법을 찾아보고 그랬었는데 가장 먼저 이런 문제를 완전탐색으로 접근하고 시간복잡도를 계산한 다음 가능하다면 완전탐색으로 문제를 해결하도록 성장하였다. 이 문제를 완전 탐색으로 푼다면 전체가 0이라고 해도 조합을 계산해본다면 최대크기가 8*8 64이기때문에 3개를 뽑는다고 해도 64C3 이기때문에 41664번이 수행될것이고 완전탐색을 그 후에 한다고 해도 2666496으로 300만이 넘지 않는다. 그러므로 완전탐색으로 접근이 가능한 문제인 것이다. 우선적으로 값..
백준 18808 <스티커 붙이기> 문제만 잘 읽는다면 많은 사람들이 쉽게 풀 수 있을 만한 전형적인 시뮬레이션 문제이다. 이 문제를 푸는데 가장 중요한것은 총 두 가지이다. 첫 번째는 스티커를 순서대로 붙이고 4방향으로 돌려서 붙여지지 않는 스티커는 넘어간다. 두 번째는 스티커를 가장 위쪽, 왼쪽에서부터 차례대로 확인하는 문제이다. 이 두 가지 방법만 잘 교려 해 준다면 쉽게 접근할 수 있는 문제이다. 기본적으로 이 문제의 최대 시간을 고려한다면 맵의 길이가 40*40이고 모든 칸을 검색한다 해도 30만이 안 되는 값이다. 4방향으로 한다고 고려하면 120만 스티커의 개수인 100을 곱해도 1억 2 천 번이기 때문에 해결할 수 있는 문제이다. 일단 나는 기본적으로 크기가 다른 배열을 넣어주기 위해서 어레이 리스트를 사용해서 2중 배열을 ..

티스토리툴바