분할 정복 : Divide and Conquer

분할 정복은 큰 문제를 작은 문제로 나누어 해결하는 기법인데, 문제의 사이즈가 바뀔지언정 문제의 내용이 바뀌진 않다보니 재귀와 연관지어서 많이 공부하게 된다.아주 간단한 분할 정복의 예제는 병합 정렬이 있다.병합 정렬은 기존의 정렬 대상으로 주어진 배열을 더 이상 나눌 수 없을 때까지 분할한다.더 이상 나눌 수 없는 경우부터 각 배열을 정렬한다.나눈 배열들을 병합하며 정렬된 형태로 마무리한다.분할 정복의 시간 복잡도는 n logn이다. 효율적인 정렬 알고리즘 중 하나 이다.전체적인 진행구조는 이렇게 된다 :분할 : 큰 문제를 여러 개로 나눈다.정복 : 나눠진 작은 문제를 각각 독립적으로 해결한다. 보통은 재귀함수를 사용한다.결합 : 작은 문제들의 해답을 모아 기존 문제의 해답을 도출한다.특징은 이렇다.작..

• format_list_bulleted 별 잡다
• · 2025. 3. 21.

[PY] 2805 : 나무 자르기

https://www.acmicpc.net/problem/2805뭘 해달란거야 하고 쭉 보니, 일단은 나무 자를 정도를 특정 할 수 있어야 할 것 같았다.특정하는 방법 중 가장 빠른 방법은 이분 탐색이다는걸 알고 있다면 뭘 해야할지 조금씩 감이 잡힌다.간단하게 풀이하면 이렇다.입력받은 나무 길이 중 최대 수치를 따로 갖고 있기로 한다. 이것을 maxTree라고 하자.0부터 maxTree는 자를 수 있는 절단기의 선택 범위가 된다. 이중에서 어떻게 자르겠다라고 가정했을 때, 자른 후의 나타난 내용을 확인한다.이 때 생각 해야 할 것은, 절단기의 높이를 정해두었는데 그보다 낮은 나무에 대해선 잘리지 않을 것이다. 그래서 나무의 높이와 절단기의 높이를 계산 했을 때, 음수로 넘어가는건 무효 숫자로 판단하고 빼..

• format_list_bulleted 문제풀이
• · 2025. 3. 21.

[PY] 1920 : 수 찾기

https://www.acmicpc.net/problem/1920이분 탐색을 아느냐 정도로만 묻는 간단한 문제다.내가 앞에서 적은 글 중 이분 탐색을 다루는 내용이 있다 : https://hyeonistic.tistory.com/22 이분 탐색 (Binary Search)이분 탐색에 대해 논해보자. 둘로 나눠서 검색을 시도하는 이 내용은 n고개 게임에서 쉽게 찾을 수 있다.생각하는 숫자를 n고개 안에 맞추는 게임은 숫자를 제시하면 업, 다운을 제시해서 범위를hyeonistic.tistory.com어느 배열을 대상으로 검색해야 할지 다소 혼란스러웠지만 큰 문제는 아니었다.import sysdef func(arr, target, str, end): if(str > end): return 0..

• format_list_bulleted 문제풀이
• · 2025. 3. 21.

이분 탐색 : Binary Search

이분 탐색에 대해 논해보자. 둘로 나눠서 검색을 시도하는 이 내용은 n고개 게임에서 쉽게 찾을 수 있다.생각하는 숫자를 n고개 안에 맞추는 게임은 숫자를 제시하면 업, 다운을 제시해서 범위를 줄여나간다.일정한 범위 내에서 상대가 숫자를 정했을 때 나는 그 범위의 절반을 딱 잡아서 부른다. 그리고 업 다운에 따라 검색 범위를 좁혀 나간다.이렇게 장황하게 써보니 떠오른게 이분 탐색은 정렬이 기본 전제 되어 있어야한다. 정렬이 되어있지 않으면 내가 특정한 위치를 찍어서 더 크다, 작다를 논 할 수 없기 때문이다.그리고 이분 탐색은 범위를 반으로 나누고 그대로 함수에 매개변수로 넣어 타고 들어간다는 점에서 합병 정렬과 약간 유사한 면이 있다.더 요약해서, 이분 탐색은 탐색 중 나오는 결과에 기반해 검색 범위를 ..

• format_list_bulleted 별 잡다
• · 2025. 3. 20.

WIL 01

미니 프로젝트가 3박 4일인 것은 사실 목요일로 sync를 맞추기 위한 의도도 들어있다는 느낌이다. 휴일도 잘 없을 상황, 어찌저찌 쥐죽은듯 하루를 성실히 보내려고 해야겠다. 어쨌든 노력한 것이 바로바로 와주면 좋겠지만 그 피드백을 견디는 시간은 누구에게든 즐거운 시간은 아닐 것 이다.주 단위로 갱신되는 아이템은 아래와 같다.알고리즘 문제 목록특정 책의 진도를 빼야 하는 범위특정한 컴퓨터 지식 키워드지식 키워드 중에서 배열이 있었는데, 이 배열을 확실히 하겠다고 누군가 정리해 둔 문제 목록 중 배열만 다룬 것을 쫙 풀기는 했다.분명 도움이 됐다고 생각하지만, 뭔가 시간이 허망하게 날아간 느낌도 들고. 어찌 됐건 무언가 남아야 하지 않을까 생각하기 때문이다.내가 원하는 것은 한 키워드에 겹치는 Task를 ..

• format_list_bulleted WIL
• · 2025. 3. 20.

정수론

정수론은 수학에서 원래 수학에서 다루던 이야기인데, 자연수에 대한 깊이 있는 내용을 다룬다.많은 알고리즘 문제와 관련이 있고, 실무에서도 자주 사용된다.아래에 설명 할 것은 정수론 내에 어떤 부분이 주로 고려 대상인지에 대해 논한다.소수 판별에라토스테네스의 체 (Sieve of Erathosthenes)자연수 n이 주어지면 1-n까지를 모두 배열에 깔아놓고, n까지의 소수들을 구한다. 소수의 배수는 100% 소수가 아닌 것이니 지운다. 1은 이도저도 아니니 지운다. 이렇게 하면 1-n까지의 모든 소수를 구 할 수 있다. 현재까지는 이게 제일 빠르다.소인수 분해주어진 수를 소수들의 곱으로 분해하는 방법으로, 암호학에서 주로 많이 사용된다.. 라고 설명하고 있다. RSA 암호화 알고리즘에서 사용한다는데 이 ..

• format_list_bulleted 별 잡다
• · 2025. 3. 20.