백준

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 풀이 백트래킹을 통해서 이전 depth에서 고른 번호를 체크하고 다음 depth로 진행하면서 모든 경우를 탐색하였다. 📌 백트래킹 탐색 public static void DFS(int depth, String value){ if(depth == M){ sb.append(value.substri..

2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 문제 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다. 풀이 이 문제를 풀면서 완전 탐색이란 무엇인가에 대해서 좀 더 깨달은 것 같다. 처음에는 그냥 오목의 승패 여부를 가르는 문제여서 쉽게 해결할 줄 알았으나 생각보다 많은 경우의 수가 존재..

15270번: 친구 팰린드롬 첫째 줄에 총 반친구 수 N(2

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. 풀이 두 개의 문자열이 주어졌을 때 LCS의 길이와 LCS를 출력하는 문제이다. ..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 풀이 이 문제의 키 포인트는 자신을 포함한 n개의 수열에서의 최댓값을 구하는 배열을 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 구한다. 이때, left[i-1] + right[i+1]은 i번째의 수를 뺀 값이라는 것..

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 풀이 계단수는 이전 자리의 수에서 +1 혹은 -1한 수가 현재 자리에 올 수 있는 수를 말한다. 따라서 이전 자리 수에 따라서 그 다음에 오는 수에 영향을 끼친다. 따라서 이를 활용하여 DP배열을 만들고 문제를 풀었다. 먼저 첫 번째 자리에 오는 수를 생각해보자. 첫 번째 자리에 올 수 있는 수는 1 ~ 9까지 총 1개의 경우의 수밖에 없다. 즉, D[1][i] = 1이 된다. (D[1][0] = 0, 계단수에서 첫 번째 자리에 0이 올 수 없다.) 여기서 1자리가..

1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다. A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오. 풀이 이전에 백트래킹으로 문제를 풀어보았기 때문에 이번 문제도 한번 백트래킹으로 접근해보았습니다. 4와 7로만 이루어진 수를 만들어야 하기 때문에 현재 자리수에서 뒤에 4, 7를 계속 붙여나가면서 이미 최대 값을 벗어난 수는 더이상 탐색할 필요가 없기 때문에 탐색을 종료..

14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 문제 하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다. 단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다. 돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자! 풀이 해당 문제는 꽃의 씨앗을 심은 기준으로 상, 하, 좌, 우, 현재 위치가 다른 꽃들과 겹치지 않도록 심으면서,..