본문 바로가기

반응형

조합

(4)
[삼성 기출 문제] 백준15686 치킨 배달 문제 링크 어떻게 풀까? 해당 문제는 전형적인 조합 문제입니다.생각해봐야할 과제는 다음과 같습니다. 1. 맵에서 치킨집의 개수를 추출한 후에 비트 조합을 이용해서 m개의 치킨집만을 고른다.2. 사람들이 사는 모든 집에서 현재 선택된 m개의 치킨 집 중에서 최소의 치킨집을 구한 후 더한다. (도시의 치킨 거리를 구한다.)3. 최소의 도시의 치킨 거리 값을 출력한다. 만약, 비트 조합을 만드실줄 모른다면 여기를 참조하세요! 1234567891011121314151617181920212223242526272829typedef struct Cod{ int r,c; } cod; int cNum, pNum;cod company[13];cod people[100]; int getAllDist(){ int visit ..
[삼성 기출 문제] 백준 14889 스타트와 링크 문제 링크 클릭시 이동합니다. 어떻게 풀까? 를 구하는 문제입니다. n 개의 데이터를 스타트 팀, 링크 팀에 넣은 뒤에 두 팀의 능력치를 계산해서 두 능력치의 차이 중 최소의 값을 출력합시다! 참고로, 능력치는 입력에 주어지는 것 처럼 2차원 배열에 저장하실 겁니다!팀의 능력치를 구할 때, i, j가 같은 팀이면 능력치를 (i,j)와 (j,i)의 합으로 구할 수 있습니다!즉, 1번 사람과 2번 사람이 팀이라면, (1,2)와 (2,1)를 더해서 구하면 됩니다! 2차원 for문을 이용하면 1번 사람과 2번 사람의 경우와 2번 사람과 1번 사람의 경우 두 개를 중복으로 확인할 것입니다.이를 피하기 위해서 j는 i+1번 번호 부터 확인하도록 합시다! 저는 비트조합을 이용해서 조합을 구했는데, 이를 확인하시려면 ..
[BOJ] 6603. 로또 로또클릭시 이동합니다. 어떻게 풀까? 조합 문제입니다! 심지어 숫자들도 오름차순으로 들어오기 때문에, 조합 짜는 코드만 잘 짜주시면 됩니다! 참고로, 최대 길이가 13밖에 되지 않으니, 선택했다는 것을 비트로 이용하여 나타낼 수 있습니다! 재귀 함수로 순열을 짜는 방법은 다음과 같습니다. 1. 해당 배열을 선택한다! - 이 경우에는 해당 배열을 선택했다는 select check를 해주고 다음 인덱스를 확인합니다.2. 해당 배열을 선택하지 않는다! - 이 경우에는 아무런 처리를 하지 않고 다음 인덱스를 확인합니다! 이렇게 하면, 마지막에 r이 0이 되거나, n이 r과 같아지는 경우에는 visit을 적절하게 1로 만들면서 visit을 이용하여 선택된 숫자들을 출력하면 됩니다. 코드 12345678910111..
[완전탐색/조합] 비트 연산을 이용하여 조합 만들기 - 비트 조합 예전에 대학생활을 하면서 '로봇 연구회' 동아리 활동을 하면서 아트메가 128을 사용했기 때문에 비트연산을 이용한 경험이 있습니다. 덕분에 프로그래밍을 하면서 비트를 이용해서 문제를 해결한 적이 있는데, 이번에는 그 중에서도 특히 인상 깊었던 '조합 만드는 법'에 대해서 설명하려고 합니다! 우선, 그 전에 비트 연산에 대해서 간단히 알아봅시다. 1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. ex) 0b 1111 & 0b 0011 = 0b 0011 2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.ex) 0b 1100 | 0b 1010 = 0b 1110 3. ~ : 모든..

반응형