1. 최단 경로 전략 너비 우선 탐색은 최단 경로 문제를 푸는 가장 직관적이고 유명한 방법이지만, 모든 최단 경로 문제를 너비 우선 탐색만으로 풀 수 있는 것은 아니다. 문제에 따라서는 너비 우선 탐색보다 다른 탐색 알고리즘이 더 강력한 경우가 있다. 2. 15- 퍼즐 7 8 4 1 2 3 5 6 9 10 11 12 13 14 15 => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 X 4 격자에 끼워진 열다섯 개의 숫자 타일을 순서에 맞게 맞추는 퍼즐이다. 빈 칸에 상하좌우로 인접한 타일 하나를 빈 칸으로 밀어넣는 것을 한번의 움직임이라 할 때, 이 퍼즐을 해결하기 위해 필요한 최소 움직임을 구하는게 오늘의 목적이다. 이 문제를 풀기 위한 첫번째 단계는 게임판의 상태를 정점으로 표..

1. 비트 마스크 문제 부울 배열들을 비트 마스크 로 풀어내는 문제이다. 과목 => 선수과목 학기 => 과목 학기마다 선수과목이 포함되어 있는지 확인하고. 강의를 들을 수 있는 과목을 선택하여 조합 탐색하면 쉽게 답을 구할 수 있다. tmpSelect = semester[j] & (~select); => 이번 학기에 들을 수 있는 수업중 이미 수강한것은 제외시킨다. => 최상위 비트또한 반전되어 없어진다. => 모든학생이 이번 학기에 들을 수 있는 강의들 if((tmpSelect&(1

1. 완전 탐색 이 문제는 BOARDCOVER에서 문제를 풀었듯이 완전 탐색으로 해결 할 수 있다. 각 차례마다 사용 가능한 모든 블록들을 모든 위치에 넣어보면서 한번이라도 짝수 차례일때 블록을 못넣으면 함수를 종료시키면 된다. 2. 비트 마스크를 사용한 동적 계획법 이 문제는 주어진 게임판의 상태에 따라 승패가 좌우된다. 이전 까지의 블록의 배치와 지금이 누구 차례인지 알 필요 없다는 것이다. 게임판은 5*5배열로 '#' 과 '.' 두 상태가 있으므로 비트마스크로 배열을 하나의 정수로 표현할 수 있다. 이 정수 하나로 메모이제이션이 가능해지고 완전 탐색에서 더욱 수행시간을 최적화 시킬 수 있다. 3. 비트마스크를 사용한 블록 배치 가능 유무성 판단 이 문제에서 블록의 형태는 L자 형과 | 형 ㅡ 형 이..

1. 완전 탐색 이 문제는 먼저 문자열들이 주어졌을 때 모든 문자열이 어떤 문자열에 얼마나 곂칠 수 있는지 계산해야한다. 이 계산은 모든 문자열의 개수 n에 대하여 overap[A][B] = A다음으로 B가 왔을때 중복되는 것을 제외한 최소의 길이 에 저장되어진다. 이 배열의 초기는 A = -1일때 B는 자기 자신의 길이를 나타낸다. 이후 계산할 restore()함수에서 이것을 더하여 최소 값을 나타낸다 next는 모든 문자열을 가리키며, 이미 쓴 문자열일경우 패스한다. restore(last, used) = min( overlap[last][next] + restore(next, used + (1

1. 완전 탐색 원래 가격은 다음에 해당해야한다 1. 바뀐 가격의 숫자들로만 이루어져있다. 2. 바뀐 가격보다 싸야한다 3. m의 배수야 한다. 다음은 이런 정보들을 통하여 완전 탐색하는 코드이다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 #include #include #include #include using namespace std; //current p..

1. 비트 마스크 이진법 관련 연산들을 아주 빨리 할 수 있도록 정수의 이진수 표현을 자료 구조로 쓰는 기법 (엄밀하게 자료 구조라고 할 수 없음) 2. 비트 마스크의 장점 - 더 빠른 수행 시간 : 대부분 연산은 O(1)에 구현된다. - 더 간결한 코드: 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문 - 더 작은 메모리 사용량: 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있다. - 연관 배열을 배열로 대체: map같은 연관 배열 객체를 단순 배열을 사용해 같은 정보를 표현 3. 비트 연산자 - AND연산: 두 비트가 모두 1인 경우. 1반환 - OR연산: 두 비트중 하나라도 1인 경우. 1반환 - XOR연산: 두 비트중 하나만 1인 경우 (1의 개수가 홀수). 1반환 - NOT연산..