본문 바로가기

알고리즘/백준333

[백준 5582] 공통 부분 문자열 (C++) https://www.acmicpc.net/problem/5582 문제두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAX.. 2024. 5. 19.
[백준 1662] 압축 (C++) https://www.acmicpc.net/problem/1662 문제압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오. 입력첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다. 출력첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다. 문제 풀이스택을 이용한 문제.현재까지의 압축되지 않은 문자열의 길이를 저장하는 스택 length와 압축 시 나타나는.. 2024. 5. 18.
[백준 24464] 득수 밥 먹이기 (C++) https://www.acmicpc.net/problem/24464 문제프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다. 늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다.첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다.어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다.어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다.오늘 간 식당은 다음날 가지 않는다.오늘 간 식당과 이웃한 식당은 다음날 가지 않는다.만약 2번 식당을 오늘 갔다면, 다음날 1, 2, 3번 식당은 가지 않는다. 따라서 새로운 느낌을 받으려면 4번 식당을 가거나 굶어야 한다... 2024. 5. 17.
[백준 1520] 내리막 길 (C++) https://www.acmicpc.net/problem/1520 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.  지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길.. 2024. 5. 16.
[백준 2011] 암호코드 (C++) https://www.acmicpc.net/problem/2011 문제상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 .. 2024. 5. 15.
[백준 26152] 플래피 버드 스코어링 (C++) https://www.acmicpc.net/problem/26152 문제플래피 버드는 장애물을 피해 최대한 멀리까지 도달하는 게임이다.하나의 장애물을 피할 때마다 1점씩 점수를 얻게 된다. 게임에는 총 N개의 장애물이 존재하고, i번째 장애물은 두 개의 장애물로 표현된다. 상단 장애물 끝 지점의 위치는 𝐴𝑖로 나타내어지고, 하단 장애물 끝 지점의 위치는 𝐵𝑖로 나타내어진다.플래피 버드 고수 세정이는 장애물이 어떤 식으로 주어지든 플래피 버드를 조작해 피할 수 있다. (단, 플래피 버드의 크기가 장애물의 틈새보다 클 경우에는 세정이도 장애물을 피하지 못한다.) 즉, 플래피 버드의 크기 𝑤가 장애물의 틈새보다 클 경우에는 장애물을 피하지 못한다. 이때, 장애물을 피하지 못하면 게임이 바로 끝나게 된.. 2024. 5. 14.
[백준 14247] 나무 자르기 (C++) https://www.acmicpc.net/problem/14247 문제영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다. 입력첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.다음 줄에는 첫.. 2024. 5. 13.
[백준 10799] 쇠막대기 (C++) https://www.acmicpc.net/problem/10799문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.이러한.. 2024. 5. 12.
[백준 1360] 되돌리기 (C++) 문제민식이는 다음과 같이 두 개의 명령만 지원하는 새로운 텍스트 에디터를 만들었다.“type c" : 현재 글의 가장 뒤에 문자 c를 추가한다.“undo t" : 이전 t초동안 수행된 작업을 역순으로 되돌린다.처음 텍스트 에디터는 비어있다.예를 들어, 다음과 같은 명령을 진행했다고 하자.1초 : type a2초 : type b3초 : type c5초 : undo 33초가 끝날 때, 텍스트는 "abc"이다. 5초때, 이전 3초동안 한 작업을 역순으로 되돌려야 한다. c는 지워지고, b도 지워질 것이다. 따라서 a만 남는다.되돌리기가 되돌리기 될 수도 있다.예를 들어1초 : type a2초 : type b3초 : undo 24초 : undo 22초일 때, 텍스트는 “ab"이다. 3초때 모든 것이 되돌리기 되.. 2024. 5. 10.

티스토리툴바