종종 사용하는 std::binary_search와 그 친구들(lower_bound, upper_bound)의 구현입니다.이 친구들은 헤더에 있습니다. 평소 쓰던 스타일을 그대로 작성하여 올립니다.binary_search가 왜 그 lower_bound와 key가 같은지만 비교하는 지는, 다른 글에서 설명하였다. [보기]코드

저는 quick sort를 기반으로 구현했고, 그 중에서도 중간값이 아닌 (위치가) 중앙에 있는 값을 사용했습니다.이 정도만 구현해도 많은 문제는 생기지 않았습니다. 다만 실제 std::sort 는 구조가 조금 다른 것으로 알고 있습니다. 크기가 100개 이하인 케이스는 insertion sort를 사용하는 등 최적화를 위해서 수정했다고 하네요. template 함수로 작성했기 때문에, 타입은 별도로 명시하지 않아도 됩니다.int형 배열 a[100]에 대해서도, std::sort 함수 쓰듯이 sort(a, a+100) 이라고 호출해도 동작합니다. 이전 게시글에서 구현한 vector를 파라미터로 넘겨도 동작합니다. 즉, sort(vec.begin(), vec.end()) 가능합니다.코드

STL 라이브러리를 사용할 수 없는 환경(시험장 등)에서 vector를 간단하게 구현하는 코드입니다.크기가 동적으로 관리되는, STL 중 정말 많이 사용되는 편리한 sequence container이죠. 큰 기능은 최대한 넣지 않았고, 기존의 vector의 사용 인터페이스와 최소한으로 비슷하게 작성한 것입니다.기본 생성자 몇개와, push_back(), pop_back(), clear() 등의 기본적인 함수가 있고, begin(), end()와 같은 반복자(iterator)들은 실제 반복자는 아니고 비스무리하게만 만들었습니다. 그래도 구조가 같아서, sort(arr.begin(), arr.end()) 를 그대로 사용해도 돌아갑니다.코드

※ 정답과 풀이가 포함된 스포일러가 있습니다. [ 문제적 남자 : 브레인 유랑단 13회, 역대급 신비로운 문제]문제와, 이번 문제는 정말 신기하고 신비로웠다.서로 전혀 다른 두 풀이가 같은 답을 만들어냈다.우선 두 정사각형 모두, 가로줄과 세로줄, 대각선줄의 합이 같도록 수를 채워야했는데 그 답으로 위와 같이 채워진 것이다. 규칙 (문제의 정답)왼쪽 사각형에 있는 한 칸의 수를 영어로 적었을 때, 그 단어의 길이가 오른쪽 사각형의 같은 칸에 적혀 있는 것이다.그러면서 모든 줄의 합이 같게 유지된 것이다.오현민은 등차수열로 접근해서 왼쪽 사각형을 풀고, 오른쪽에서 가능한 모든 경우의 수를 추린 후 정답을 찾았다.여기서 나는 의문이 생겼다.그럼, 이런 (두) 사각형은 얼마나 더 있을까? 탐색1부터 99까지의..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu예전 기억으로는, 삼성 SW 역량 테스트 준비용 샘플 문제가 하나밖에 없었는데 뭔가 많이 추가된 모양이다.이번 문제는 그 중 하나이다.삼성 SW 역량 테스트에는 이런 백트래킹류의 탐색 문제가 자주 나오는 것 같다.문제문제를 요약하자면, 세로 길이가 D이고 가로 길이가 W인 2차원 평면에서, 특정 조건에 맞추기 위해 어떤 행을 모두 A(0) 또는 B(1)로 바꾸는 횟수를 최소로 하고 싶다는 것이다.여기서 조건은, 모든 세로줄에서 같은 종류끼리 K개 이상 연속으로 붙어 있으면 되게 만드는 것이다. 어떤 행을 선택하는 조합이 여러개이므로 ..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3lS6aF-MDFAWJ문제별표(*) 또는 0~9 숫자가 3개 적힌 카드가 N개 있을 때, 숫자끼리 연결되게 이어 붙여서 그 때의 모든 숫자의 합이 가장 큰 것을 구하는 문제이다. 여기서 별표(*)는 숫자를 연결하지 못하도록 만드는 구분자라고 생각하면 된다. 단순해보이지만 케이스를 제대로 생각못해서 여러번 시도 끝에 맞췄다.풀이는 브루트 포스(Brute force)이다. 먼저 숫자 카드는 아래처럼 6가지의 케이스가 있을 것이다. 편의상 (a) + (b) = 12312* 와 같이 적겠다. 숫자로만 이루어진 (a)는 어디에든 붙을 수 있으니, 그냥 무조건 더해..

링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_문제경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.항상 위쪽 또는 왼쪽까지 도착..