Limky 삽질블로그

BackJoon #14891 - 톱니바퀴(Gear) https://www.acmicpc.net/problem/14891 삼성전자 2017 하반기 SW직군 역량테스트 중 기출문제 1번을 풀어봤습니다. 흠...저는 대략 2시간 걸린 것 같습니다. 코드가 좀 지저분한데 리팩토링 좀 해야겠네요.. package SamsungTest; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Gear { static int[][] command; static ArrayList list; public static v..

BackJoon #1991 - 트리순회(Tree Order) https://www.acmicpc.net/problem/1991 이번 시간은 트리 순회에 대해서 알아보겠습니다. 트리 순회는 3가지 방법으로 트리를 순회할 수 있습니다. 각 순회 방법에 따라 루트 탐색 순서가 어떤지 파악하면, 쉽게 암기 할 수 있습니다. 다음과 같은 트리가 있다고 가정하면, 각 순회 방법에 따라 탐색 순서가 바뀝니다. 1. 전위 순회 루트 - > Left -> Right // ABDCEFG 2. 중위 순회 Left -> 루트 -> Right // DBAECFG 3. 후위 순회 Left -> Right - > 루트 // DBEGFCA 이제 재귀함수 호출을 통해 전위, 중위, 후위 순회를 구현해보겠습니다. 입력 값이 알파벳이기 ..

BackJoon #2579 - 계단오르기(Climbing Stairs) https://www.acmicpc.net/problem/2579 대표적인 DP문제입니다. DP[N] 을 N개 계단을 계단오르기 규칙에 의해 얻은 가장 큰 점수라고 하겠습니다.N번째 계단은 무조건 밟아야 하기 때문에 N번째 계단이 1번 연속인 경우! N번째 계단이 2번연속인 경우! 이 2가지 경우를 나누어서 생각해 보겠습니다. 저는 1차원 배열로 DP를 잡고 풀었습니다. A 배열은 주어진 계단 점수를 담고 있습니다. N번째 계단이 1번 연속인 경우 N-1번째 계단은 필요 없고, N-2번째 계단의 총점을 합쳐야 합니다. 따라서.. DP[N] = DP[N-2] + A[N] N번째 계단이 2번 연속인 경우 N-1번째 계단은 밟아야 하고, ..

BackJoon #1912 - 연속합 (Continuous Sum) https://www.acmicpc.net/problem/1912 대표적인 DP문제입니다. DP[N] 을 N개 자리수에 연속합을 한 것들 중에서 가장 큰 연속합 이라고 하겠습니다.N자리에 해당하는 숫자가 이전 연속합에 속하는 경우와 속하지 않고 새롭게 연속합을 시작하는 경우 2가지로 나누어서 생각해 볼 수 있습니다. ARR 배열은 주어진 수열을 담고 있습니다. N자리에 숫자를 연속합에 합치면, 이득인 경우 DP[N] = DP[N-1] + ARR[N] N자리에 숫자를 연속합에 합치면, 이득을 얻지 못하는 경우 (새롭게 다시 연속합을 시작해야함) DP[N] = ARR[N] 그렇다면 이 2가지 경우를 분기 처리해야 하는데 어떻게 할까요???우..

BackJoon # 2193 - 이친수 (Pinary Number) https://www.acmicpc.net/problem/2193 대표적인 DP문제입니다. DP[N] 을 N개 자리수에 이친수를 만족하는 경우의 수라고 생각하겠습니다.N자리에 올 수 있는 숫자는 0 OR 1입니다. 각각에 경우에 대해서 생각해 보겠습니다. N자리에 0인 경우 N-1자리에 올 수 있는 숫자는 0 OR 1 둘 다 가능합니다. 따라서 DP[N] = DP[N-1] 이 성립합니다. N자리에 1인 경우 N-1자리에 올 수 있는 숫자는 0 만 가능합니다. 그렇다면 N-2 자리에 올 수 있는 숫자는? 0 OR 1 이 가능합니다. 따라서 . . . DP[N] = DP[N-2] 이 성립합니다. 이제 N자리에 0 이 올수도 1이 올수도 있으..

BackJoon # 11057 - 오르막 수 (Ascending Number) https://www.acmicpc.net/problem/11057 대표적인 DP문제입니다. DP[N][L] 을 N자리수의 L이라는 숫자가 올 경우, 오르막 수 조건에 해당하는 경우의 수 라고 하겠습니다. DP[3][7] 이라고 하면 _ _ 7 을 뜻합니다. 그렇 다면 2번째 자리는 어떤 숫자가 올 수 있을까요?오르막 수 규칙에 의하면 0 ~ 7 이라는 숫자가 올 수 있습니다. 즉 N자리 L 숫자가 온다면, N-1자리 숫자는 0 ~ L 범위의 숫자가 올 수 있는 것입니다. 지금은 하나의 경우인 즉 L숫자를 가정했지만, 모든 경우의 수를 고려해야 하기 때문에 시그마로 식을 세워야 합니다. 결국 DP[N][L] = DP[N-1][..

BackJoon # 2156 - 포도주 시식 (Wine Tasting) https://www.acmicpc.net/problem/2156 대표적인 DP문제입니다. 연속으로 3번 마시지 않으면서 주어진 N개 포도주를 어찌어찌 마신다면, 얼만큼 마실 수 있느냐 그 최고 값을 찾아라 입니다. 어찌어찌 마신다는 것은 우리가 어떻게 마셔라 라고 마음대로 정해줄 수 있다는 뜻입니다. 3번 연속으로 마실 수 없다는 것을 따져보면, 0번 연속 마실 수 있는 경우, 1번 연속 마실 수 있는 경우 , 2번 연속 마실 수 있는 경우가 있습니다. 자 그럼 점화식을 짜봅시다.ㅎㅎㅎㅎ dp[n] = 포도주 n개가 주어졌을 때, 가장 많이 마실 수 있는 양 p[n] = n번째 포도주의 양 0번 연속 마실 수 있는 경우 n번째 포도..

BackJoon # 5427- 불(Fire) https://www.acmicpc.net/problem/5427 package BackJoon; import java.awt.Point; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Fire { static ArrayList arrays; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); arrays = new ArrayList(); char [][]temp; fo..