Java53 [Gold IV] 여행 가자 - 1976 (Java) 문제 요약 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다. 문제 분석 도시 간의 연.. 2023. 7. 28. [Gold III] LCS 3 - 1958 (Java) 문제 요약 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라. 문제 분석 기존에 풀었던 LCS2문제의 연장선에서 3차원 배열을 사용한 문제 해결. https://cornsilk-tea.tistory.com/64 [Gold IV] LCS 2 - 9252 (Java) 문제 요약 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수.. 2023. 7. 28. [Gold IV] LCS 2 - 9252 (Java) 문제 요약 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 문제 분석 두 문자열 A와 B의 모든 위치를 검사하면서, 만약 두 문자가 같다면 이전 위치의 LCS 길이에 1을 더하고, 그렇지 않다면 이전 위치에서의 LCS 길이 중 큰 값을 저장한다. 이 과정을 통해 얻은 2차원 배열 dp의 마지막 요소 dp[A.length][B.length]가 두 문자열의 LCS 길이가 된다. LCS를 출력하기 위해, 문자열 A와 B의 마지막 위치에서 시작해 첫 위치까지 역순으로 이동하면서, 두 문자가 같을 경우 해당 문자를 스택에.. 2023. 7. 28. [Silver I] 쉬운 계단 수 - 10844 (Java) 문제 요약 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 문제 분석 자릿수가 1일 때, 1부터 9까지의 수에 대해 각각 계단 수는 1개씩 있음을 저장 2자리 이상인 경우, 각 자릿수 N에 대해 마지막 숫자가 0부터 9까지 각각 어떤 계단 수로 이어질 수 있는지 계산하고 저장 여기서 계단 수는 이전 자릿수의 마지막 숫자에서 1 증가하거나 감소한 수 마지막으로, 주어진 자릿수 N에 대해 마지막 숫자가 0부터 9까지 가능한 모든 계단 수의 개수를 더하면 문제의 답이된다. 코드 package Week20; import java.io.BufferedR.. 2023. 7. 28. [Gold IV] 빙산 - 2573 (Java) 문제 요약 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 만일 전부 다 녹을 때까지 두 덩.. 2023. 7. 22. [Gold V] 회문 - 17609 (Java) 문제 요약 회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다. 여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 .. 2023. 7. 22. 이전 1 2 3 4 5 6 ··· 9 다음
