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

C++ 헤더에 binary_search()라는 함수가 정의되어 있다. 이름만 봐도 딱 이진탐색임을 알 수 있을 것이다. 이런 함수가 존재하는지 방금 처음 알았는데, 자세히 뜯어보기로 했다. https://cplusplus.com/reference/algorithm/binary_search/ https://cplusplus.com/reference/algorithm/binary_search/ function template std::binary_search default (1)template bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);custom (2)template bool binary_search (For..

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이..

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 굉장히 쉬운 문제인데 헛짓거리를 오래 해서 정신차릴 겸 써보려 한다. 성공했긴 한데 처음에 너무 멍청하게 풀었다. int형 배열과 char형 배열의 입력값에 혼동이 와서... 예를 들어 123을 입력 받을 경우 int형 배열은 0번째 칸에 123을 입력받는 반면, char형 배열은 0번째 칸에 1, 1번째 칸에 2, 2번째 칸에 3을 입력받는다. char형 배열을 순간 int형 배열로..

코딩 테스트 관련 포스팅은 당초 계획에 있지는 않았으나, 1. 풀었지만 다른 사람의 풀이가 너무 좋은 경우 2. 풀지 못하고 다른 사람의 풀이를 참고한 경우 에는 정리 겸 글로 남기는 것도 나쁘지 않을 것 같다고 판단하여 하나씩 채워보려 한다. 이번 문제는 백준 1018번이다. https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 좌측 상단 모서리를 기준으로 B인지 W인지 체크한 후, 체스판을 만들어서 최솟값을 ..