본문 바로가기

CS48

[알고리즘 이론] 9. 라인 스위핑 라인 스위핑 공간이나 직선 상에서 한 쪽 시작점을 기준으로 반대편 종료지점까지 스캔하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준을 적용해 주면 정답이 구해지는 형태이다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 예시 라인을 1,3 / 2,5 / 3,5 / 6,7 총 4개를 준다고 가정한다. 라인들을 pair로 저장하고 pair배열에 삽입 후 정렬 처음 pair 의 시작점(1)을 start, 끝점(3)을 end 로 지정 다음 pair인 2,5 에서 시작점인 2가 끝점보다 적으므로 패스, 끝점이 5로 3보다 크므로 끝점을 5로 바꿈 다음 pair인 3,5 에서 시작점인 3이 끝점보다 작고, 5.. 2023. 5. 9.
[알고리즘 이론] 8. 비트마스킹 비트 마스크 알고리즘이 아닌 하나의 기법이다. 정수를 이진수로 표현하고, 비트 연산으로 다양한 문제를 해결해나가는 방법이다. 예시 열쇠가 a, b, c, d, e, f로 6개가 있다고 가정하고, 가지고 있는 열쇠가 a, c, e 일 때 // 가지고 있는 열쇠를 1, 아닌 것을 0으로 표시한다. // -> 열쇠말고 다양한 곳에서 사용 가능하다. // 1 (true), 0 (false) 로도 가능 a b c d e f 1 0 1 0 1 0 비트 연산자 1. AND // & : 대응되는 비트가 모두 1이면 1을 반환한다. 00001111 & 00010101 = 00000101 2. OR // | : 대응되는 비트 중에서 하나라도 1이면 1을 반환한다. 00001111 | 00010101 = 00011111 3.. 2023. 5. 9.
[알고리즘 이론] 7. 백트래킹 백트래킹 제약조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 백트랙(이 후보군은 다시 체크하지 않을 것을 표시) 하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서, 각 루트에 대해 조건이 부합하는지 체크하고, 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지를 쳐버리는 탐색. 알고리즘 문제 추천 N과 M(1 ~ 4) (실버 3) https://www.acmicpc.net/problem/15649 https://www.acmicpc.net/problem/15650 .. 2023. 5. 9.
[알고리즘 이론] 6. 완전탐색 완전탐색 모든 경우의 수를 시도하여 정답을 찾는 방법이다. 무식하게 푼다는 의미로 Brute Force 라고도 한다. 상대적으로 간단하지만 경우의 수가 많아지면 시간이 길어지는 단점이 있다. 1. 단순 Brute-Force 특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함 이 방법으로 풀 수 있는 문제는 많지 않음 2. 비트마스크 각 원소를 두 가지 상태로 분류할 수 있을 때 사용 모든 경우의 수에서 각각의 원소가 포함되거나 포함되지 않는 경우 포함되면 1, 포함되지 않으면 0으로 구분한다 -> 2진수 EX) 원소 n개인 집합의 부분집합 구하기 자세한 건 아래 게시글 https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC.. 2023. 5. 9.

티스토리툴바