BBTY의 공부 기록 BBTY의 공부 기록

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 감기 때문에 평소보다 머리도 안 돌아가고.. 고생고생해서 하나 풀고 자려 했는데 이게 웬걸 틀림... 그래도 힘내서 풀고 새로운 내용이라 포스팅까지 하자는 생각으로 글을 쓴다. 사실 이거 왜 시간 초과가 떴는지는 모르겠다. 사고과정은 다음과 같다. a, b, c, d, e ab, bc, cd, de ... 이런 식으로 하나씩 map에 넣으면서 중복이 아닌 것만 세준다. 반복문도 하나인데 시간 초과 나옴.. 왜인지 모르겠..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 음.. 사실 이거 굳이 포스팅 하려고 하지는 않았는데.. (너무 쉽게 풀려서) 구글링을 해보니 다들 이진탐색으로 풀어서 '뭐지?' 싶어서 더 쉽게 풀고 싶은 다른 사람들에게 도움이 될까 하여 적는다. 처음에는 map를 선언하여 찾았다. 근데 사실 시작 전부터 안될 것 같긴 했다 ㅋㅋㅋ.. value가 같은 ..

이틀동안 이것저것 알아본다고 PS에 손을 대지 않았다. 이틀 안했다고 그새 뻑뻑해진 느낌.. 하루도 거르지 않는 습관을 들이자. https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net map 사용 문제이다. 풀고난 후의 관전 포인트는 '처음에 map을 선언할 때 key와 value의 자료형을 어떻게 지정할 것인가'인 듯 하다. 처음 풀 때도 정답은 나오기는 했다. 그러나 이 문제는 시간 ..

https://bbty97.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F TISTORY 나를 표현하는 블로그를 만들어보세요. www.tistory.com 배수, 약수, 소수 관련 포스팅을 이렇게 많이 할 줄은 몰랐다.. 모두 알고 있는 내용이지만 알고리즘을 어떤 식으로 구현하는지에 따라서 시간 차이가 천차만별인 것을 보고 다각도의 시선이 얼마나 중요한 것인지 다시 한 번 깨닫는다. 이전 소수 문제에서 썼던 알고리즘인 √n 을 다시 한 번 이용했다. 6을 예로 들면, 2부터 모든 가짓수를 세고 3 + 3 = 6 을 발견해낸다. 어차피 (2, 3) 과 (3, 2)의 순서쌍은 같은 것으로 취급되기에 6의..

https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 소수 판별 문제이다. 조금 헤맸는데 이건 방법론적인 문제라 이에 대해서는 아래에서 이야기하려 한다. 단순 소수 판별 문제에 시간을 너무 투자하는 것이 너무 아깝다고 생각 되어 1시간정도 고민해보다가 구글링을 해보았는데.. 이게 웬걸 C++ 풀이가 안나오는 것이었다. 그래서 조금 더 고민해보고 풀어서 내가 C++ 풀이를 올리자고 마음 먹었다. 처음엔 일반적으로 반복문을 통하여 n까지 모두 돌리며 n이상의 소수를 찾으려고 했는데, 입력값을 ..

https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 글을 쓸까말까 하다가 다시 헛짓거리하지 않기 위해 되새김질 하는 의미에서 쓰려한다. 일단 문제는 최대공약수를 이용하는 문제이다. 그림을 그려보거나 조금만 생각해봐도 이건 생각해낼 수 있는데, 내가 문제가 되었던 점은 '지금까지 푼 최대공약수 문제들은 입력값이 두 개밖에 없었는데 이건 너무 많은데 어떡하지?'였다. 그래서 선택한 방법이 브루트 포스 방법으로 모든 최대공약수들을 찾아내어 그 중..

https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 처음 문제를 보자마자 생각이 난 풀이는 고전적인 풀이법이었다. 많이들 알고 있는 풀이일 것이다. 해당 풀이대로 구현을 하니 꽤나 복잡했다. 아래는 코드이다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL..

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 1시간 반 헛짓거리하다 무릎을 탁! 쳤다. 한 50번째 수까지 직접 써보고 패턴을 찾으려 했는데... 대충 감은 오는데 숫자가 커질수록 패턴을 계산하는 게 어려워지는 것이 아닌가..... 나는 진짜 바보인가? 브루트 포스 문제인 걸 모르고 푼 것도 아니고 알고 풀었는데 왜 패턴을 찾으려고 했을까 ㅋㅋㅋ 아무튼 브루트 포스인 걸 깨닫고 나니 문제가 다르게 보였다. 1부터 시작해서 차례대로 666이..