본문 바로가기

알고리즘/백준336

[백준 22859] HTML 파싱 (C++) https://www.acmicpc.net/problem/22859 문제웹 크롤링을 하여 HTML을 가공하는 프로그램을 만들려고 한다. HTML은 아래와 같이 구성되어있다. (문제 일반화를 위해 실제 HTML 소스 코드 및 태그가 실제 존재하는 것과 다를 수 있다.) paragraph 1 paragraph 2 Italic Tag paragraph 3 Bold Tag end. paragraph 4 paragraph 5 Italic Tag 2 end. HTML에는 여는 태그  로 시작하여 닫는 태그  로 항상 끝나고, ,  사이에 하나의 문단이 존재하고, ,  사이에 하나의 문장이 존재한다. ,  사이에는 main.. 2024. 8. 18.
[백준 9184] 신나는 함수 실행 (C++) 문제재귀 호출만 생각하면 신이 난다! 아닌가요?다음과 같은 재귀함수 w(a, b, c)가 있다.if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오. 입력입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. 출력 입력으로 주어진 각각의 a, b, c에 대해서, w(a.. 2024. 8. 17.
[백준 6118] 숨바꼭질 (C++) https://www.acmicpc.net/problem/6118문제재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다. 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!입력첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어진다.이후 M줄에 걸쳐서 A_i와 B_i가 공백을 사이에 두고 주어진다. 출력출력은 한줄로 이루어지며, 세.. 2024. 8. 16.
[백준 24524] 아름다운 문자열 (C++) 문제당신은 문자열 𝑆를 선물 받았다. 하지만 당신은 오직 문자열 𝑇만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, 𝑇 역시 모든 문자가 서로 다르다.그러던 당신에게 좋은 생각이 떠올랐다. 바로 𝑆의 문자들을 골라내서 𝑇를 만드는 것이다! 당신은 𝑆에서 문자들을 골라내서 𝑆에서의 순서대로 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 𝑆의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, 𝑆가 "aabb"이면 첫 번째 문자 "a"와 세 번째 문자 "b"를 골라 문자열 "ab"를 만들고, 다시 두 번째 문자 "a"와 네 번째 문자 "b"를 골라 문자열 "ab"를 만들 수 있다.당신은 𝑇를 가능한.. 2024. 8. 15.
[백준 2671] 잠수함식별 (C++) https://www.acmicpc.net/problem/2671문제일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 0과 1로 표시한다.또, 한 특정한 소리의 반복은 ~로 표시한다. 예를 들어 x~는 x가 한번 이상 반복되는 모든 소리의 집합을 말하고, (xyz)~는 괄호 안에 있는 xyz로 표현된 소리가 한번 이상 반복되는 모든 소리의 집합을 말한다. 다음의 예를 보라.1~ = {1, 11, 111, 1111, ..., 1...1, ...}(01)~.. 2024. 8. 14.
[백준 16120] PPAP (C++) https://www.acmicpc.net/problem/16120문제bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.P는 PPAP 문자열이다.PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라. .. 2024. 8. 13.
[백준 20955] 민서의 응급 수술 (C++) 문제민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서는 놀라 자빠질 수밖에 없었다. 한 학생이 꾸벅꾸벅 졸다가 책상에 머리를 아주 세게 박았기 때문이다. 한시라도 수술이 시급한 상황, 민서는 의사가 되어 수술을 집도하기로 결심하였다.사람의 뇌는 수백억 개의 뉴런으로 구성되며, 각 뉴런은 시냅스를 통하여 연결된다. 민서의 진찰 결과, 학생은 뇌 속의 일부 뉴런의 연결이 끊어져 잠이 든 것으로 확인되었다. 끊어진 시냅스만 복구된다면 학생은 잠에서 깨어나겠지만, 알다시피 민서는 컴퓨터공학과 교수이다.민서는 끊어진 시냅스를 복구하는 대신 뇌 속의 모든 뉴런을 하나의 트리 형태로.. 2024. 8. 12.
[백준 30804] 과일 탕후루 (C++) https://www.acmicpc.net/problem/30804문제은하는 긴 막대에 𝑁개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 𝑆1, 𝑆2, ⋯, 𝑆𝑁번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 𝑎개, 뒤에서 𝑏개의 과일을 빼면 𝑆𝑎+1, 𝑆𝑎+2, ⋯, 𝑆𝑁−𝑏−1, 𝑆𝑁−𝑏번 과일, 총 𝑁−(𝑎+𝑏)개가 꽂혀있는 탕후루가 됩니다. (0 ≤ 𝑎,𝑏; 𝑎 + ?.. 2024. 8. 11.
[백준 13909] 창문 닫기 (C++) https://www.acmicpc.net/problem/13909문제서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)결과적으로 마지막에 열려 있.. 2024. 8. 10.

티스토리툴바