08월 03일 모각코_와팬호 5회차 결과 보고서

2021년 08월 03일 화요일 21:00~24:00

 

🔥 Baekjoon 문제 해결 🔥

 

① 1748 수 이어 쓰기 1 _ Python

 

https://www.acmicpc.net/problem/1748

 문제) 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자릿수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

 

- 처음에 생각한 방법은 반복문과 조건문을 사용하여 처음부터 끝까지 길이를 더해주는 방법이었다.

하지만 시간제한 0.15초로 당연히 시간 초과가 발생하였다.

또, 검색의 힘을 받아 해결한 방법은 일의 자리, 십의 자리, 백의 자리 이런 식으로 생각해보는 방법이었다.

일의 자리 = 1 ~ 끝까지 

십의 자리 = 10 ~ 끝까지

백의 자리 = 100 ~ 끝까지 

이런 식으로 나오는 것을 이용하여 문제를 해결할 수 있었다.

 

 

② 1003 피보나치 함수 _ Python

 

https://www.acmicpc.net/problem/1003

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
fibonacci(0)은 0을 출력하고, 0을 리턴한다.
fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

- 이제 피보나치는 가뿐하다는 생각을 파사삭하게 만든 문제

재귀로 풀어본 결과 시간제한 0.25초라는 벽에 막히게 되었다.

조금의 검색의 힘으로 dp로 해결하면 된다는 말에 코드를 도도독 🙄

이번에는 20%에서 틀렸습니다 라는 결과를 받게 되었다. 왜? Why? 

다시 검색해본 결과 나의 코드와 다른 부분이 있지만 이 부분에서 왜 틀렸습니다가 발생하는지는

아직도 의문이다. 🙄

 

 

③ 2751 수 정렬하기 2 _ PyPy3

 

https://www.acmicpc.net/problem/2751

 

- 똑같은 코드를 Python3로 제출 시 시간 초과 발생

- PyPy3로 제출 시 성공! (sort, sorted 둘 다 성공)

 

 

④ 9935 문자열 폭발 _ Python

 

https://www.acmicpc.net/problem/9935

 

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다.

문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

 

- 내장 함수를 사용했을 때 시간 초과가 발생한다.

- 두 번째로는 stack을 사용하였다. 스택에 넣기 전에 bomb의 마지막 문자와 같은 문자면

stack에 들어있는 앞에 글자들과 비교해서 지우는 방법으로 코드를 작성하였다. 

하지만 이 방법은 시간 초과는 발생하지 않았지만 50%쯤에서 틀렸다고 나왔다.

- 마지막 방법으로는 처음에 stack에 넣고 마지막으로 넣은 것이 bomb의 마지막 문자와 같으면

stack에서 bomb의 길이만큼 비교하여 같으면 지우는 방법으로 코드를 작성하였다.

두 번째 방법과 비슷하지 않은가...? 차이점을 아직도 잘 모르겠다. 😥