본문 바로가기

개발65

[알고리즘 이론] 10. 투포인터 투포인터 선형 시간으로 알고리즘을 풀 수 있게 만들어주는 알고리즘이다. 연속적인 값들을 이용해 푸는 문제에 적합하다. 원리 배열의 하나의 인덱스를 가리키는 start 점과 end 점 두 개를 만든다. 처음 start 와 end 는 0으로 초기화. start 부터 end까지 합을 구해서 sum에 저장한다. -> 처음엔 0이 저장 배열을 도는데 세 가지 조건으로 돈다 sum == 찾고자 하는 값 -> 찾고자 하는 값이 나왔으니 count를 1 늘려주고, sum 값에서 start 인덱스 값을 빼주고 1을 늘려준다. 그리고 end 값을 1 더한 후 그 인덱스의 값을 sum에 더해준다. -> 문제를 풀어보면 이해할 수 있다. sum sum이 더 작으니까 start값은 그대로 두고, end.. 2023. 5. 9.
[알고리즘 이론] 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.

티스토리툴바