'알고리즘 모음집' 카테고리의 글 목록 (71 Page)
본문 바로가기
728x90
반응형

알고리즘 모음집307

백준 1182 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분 수열 이문제는 1개부터 N개까지 모든 경우를 뽑아내서 더해서 합이 S와 같은 갯수가 몇개 인지 세면되는데 비트로 생각하면 이렇게 뽑히면 되는겁니다. 이렇게 해서 1인부분의 합이 S가 되는 것을 세면 되는 문제로 엄청 쉬워집니다. 무튼 오늘은 아래 소스가 로또 문제랑 비슷하니 로또 문제도 풀어보시고 이문제도 풀어보시면 좋을것 같습니다. 1 2 3 4 5 6 .. 2019. 7. 24.
백준 11723 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 집합문제는 풀이를 했을때 27% 정답비율이여서 뭔가 함정이 있는지 생각을 했습니다. 하지만 함정은 없고 그냥 단순 구현문제 였습니다. 저는 이문제를 풀때 add , remove, check, toggle, all, empty 이 6개의 명령을 구분을 하기위해서 배열에 1번방에 문자가 다른점을 이용해서 배열의 1번방에 따라 조건을 문제에 제시한대로 구현을 했습니다. 딱히 어려운것은 없었던 문제 였던것 같습니다. 토글 부분에 1이면 0.. 2019. 7. 24.
백준 6603 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2 www.acmicpc.net 문제에 보면 모든순열같이 숫자를 배치하는 것은 비슷하지만 대신 오름차순으로만 된것을 뽑아야합니다. 그렇게 하려면 탈출조건을 위해 idx 한개.. 2019. 7. 24.
백준 1339 단어 수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 알파벳에 1부터 10까지 숫자를 부여해서 주어진 식의 합이 최대가 되는 것을 출력하는 것으로 어떻게 보든 모든것을 완전 탐색을 해봐야 아는 문제입니다. A 에도 1 부터 10까지 B 에도 C에도 Z까지 각 1부터 10까지 부여해야 하므로 가장 간단한 완전 탐색 방법 중 하나인 재귀를 이용한 백트래킹을 사용하.. 2019. 7. 23.
728x90
반응형

티스토리툴바