code/2019 하계 알고리즘 캠프 (16) 썸네일형 리스트형 1-A-B 백준 14501번 퇴사 (+ 퇴사 2) 알고리즘 캠프에서 풀었던 다른 문제들: 알고리즘 캠프 인덱스 5일동안 풀었던 여러 유형의 백준 문제들 1일차 Brute Force 2일차 BFS 3일차 4일차 5일차 오전(A) A. 15650번 N과 M(2) B. 14501번 퇴사(+ 퇴사 2) 오후(B) A. 16922 로마숫자 만들기 B. 16917번 두 동전 C. 1693.. dongwook-chang.tistory.com 문제 링크: 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ .. 1-A-A 백준 15650번 N과 M(2) 알고리즘 캠프에서 풀었던 다른 문제들: 알고리즘 캠프 인덱스 5일동안 풀었던 여러 유형의 백준 문제들 1일차 Brute Force 2일차 BFS 3일차 4일차 5일차 오전(A) A. 15650번 N과 M(2) B. 14501번 퇴사(+ 퇴사 2) 오후(B) A. 16922 로마숫자 만들기 B. 16917번 두 동전 C. 1693.. dongwook-chang.tistory.com 함께 보면 좋은 문제들: 백준 N과 M(1) ~ (12) 1-A-A 첫번째 문제 백준 15650번 N과 M(2) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다... dongwook-chang.tistor.. BFS 위치별 cost를 함수 밖에서도 알 수 있도록 cost에 대한 자료구조를 qnode struct가 아니라 배열로 선언하기 참고하기 입력 속도 비교 여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 걸리는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김 순위 언어 입력 방법 평균 (초) 1 C11 mmap 0.043 2 C11 fread 0.0799 3 C11 getchar 0.3496 4 C++17 ios_base:: www.acmicpc.net 출력 속도 비교 여러가지 언어와 출력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 총 N개의 줄에 1부터 10,000,000까지의 자연수를 한 줄에 하나씩 출력하는 시간을 측정. 10번 .. 알아놓을 숫자들 문제 case 개수 상한인 1억(약 1초 소요) 1억 = 10^8, > 11! : BF의 순서해법 > 2 ^ 26 : BF의 선택해법 = (1000)^2, > (464)^3, > (100)^4 둘째날 탐색 중 큰 자료구조 인자로 받을 때는 부모에 수정사항이 반영되도 된다면 주소 혹은 &로 넘겨주어 전체 메모리 줄이기 자주 쓰이는 상수는 매크로화로 옮겨오는 실수 줄이기 Brute Force - 순열과 조합 스타와 링크 풀어보기 n! ( = P(n, n) ) P(n, r) C(n, r) Pie(n, r) 경우의수 n! n!/(n-r)! n!/(n-r)!r! n^r t복잡도 O(n!) O(n^r) O(n^min(r, n-r)) O(n^r) 백준풀이 BF - 순서 BF - 선택 lvl의미 선택한 개수 선택지 인덱스 r 간 순서 반영 무시 반영 결과정렬 인덱싱 0부터/N-1부터 선택먼저/비선택먼저 구현 std::next_permutation 혹은 직접 구현 (아래 코드 참조) C(n, r)로 조합 구하고 next_permutation로 순서 정하기 BF(int i, int lvl){ if(lvl > r) return for(;i < n; ++i) BF(i + 1, lvl + 1); } BF(int lvl){ if.. 첫째날 - Brute Force 코딩 관습: 전역변수 프로그램 전반에 걸쳐 공유하는 경우 변치 않는 경우(map의 크기) 변하는 경우(map, min/max_ans) 내가 이해한 바: N! 모든 이전 1 2 다음