전체 글 (168) 썸네일형 리스트형 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! 모든 백준 14502 연구소 설계: '감염 영역' BFS를 통해 얻는 건 '안전 영역'의 여집합의 크기이기 때문에 해당 집합을 칭하는 '감염 영역'이라는 개념 도입 BFS를 수행할 때 벽(1)의 개수는 고정이기 때문에 '안전 영역'(0)의 최대화는 '감염 영역'(2)의 최소화임 trimming BF에서 현재까지 최소 감염영역의 크기(ma)를 BFS의 인자로 넘겨주고, BFS 중 감염영역이 ma 이상이 되면 어짜피 ma 갱신이 불가함으로(정답에 영향 주지 않음) 탐색 중지 0의 좌표를 배열화 BF body의 for문으로 2차원인 map을 커버하려면 1. '1일 경우 skip', 2. r과 c 모두 인자로 유지하면서 'c가 C - 1이 되면 ++r, c = 0'의 예외처리를 해줘야 한다. BF는 시간 복잡도((R X C)!)가 높기 때.. 경제계획수립 아침 운동이 반토막 나고 말았다. 그 덕인지 오랜만에 20분에 집을 나서 보람찬 하루의 시작이었다. 오전에는 어제 손을 놓자마자 해법이 생각난 미해결 문제를 해결했다. 새로운 문제를 시작하는 도중에 졸려서 잠시 눈을 붙였다. 월간 지출액을 계획하고 커피를 끊기고 결심했다. 신용 지출액을 줄이고, 가변적 소비에 대응하기 위함이다. 얼마나 오래갈지 의문이지만 다시 커피를 마시기 시작했다간 내 신용이 얼마나 더 버텨줄지가 의문이다. 가변적 소비폭을 완충해줄 목돈의 필요성도 느꼈다. 불행히도 은행 대기인원 45명에 대한 정신적 완충은 없었다. 목돈의 마지막 출처인 외화계좌에서 마지막 잔액을 인출했다. 환율이 좀 더 오르면 환전할 계획이다. 옷을 취소했고, 모바일 티머니 정산이 끝나고 챌린져스에서 환급을 받으면 .. D-57 일일 성과표 시각 학습내용 학습결과 소요시간 개념 코딩 백준 5213 과외맨 백준 3184 양 기타 은행 다녀옴 총 학습 시간 5:05 개선점 백준 5213 과외맨 설계: BFS 조건 만족시키기(mapping) BFS의 '비용=1' 조건을 만족시키기 위해 주어진 조각들의 map(pm)을 타일의 map(ts)에 대응시키기 pm(idx = 조각 위치, pm[idx] = 조각번호), tn(idx = 조각 위치, tn[idx] = 타일번호) 2조각이 1타일에 대응되므로 pm과 동일한 크기의 tn배열 선언, 첫 2칸을 1로하고 2칸마다 1씩 증가 pm상 모든 조각에 대해 2조각 씩 뛰어넘으며 이웃 조건 검사해 adj list 구성 ts(idx = 타일번호, ts[idx] = 타일의 이웃 목록 => graph repr; adj list) 수정: 경로 출력하기 qnode를 임의 메모리에 선언x 타일번호 tn으로 접근할 수 있도록 tn을 idx로 삼는 qnode 배열 선언 qs(.. 백준 3184 양 설계: map상 obj인 울타리, 양, 늑대의 존재여부를 나타내는 bool 2차원 배열 선언 vs map 2차원 배열 선언 전자는 한 위치에 여러 obj 존재 가능할 경우 유용 vs 후자는 한 위치에 하나의 obj만 존재 가능할 경우 유용 수정: 탐색시 '기방문 위치 skip' 누락 switch의 각 case별 break 누락 소요시간: 개선: 방문 여부를 나타내는 별도 배열 선언 대신 map에 '#'로 표시 map상 모든 위치에 대해 탐색하는 대신 'o', 'v'가 존재하는 위치만 탐색 // BFS버전 #include #include #include using namespace std; int dr[] = { -1, 0, 1, 0 }; int dc[] = { 0, 1, 0, -1 }; #define I.. D-59 일일 성과표 시각 학습내용 학습결과 소요시간 개념 코딩 백준 2933 미네랄 약 3시간 백준 5213 과외맨 진행중 약 1시간반 기타 총 학습 시간 약 8:00 개선점 측정이 미흡 코딩 속도 느림 코딩 체계적이지 않음 어렴풋이 기억나는 내용이 많음 -> 빨리 채울 것! 이전 1 ··· 15 16 17 18 19 20 21 다음
