분할 정복, 브루트 포스 - N = 40 이면 공집합을 뺀 부분집합의 갯수는 2^40 - 1... - 그대로 완전 탐색을 할 수 없으니 두 집합으로 나눠서 세면 된다- 답이 될 수 있는 경우의 수가 int를 초과하므로 long long 으로 해줘야 한다. 이것 때문에 몇 번을 틀렸다ㅜㅜ 풀이 1. 입력받은 40개의 정수를 반으로 나눈다. 2. 두 개로 나눈 정수들을 가지고 집합을 만든다.3. 집합을 만들 때 공집합을 제외시키고 합이 S 인 경우를 세준다.4. 만든 집합들을 정렬하고 upper_bound, lower_bound를 이용해 갯수를 센다. 소스 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454..
BFS - 무방향 그래프의 BFS를 수행하면 된다.- 가능한 BFS 방문 순서가 여러가지 이므로 신경을 써줄 필요가 있다. 풀이 1. 조건에 따라 큐에 1을 삽입하고 1을 방문처리한다. 2. 큐의 현재 노드에 연결된 다음 노드들을 확인하고 set에 넣어준다.3. 주어진 BFS 방문 순서대로 확인한다. 이 때, 유효한 노드면 큐에 삽입하고 아니라면 0 출력하고 끝낸다.4. 방문 순서 배열의 인덱스를 갱신한다. 소스 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include #include #define FOR(i,a,b)..
정렬, 이분 탐색 - 정렬하고 나서 높이가 500000개 이므로 높이 하나 씩 탐색하는 방식으로 풀었다.- 다른 사람들의 코드를 보니 입력 받자마자 배열에 갯수를 추가하는 방식으로 풀 수도 있더라. N이 200000개 밖에 안되니 충분히 가능한 풀이고 내 풀이보다 더 빠르다. 풀이 1. 석순과 종유석을 각각 배열을 만들어 입력받는다 2. 두 배열을 정렬한다.3. 아래 식에 따라 높이 1 부터 H 까지 수행한다. 높이 1 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 0 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 H - 1 이하 갯수)높이 2 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 1 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 H - 2 이하 갯수)...높..
수학, 구현 문제 며칠을 고민해도 왜 시간 초과가 나는지 몰랐는데 N = 1 인 경우를 체크 안해서 틀린거였다. ㅜㅜ '엣지 케이스' 체크는 필수라는 것을 다시 한 번 깨달았다. 순열을 직접 나열해보고 구간을 쪼개서 규칙성을 찾으면 되는 문제다. 맨 처음에 오는 숫자가 뭐 일 때 몇 가지가 있고 그 다음에 올 수 있는 수는 몇 가지...... 쪼개 보면 활로가 보인다. 단지 좀 귀찮다. ex) N = 5 일 때 24번째 순열을 찾아보자. 전체 경우의 수는 5! = 120가지 맨 처음 올 수 있는 숫자들 (편의상 0번째 부터 카운트, 즉 23번째를 찾아야 한다) 1 : (5-1)! = 24가지 0번째 ~ 23번째2 : (5-1)! = 24가지 24번째 ~ 47번째3 : (5-1)! = 24가지 48번째 ~..
- Total
- Today
- Yesterday
- 프로그래밍 온라인 강의
- 자료구조
- 운영체제
- 개발자 취업
- 패스트캠퍼스
- Fast Campus
- #패스트캠퍼스 #프로그래밍대학생서포터즈 #올인원패키지 #컴퓨터공학 #성공하는프로그래밍공부법
- 코딩 면접
- 올인원 패키지
- 컴퓨터공학
- c언어
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |