출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo "DFS와 BFS 를 이용한 단순 구현, 깊은 복사" 벽돌이 쌓여있는 격자에서 W의 열 중에 깰 수 있는 벽돌들의 경우를 DFS를 이용하여 탐색한다. BFS를 이용해 선택한 벽돌의 숫자 만큼 상,하,좌,우 벽돌을 탐색하여 해당 턴에 삭제될 벽돌들을 넣고 벽돌을 삭제 시킨다. 그리고 공중에 떠 있는 벽돌들을 아래로 내려준다. 이 과정에서 나는 깊은 복사를 사용했다. 시뮬레이션 중에 백트래킹이 힘들 경우에는 깊은 복사를 사용하는 것도 좋은 방법 인 것 같다. map 의 크기가 작다면 옅은 복사나 깊은 복사나 그렇게 큰 차이가 없다고 ..
출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo "시뮬레이션" 단순 시뮬레이션 문제로써 각 지점에서 최대 배터리 충전 용량을 구하는 것이다. 여기서 중요한 것은 움직이는 매 순간마다 사용자 A와 B가 어떤 BC를 선택해야 배터리 충전 용량이 최대가 되는지를 판별하는 것이다. path[2][A] 배열을 만들어서 매 시간마다 사용자 A 와 B 가 접근할 수 있는 모든 BC를 체크 한 후, getMax 라는 함수를 통해 A와 B가 선택 가능한 BC의 모든 조합을 조사해 그중에서 최대 배터리 충전량을 구하는 식으로 문제를 해결했다. 삼성 역량 테스트 문제의 시뮬레이션이 점점 복잡해지는..
SWEA 1859. 백만 장자 프로젝트 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc) "완전 탐색할 건 아니야, 뭔가 아이디어를 찾자." 해당 문제에서 N이 1,000,000 까지가 있고, 각 지점에서 할 수 있는 행동은 산다/판다/아무것도 안한다. 의 세가지로 나뉜다. 따라서 대략적인 시간복잡도를 계산해 보면 3^1,000,000 이 되고, 완전 탐색으로는 시간 내에 풀 수 없다. 따라서 다른 아이디어를 찾아야 했다. 주식 그래프를 생각해보자. 언제 파는 것이 이익이 최대가 될까? 당연히 고점 보다 낮게 사서 고점에 파는것이 좋다. 고점을 그래프의 가장 끝점으로 우선 잡는다. 내..
출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo "시뮬레이션, map을 두르는 사각형 블록을 세운다." 간단. 이런 방향 전환을 switch 로 일일이 하는 것 말고 더 좋은 건 없을까...? 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810..
출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq "완전 탐색, 매달 이용하냐 안하냐" 문제를 풀면서 완전 탐색을 생각했다. 뭔가 이런 비슷한 문제를 예전에 점화식으로 풀었던 문제가 기억났는데, 사실 이해를 못함. 문제는 단순히 이용 계획이 0 일 이상인 월에 대해서 3가지 이용권으로 모두 탐색을 했다. (1년 이용권의 경우 한번만 체크) 어렵지 않았던 문제였다. 단, 이용 계획이 0인 달에는 재귀호출할 때 금액을 올리지 않는다. 이 부분만 고려하면 쉽게 풀렸다. 12345678910111213141516171819202122232425262728293031323334353637..
- Total
- Today
- Yesterday