IT 개발 돼지의 일상

출처 : https://www.acmicpc.net/problem/5566 "단순 시뮬레이션" 123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int N,M; static int[] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader..

백준 3048. 개미 (https://www.acmicpc.net/problem/3048) "단순 시뮬레이션" 해당 문제는 단순 시뮬레이션 문제인 것 같다. 실제로 해보는 것이 답. 근데 어떻게 구현 할 것인가. 단순 시뮬레이션을 돌려야 하는 것인가? 어떤 수식 수식이나 그리디하게 풀 수 있는 방법이 있나? 잘 모르겠다. 무식하게 다 해보자. 나는 구현에 ArrayList 를 사용했다. 두 그룹을 ArrayList에 넣고 반대 방향의 개미를 만나면 위치를 서로 바꿔주었다. 그리고 실제 개미들이 모두 지나갔는데도 T 값이 증가할 것을 염려하여 시뮬레이션 이전에 T 값을 비교하여, 모두 지나간 시간보다 더 큰 T값이 주어지면 그냥 문자열을 붙여서 출력하고 끝냈다. 아 그리고 매번 System.out.prin..

SWEA 1859. 백만 장자 프로젝트 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc) "완전 탐색할 건 아니야, 뭔가 아이디어를 찾자." 해당 문제에서 N이 1,000,000 까지가 있고, 각 지점에서 할 수 있는 행동은 산다/판다/아무것도 안한다. 의 세가지로 나뉜다. 따라서 대략적인 시간복잡도를 계산해 보면 3^1,000,000 이 되고, 완전 탐색으로는 시간 내에 풀 수 없다. 따라서 다른 아이디어를 찾아야 했다. 주식 그래프를 생각해보자. 언제 파는 것이 이익이 최대가 될까? 당연히 고점 보다 낮게 사서 고점에 파는것이 좋다. 고점을 그래프의 가장 끝점으로 우선 잡는다. 내..

출처 : https://www.acmicpc.net/problem/2186 "전형적인 DP 문제, 재귀 호출 및 리턴에 대해 잘 알고있자." N,M 의 범위를 고려하면 100,000 개의 칸이 존재한다. 대략 계산해 봤을 때, 100*100 개 칸에서 갈 수 있는 방법의 개수는 4가지 방향에 최대 5칸의 거리 20개가 된다. 20^100,000 ... 브루트 포스로는 절대 돌아가지 않는다. 100 * 100 격자에 모든 문자가 'B' 이며 'BB' 를 만드는 경우의 수를 생각해보면 굉장히 많다. 그리디한 방법도 없고, 이럴 때는 DP 를 이용해 푸는 것이 좋겠다. 사실 이런 격자 문제를 풀때 DP를 사용하면 나는 항상 DP[X][Y][?] 이런 식으로 놓고 생각해본다. 무엇을 어떻게 메모이제이션 할 것인..

출처 : 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..

출처 : https://www.acmicpc.net/problem/12761 "DP를 사용할 때, 부등호를 조심하자." 해당 문제를 BFS를 이용해 풀었다. 대충 계산해보아도 총 100,001 개의 지점이 있고, 각 지점마다 갈 수 있는 경우의 수는 8 가지 이므로 8^100000 이나 되므로(실제로는 이보다 작겠지만) 그냥 단순 탐색으로는 무리가 있고, 메모이제이션을 이용해서 가지치기를 해줘야 했다. 지점 A에서 B로 간다고 했을 때, 내가 지점 B까지 가는데 걸린 횟수를 저장하는 것, 단 이때 DP[B] 에 값이 INF 가 아니라면(이미 누군가 방문 했다면) 나보다 지점 A를 더 짧은 횟수 안에 통과했는지를 비교한다. if ( dp[B]