SY DevLog

10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 어느 한 도시에서 출발하여 모든 도시를 거친 후, 처음으로 돌아오는 문제이다. 여기서 알아야 할 사실은 어느 도시에서 출발하든 가장 적게 드는 비용은 동일하다는 것이다. 따라서 아무나 한 곳을 시작도시로 정해서 dfs를 사용하여 시작한 곳으로 돌아오면 된다. 모든 도시를 한 번씩만 방문해야하므로 visited 배열을 이용하여 방문 여부를 표시한다. 그런데 문제를 풀면서 한가지 헷갈렸던 점이 있다. 처음 시작한 도시는 이..

1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 이 문제는 이분탐색으로 모든 아이들이 다 놀이기구를 탈 수 있는 최소 시간을 구하여 풀 수 있다. 문제의 예제를 보자. 문제의 예제에서 탑승하는 아이들의 수가 22명이고, 놀이기구가 5개이며 각각의 운행시간이 1,2,3,4,5 이다. 처음 0분에 모든 놀이기구가 비어있으므로 22명 중 5명의 아이들이 각각의 놀이기구에 탑승한다. 그 다음 1분이 지난 후, 비어있는 놀이기구는 1번 놀이기구 하나뿐이다. 따라서 6번째 아이가 1..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 1912번 : 연속합 문제에서 좀 더 발전한 문제이다. 이번에는 주어진 수열에서 연속합을 구하되, 중간에 수 하나를 제거할 수가 있다. 백준 1912번 문제에서는 dp 1차원 배열을 이용하여 문제를 풀었는데, 이번에는 2차원 배열로 만들어서 풀었다. 아래는 백준 1912번 문제 풀이한 링크이다. lotuslee.tistory.com/89 [백준 1912번] 연속합 (java) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 ..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. 다이나믹 프로그래밍은 무엇보다 점화식을 세우는 것이 중요하다. 나는 int[] dp = new int[n]; 로 1차원 dp배열을 생성하였고, dp[n]의 의미는 다음과 같이하였다. dp[n] : n번째 수가 연속합의 마지막일 때, 최대가 되는 연속합 무슨 말이냐면, 입력받은 수열을 배열 arr에 저장한다고 했을 때, arr[0] + ... + arr[n] : 0번째 수부터 n번째 수까지의 연속합 arr[1] + ... + arr[n] : ..

10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 한바퀴 돌때마다 재귀함수를 호출하여서 arr 2차원 배열에 앉게 될 대기자의 대기번호를 차례대로 넣어준다. solve(int sr, int sc, int r, int c) (sr, sc)는 한바퀴에서 첫번째 시작하는 좌표를 의미하고, r은 세로 길이, c는 가로 길이를 의미한다. 소스코드 :

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 분할하여 같은 동작을 반복하기 때문에 재귀를 이용하여 풀 수 있다. 처음에는 1, 2, 3, 4 분면의 모든 경우의 수를 다 재귀함수 호출을 했더니 시간 초과가 나왔다. 그래서 조건문을 이용하여 (r, c)이 포함된 사각형만 선별적으로 재귀를 실행하도록 변경하였다. 2차원 배열의 정보를 가장 왼쪽 위 좌표(i, j) 와 한 변의 길이 size로 나타낼 때, 이 2차원 배열을 4등분한 각각의 사각형은 다음과 같이 표현이 가능하다. - 2사분면 : (i, j..

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 주어진 배열 전체를 가지고 부분수열의 합을 구하면 시간초과가 난다. 그러므로 이 문제를 배열을 두 개로 나누어서 투 포인터 알고리즘으로 부분수열의 합을 구해야 한다. 처음에는 부분수열이 연속해야만 하는 줄 알았는데, 문제를 다시 읽어보니 꼭 연속하지 않은 수열이어도 상관없다는 것을 깨달았다. 알고리즘 1. 먼저 배열을 두 개로 나눈다. (0 ~ N/2), (N/2 ~ N) 예를 들어, 문제 예제에서 주어진 배열이 -7 -3..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 색종이를 계속 4등분으로 분할하여 모두 같은 색으로 이루어졌는지 아닌지를 확인하는 문제. 분할을 하면서 동일한 로직을 반복하기 때문에 재귀를 이용하여 해결할 수 있다. 재귀 문제는 항상 base case 즉, 탈출 조건이 무엇인지를 확인해야 한다. 이 문제의 base case은 다음과 같다. 1. 색종이의 크기가 1인 경우 색종이의 크기가 1이면 더 이상 분할이 불가능하므로 재귀를 종료한다. 2. 색종이의 크기가 1보다 크지만, 모두 ..

2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 다음과 같은 트리가 있을 때, 인오더와 포스트오더로 나타내면 아래와 같다. InOrder : 4 - 2 - 5 - 1 - 6 - 3 - 7 PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1 포스트오더로 나열하면 가장 오른쪽에 있는 값은 트리의 루트가 된다. 포스트오더는 왼쪽 노드 - 오른쪽 노드 - 가운데 노드 순서대로 순회하기 때문이다. PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1 인오더에서는 루트를 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자..

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 2차원 배열을 4등분으로 계속 분할해나가면서 푸는 문제이기 때문에 재귀를 이용하여 쉽게 풀 수 있다. quardTree() 라는 재귀함수를 만들어서 각 이차원 배열의 가장 왼쪽 위의 위치(r, c)와, 배열의 크기(size)를 인수로 입력받는다. -> quardTree(int r, int c, int size) 재귀의 base case는 언제인가? size = 1로, 더 이상 분할이 불가능한 경우 size가 1보다는 크지만, (r, c)를 가장 왼쪽..