전체 글71 [Gold IV] 가르침 - 1062 (Java) 문제 요약 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 문제 분석 입력받는 단어에 고정적으로 들어가는 알파벳들과 문자열을 전처리해준다. 그 후 비트마스킹을 거친 값.. 2023. 8. 8. [Silver I] 전쟁 - 전투 - 1303 (JAVA) 문제 요약 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다. 문제 분석 맵을 받아서 순차적으로 탐색하며 BFS를 돌린다. 이때 찾은 병사들의 색을 기준으로 값을 갱신해준다. 코드 import java.io.BufferedReader; import java.io.IOException.. 2023. 8. 8. [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. 이전 1 2 3 4 5 6 ··· 12 다음
