본문 바로가기

분류 전체보기41

[백준] 9252번 LCS 2 (C++) 목차문제입력출력풀이문제 해결 방법코드문제 문제 링크LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.예제 입력 1ACAYKPCAPCAK출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.LCS가 여러 가지인 경우에는 아무거나 출력한다.예제 출력 14ACAK풀이문제 해결 방법이 문제는 동적 프로그래밍을 사용하여 해결할 수 있습니다. 주요 해결 단계는 다음과 .. 2025. 4. 12.
[백준] 5052번 전화번호 목록 (C++) 목차문제입력출력풀이문제 해결 방법코드문제 문제 링크전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자긴급전화: 911상근이: 97 625 999선영: 91 12 54 26이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간, 긴급전화가 연결되기 때문이다.따라서, 이 목록은 일관성이 없는 목록이다.입력첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50)각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000.. 2025. 4. 12.
[백준] 3955번 캔디 분배 (C++) 목차문제입력출력풀이문제 해결 방법코드문제 문제 링크창영이는 K명의 아이들에게 캔디를 하나씩 나누어 주려고 한다.하지만 캔디는 한 봉지에 C개가 들어있다.따라서 창영이는 한 봉지를 사면, C개의 캔디를 가지게 된다.아이들은 항상 한 개의 캔디를 받아야 한다.봉지는 적어도 1개를 사야하고, 캔디는 버리면 안 된다.K명의 아이들에게 캔디를 나누어 주기 위해서 최소 몇 봉지의 사탕을 사야하는지 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어 주어진다. (1 ≤ K, C ≤ 10^9)예제 입력 1510 510 71337 23123454321 42999999937 142857133출력각 테스트 케이스에 대.. 2025. 4. 12.
[백준] 3830번 교수님은 기다리지 않는다. (C++) 목차문제입력출력풀이문제 해결 방법코드문제 문제 링크상근이는 매일 아침 실험실로 출근해서 샘플의 무게를 재는 일을 하고 있다. 상근이는 두 샘플을 고른 뒤, 저울을 이용해서 무게의 차이를 측정한다.교수님의 마음에 들기 위해서 매일 아침부터 무게를 재고 있지만, 가끔 교수님이 실험실에 들어와서 상근이에게 어떤 두 샘플의 무게의 차이를 물어보기도 한다. 이때, 상근이는 지금까지 잰 결과를 바탕으로 대답을 할 수도 있고, 못 할 수도 있다.상근이는 결과를 출근한 첫 날부터 공책에 적어 두었다. 하지만, 엄청난 양의 무게가 적혀있기 때문에, 교수님의 질문에 재빨리 대답할 수 없었다. 이런 상근이를 위해서 프로그램을 만들어 주자.입력입력은 여러 개의 테스트 케이스로 이루어져 있다.각 테스트 케이스의 첫째 줄에는 샘.. 2025. 4. 12.
[백준] 2960번 에라토스테네스의 체 (C++) 목차문제입력출력풀이문제 해결 방법코드문제 문제 링크에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ K 예제 입력 17 3출력첫째 줄에 K번째 지우는 수를 출력한다.예제 출력 16풀이문제 해결 방법이 문제는 에라토스테네스의 체 알고리즘을 구현하여 K번째로 지워지는 수를 찾는 문제입니다. 주요.. 2025. 4. 12.
[백준] 2042번 구간 합 구하기 (C++) 목차문제입력출력풀이문제 해결 방법코드문제 문제 링크어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다.M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다.그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다.그리고 N+2번째 .. 2025. 4. 12.

티스토리툴바