이분 탐색 : 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.

완전 탐색 (Brute Force)

완전 탐색브루트 포스로도 불리는 완전 탐색은 제목 그대로 싸그리 찾는 컨셉이다.무식하게 때려박을 수 있는 문제는 이것부터 써내려가곤 한다.1차적으로 해결이 목표일 때는 여기서 시작해서, 차차 코드를 시간복잡도가 더 우세한 영역으로 고치곤 한다.백준의 N과 M(1) - (12)을 생각하면 보다 빠르게 감을 잡을 수 있다.파일럿 코 :구현이 간단하고 직관적인 완전 탐색은 일반적으로 성능이 상대적으로 좋지 못합니다.경우의 수가 매우 많은 경우를 걸러내지 못하고 비효율적으로 작동하는 경우가 잦기 때문입니다.완전 탐색은 기본적인 접근법일 뿐이며, 효율적인 해결책을 위해 보통 더 딥한 알고리즘으로 대체하곤 합니다.덩치 큰 복잡도 유형들이 여러가지 있다.모든 가능한 조합을 탐색 : Combination Search주..

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

[PY] 1914 : 하노이 탑

https://www.acmicpc.net/problem/1914얘는 진짜 풀었던거라 금방 하고 넘어갔어야 했는데 막상 중요한 내용이 기억이 안났다.좀 민망할 정도로 극단적으로 요약하면 이런 견적이 나온다.n-1번째까지를 2번 기둥에 치운다.n번째를 1번 기둥에서 3번 기둥으로 옮긴다.n-1번째까지를 2번 기둥에서 3번으로 마저 옮겨준다.어찌 되었건 n 이전에 n-1이 옮겨져야 하는 것은 당연하다.따라서, 그럼 단계에 대한 매개변수를 하나 쓸건데, 이걸 n이라고 해야겠다.그리고 str, dest 즉 출발지와 도착지를 지정해주어야 하는데, 이 부분이 떠오를랑 말랑 해서 결과적으로 그냥 처음부터 끝까지 그렸다.5개의 플레이트가 주어지는 경우를 그린 상황이다. 할 말이 참 많지만 전체적인 전개는 이런식으로 진..

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

[PY] 9663 : N-Queen

https://www.acmicpc.net/problem/9663결론만 적으면 내 힘으로 못 풀었다. 그래서 이렇게 별도로 글을 쓴다.작동이 되는 방식을 두 가지 구현을 했다. 하나는 2차원 배열로, 하나는 1차원 배열로..더 깊이 고민하면 됐을지도 모르겠지만 (정신)체력적인 한계로 책을 결국 펼치고 말았다.분명 몇 달 전에도 비슷한 엔딩으로 모든 구조를 되새겼다고 생각하고 지나갔던 문제인데, 사람이 기억하려고 의식적으로 노력해야 하는 것 같다.N-Queen 문제는 어쨌든 배경지식으로 체스에서 Queen이 할 수 있는 것을 알아야 한다.퀸은 진짜 사방팔방 움직일 수 있다. 말 그대로 8 방향에서 움직일 수 있다. 상하좌우 북서 동북 남동 남서서로 공격하지 않게 해야 한다고 하면 사전에 놓을 수 없는 범위..

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