♣ 비트마스킹 개념컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 한다. 비트마스크를 사용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다.  ♣ 비트 연산자 ♣ 비트를 이용한 집합 연산 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개의 회의에 대해 회의를 가장 많이 할 수 있는 최대 횟수를 구하는 문제이다. ♣ 문제 해결 먼저 주어진 회의가 끝나는 시간을 기준으로 회의들을 정렬한다. 회의가 끝나야 다음 회의가 들어올 수 있으므로 끝나는 시간을 기준으로 정렬하면 각 회의들의 부분 구조를 만들 수 있다. 시작 시간에 관계 없이 빠르게 끝나는 회의를 먼저 선택해야 회의를 조금이라도 더 많이 진행할 수 있기 때문이다. 회의가 끝나는 시간을 기준으로 정렬..

♣ 투 포인터 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘. 시작점과 끝점 두 개의 점으로 접근할 데이터의 특정 범위를 표현할 수 있다. *대표적인 문제: 특정한 합을 가지는 부분 연속 수열 찾기 - n개의 자연수로 구성된 수열이 있다 - 합이 m인 부분 연속 수열의 개수를 구한다 - 수행 시간 제한은 O(N)이다. 위의 수열에서 합이 5인 부분 연속 수열을 구하려면 경우의 수가 3가지이다. (2, 3), (3, 2), (5) 수열의 모든 구성 요소에 대해 요소를 하나씩 더하는 완전탐색을 할 경우 걸리는 시간이 O2이 되어 시간 초과가 난다. 해결 방법은 아래와 같다. 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2...

♣ 백트래킹 알고리즘 현재 상태에서 가능한 모든 경로를 따라 들어가서 탐색하다가 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 알고리즘이다(방금 왔던 길을 되돌아간다는 의미). 즉 모든 가능성을 시도하는 것이 아니라 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지의 여부를 검사하며 해답을 찾는 것이다. 백트래킹은 보통 재귀함수를 이용하여 구현된다. DFS와 혼동하기 쉬운데, 백트래킹은 불필요한 탐색을 하지 않는다. 하지만 DFS는 모든 경우의 수를 자식 노드가 끝날 때까지 탐색한다. 백트래킹의 특징 어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소 불필요한 경로의 조기 차..