알고리즘 스터디 1주차 주제: 정렬 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ ..
알고리즘 스터디 1주차 주제 : 정렬 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 절댓값이 1,000,000보다 작거나 같은 정수 N개가 주어진다. 문제 접근 수 정렬하기 문제와 유사하지만 최대 100만개의 수를 정렬하는 만큼 시간 복잡도가 logN인 알고리즘을 채택해야 합니다. 퀵 정렬은 최악의 경우 O(N^2)의 시간 복잡도를 갖고, 병합 정렬(merge sort)는 메모리가 넉넉하지 않은 환경에서 O(NlogNlogN)의 복잡도를 가지므로 언제나 O(NlogN)을 보장하는 힙 정렬을 선택했습니다. 문제 풀이 C++은 헤더파일에서 다양한 정렬 알고리즘을 제공합니다. 이를 이용해 코드를 짰습니다. 1. 힙을 생성한다. 2. 힙을 정렬한다. 3. 반복자를 이용해..
알고리즘 분류 비트 마스크 solved.ac 티어 silver 3 문제 링크 https://www.acmicpc.net/problem/14889 관련 블로그 포스팅 이 게시글은 코드 플러스 강의 '알고리즘 기초 2/2'의 강의 내용을 기반으로 작성되었습니다. 문제 이해 N 개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제. 즉, 공집합을 제외한 부분 수열을 구해야 하고 부분 수열의 원소를 더한 값이 S가 되는지 확인해야 한다. 문제 접근 N 개의 정수로 이루어진 수열에서 부분 수열 구하기 수열의 부분 수열은 각 원소의 유무로 표현이 가능하다. 수열의 n 번째 원소를 An이라고 했을 때, 부분 수열을 아래와 같이 표..
