SY DevLog

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 인오더에서는 루트를 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자..

8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 이분탐색을 이용하여 해결할 수 있다. 사대의 위치를 arr 배열에 오름차순으로 정렬한다. 정렬 전 : 6 1 4 9 정렬 후 : 1 4 6 9 특정 동물의 위치에서 가장 가까운 사대의 위치를 이분탐색으로 찾는다. 이분탐색을 진행하는 방법은 다음과 같다. arr[middle] == x 이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표와 일치한다면, 즉 사대가 같은 세로 일직선 상에 존재한다면 이 때의 사대가 동물과의 거리가..

2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net R : 홀수 OR C : 홀수 R, C 둘 중에 하나라도 홀수이면 모든 칸에 있는 기쁨을 다 더할 수 있다. 모든 칸을 다 방문할 수 있다. R : 짝수 AND C : 짝수 문제는 R과 C 둘 다 짝수인 경우이다. R과 C 둘 다 짝수인 경우에는 모든 칸을 다 지날 수 없기 때문에 기쁨의 합이 최대가 되는 방법을 생각해야한다. 처음에는 dfs를 이용하여서 모든 가능한 경로를 다 탐색한 후에 기쁨의 합이 최대가 되는 경로를 출력하도록 했었다. 그러나 결과는 '..

1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net A[r][c]에 대하여 A[r][c]!=B[r][c] 이면, (r, c)를 시작으로하는 3*3 행렬만큼 0은 1로, 1은 0으로 뒤집는다. 위 과정을 r = 0, c = 0 부터 마지막까지 반복한다. 이렇게 하는 이유는 만약에 A[0][0]!=B[0][0] 라면 B[0][0]와 같게 하기 위해 A[0][0]를 뒤집어야 한다. 그런데 A[0][0]를 뒤집기 위해서는 결국 (0,0)을 맨 왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다. A[0][1]도 마찬가지이다. A[0][1]..