♣ 분할정복(divide and conquer)하나의 문제를 작은 문제로 분할하여 해결하는 방법을 의미한다. 퀵 정렬, 합병 정렬, 이진탐색, 선택 문제, 고속푸리에 변환 문제들이 대표적으로 분할정복 알고리즘으로 해결할 수 있는 문제들이다.   ♣ 분할정복 설계1. Divide문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할때까지 나눈다.  2. Conquer각 하위 문제를 재귀적으로 해결한다. 하위 문제가 더 이상 나눌 수 없는 단위가 되면 탈출 조건을 설정하여 해결한다.  3. CombineConquer한 문제들을 통합하여 원래의 문제의 답을 얻어 해결한다.   ♣ 분할 정복의 특징 및 장단점1. 분할된 작은 문제는 원래 문제와 성격이 동일하다2. 분할된 문제는 서로 독립적이다. 3...

♣ Transfer LearningDownstream task = 현재 풀고자 하는 문제Pre-trained task = Downstream task와 비슷하지만 다른 문제  Downstream task에서 데이터가 부족한 경우, 데이터가 풍부하면서도 Downstream과 어느 정도 연관된 Pre-training task에 모델을 사전학습시켜서 Downstream task에 도움이 될 수 있는 feature들을 모델에 학습시킨다. 즉 pre-training task에 대해 이미 학습된 모델이 있을 때, 해당 모델의 weight로 초기화하여 downstream task에 대해서 학습(fine-tuning)하는 방법이다.  전이학습을 사용하는 이유1. Random하게 초기화해서 학습하는 것보다 학습 수렴 속..

♣ 비트마스킹 개념컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 한다. 비트마스크를 사용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다.  ♣ 비트 연산자 ♣ 비트를 이용한 집합 연산 1. 원소 추가현재 상태 bit가 있을 때 x번 원소를 추가한다고 하자. 현재 상태 bit에서 x번 비트를 1로 바꿔줘야 한다. bit = bit | (1 2. 원소 삭제현재 상태 bit에서 x번 원소를 삭제한다. 현재 bit에서 x번 비트를 0으로 바꿔줘야 한다. bit = bit & ~(1 3. 원소 토글x번 비트가 1이면 0, 0이면 1로 바꾼다. bit = bit ^ (1  ♣ 백준 알고..

♣ 문제 이해  문제가 별 것 아닌 것처럼 보여서 도전했다가 '틀렸습니다'를 여섯 개나 적립했다. 이 문제에서는 조건 파악이 중요한데, p의 길이가 100,000까지 갈 수 있으므로 코드의 시간 효율성을 고려해야 한다. 또한 출력 결과를 보면 따옴표 사이에 빈칸이 없다. 즉 리스트로 출력하면 안되고, str 형태로 출력해야 한다.   ♣ 실수1(시간 초과) 위의 코드를 사용하면 16%에서 시간초과가 나는데, R이 나올 때마다 deque를 reverse 했기 때문이다. 100,000 개의 p가 있다면 수없이 많이 reverse 해야 하므로 시간초과가 난다.   ♣ 실수2(리스트 실수) 시간 초과를 해결하자 이번에는 '틀렸습니다' 가 떴는데, 문자열로 출력해야 하는 것을 놓쳐서 list로 출력한 탓이었다. ..

♣ 휴리스틱불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론의 방법을 의미한다.  휴리스틱은 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다. 휴리스틱 관련 기법가지치기(pruning) 기법Simulated Annealing (담금질 기법)Genetic Algorithms (유전 알고리즘) ♣ 그리디 알고리즘 vs 휴리스틱 그리디 알고리즘은 stage를 분할해 각 스테이지별로 최적해를 찾는다.  하지만 마지막 결과가 최적해임을 보장하지는 못하기 때문에 결과가 최적해인지 검증하는 단계가 필요하다. 마찬..

♣ 그리디 알고리즘 문제 해결의 조건 1. 각 단계에서 최선의 선택을 해야 한다. 2. 최적의 부분 구조를 만들어야 한다. 즉 전체 문제를 작은 부분으로 나누어 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것이다. ♣ 백준 알고리즘 1931번 이 문제는 N개의 회의에 대해 회의를 가장 많이 할 수 있는 최대 횟수를 구하는 문제이다. ♣ 문제 해결 먼저 주어진 회의가 끝나는 시간을 기준으로 회의들을 정렬한다. 회의가 끝나야 다음 회의가 들어올 수 있으므로 끝나는 시간을 기준으로 정렬하면 각 회의들의 부분 구조를 만들 수 있다. 시작 시간에 관계 없이 빠르게 끝나는 회의를 먼저 선택해야 회의를 조금이라도 더 많이 진행할 수 있기 때문이다. 회의가 끝나는 시간을 기준으로 정렬..