알고리즘/백준(131)
-
[백준 2606번] 바이러스
풀이문제를 알고리즘 유형에 맞게 바꾸어 해석해보면 다음과 같다. 1. 출발지점은 무조건 1번부터 시작한다. (1번 컴퓨터는 무조건 감염 되어있다.)2. 출발지점부터 그다음 갈 수 있는 지점까지를 카운트 한다. (1번부터 연결되어 있는 컴퓨터를 모두 찾아야 한다.) 이렇게 보면 출발지점이 고정되어 있는 일반적인 BFS 문제와 같다. 만약 2하고 4가 연결되어 있다면 2번지점에 있을때 4번으로 갈 수 있고, 4번지점에 있을때 2번으로 갈 수 있다. (양방향 간선이다.)2차원 배열을 만들어서 연결되어 있다면 1, 없다면 0을 넣어두고 array[컴퓨터1][컴퓨터2] == 1 일때만 큐에 삽입할 수 있게한다.이 때 양방향으로 갈 수 있으므로 array[컴퓨터2][컴퓨터1] == 1 일때도 생각해 주어야한다. 순..
2017.05.16 -
[백준 2193번]이친수
풀이규칙을 알기위해서 수작업으로 어떤 경우의 수가 있는지 탐색합니다. n=1 1n=2 10n=3 100 101n=4 1000 1001 1010n=5 10000 10001 10010 10100 10101n=6 100000 100001 100010 100100 101000 100101 101010 101001 : : 규칙을 보면 1 1 2 3 5 8 ''' 과 같은 익숙한 숫자가 나옵니다. 위 숫자는 피보나치 수로 재귀나 DP로 간단하게 구현할 수 있습니다. 피보나치 수를 재귀로 구현하면 미리 계산한 부분을 또 계산하기 때문에 비효율적이고 시간초과가 날 수 있습니다. 이런 경우 메모이제이션을 통해 구할 수 있습니다. 주의할 점은 피보나치의 수를 구현할 때 n이 47을 넘게 되면 int형의 범위를 넘어가게 됩..
2017.05.15 -
[백준 11726번] 2xn 타일링
풀이모든 경우의 수를 생각해 보았습니다.n=1 --> 크기1 1개n=2 --> 크기1 2개 or 크기2 1개n=3 --> 크기1 3개 or 크기1 1개 + 크기2 1개 (왼쪽에 배치하였을 때) or 크기1 1개 + 크기2 1개 (오른쪽에 배치하였을 때) : : 규칙을 찾아보면 점화식을 이루는 것을 찾을 수 있습니다.점화식 n = n-1 + n-2 재귀로도 풀 수 있지만 1000까지 재귀로 풀게되면 시간초과가 날 수 있으므로 DP를 이용하여 풀 수 있습니다. 12dp[1] = 1;dp[2] = 2;cs초기값을 미리 지정해줍니다. (피보나치 수열과 비슷합니다.) 1dp[i] = (dp[i - 1] + dp[i - 2])cs다음과 같이 점화식을 쓸 수 있습니다. 문제에서 10007으로 나눈 나머지를 출력하라 ..
2017.05.15 -
[백준 2579번] 계단 오르기
DP로 분류된 문제 조건1. 계단을 오를때는 1칸 또는 2칸까지 한번에 오를수있다.2. 연속된 3칸은 오를 수 없다.3. 마지막 계단은 무조건 밟아야한다. 풀이마지막 계단을 무조건 밟아야한다면 두가지로 분류할 수 있다.1. 전칸을 밟고 마지막칸을 밟는 경우 ? ? O O --> 마지막 칸이 n이라면 n-1 + n이 된다. 2. 전전칸을 밟고 마지막칸을 밟는 경우? O X O --> 마지막 칸이 n이라면 n-2 + n이 된다. 하지만 1번의 경우 연속으로 3칸을 밟을 수 없으므로 전칸을 밟고 현재칸을 밟는경우에는 조건을 추가해주어야한다. 1. 전칸을 밟는 경우에는 n-2번째 칸을 밟을 수 없다. (즉, 전전전칸 + 전칸 + 현재칸이 되어야한다.)? O X O O --> n-3 + n-1 + n으로 쓸 수 ..
2017.05.14 -
[백준 1149번] RGB거리
https://www.acmicpc.net/problem/1149 방 법 1. R을 선택하였을때 그다음 줄에서 G,B와 합한 값을 임시로 저장2. G를 선택하였을때 그다음 줄에서 R,B와 합한 값을 임시로 저장 (1번에서 B를 저장했기때문에 R+B와 G+B중 작은 값을 저장)3. B를 선택하였을때 그다음 줄에서 G,R와 합한 값을 임시로 저장 (2번에서 R을 저장했기때문에 G+R와 B+R중 작은 값을 저장)4. 임시로 저장한 배열을 원래의 배열에 다시 삽입5. 처음부터 마지막줄까지 돌면 마지막 줄에는 최종값 3개가 나옴6. 최종값중 최소값이 답 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include us..
2017.05.13