본문 바로가기

CS/Algorithms10

에라토스테네스의 체를 활용한 소인수분해 어떠한 수 N을 수인수분해한다고 해보자. 예를들어 60 = 2 x 2 x 3 x 5 이다. 예를들어 입력값이 아래와 같다면 (첫번째 줄에 N = 소인수분해하려는 수의 갯수, 두번째 줄에 소인수분해하려는 수 kn / N은 1 ~ 1,000,000, kn은 2 ~ 5,000,000) N k1 k2 k3... 5 5 4 45 64 54 다음과 같이 각각 한줄로 소인수분해한 값을 출력해야 한다고 해보자. 5 2 2 3 3 5 2 2 2 2 2 2 2 3 3 3 기존에 생각했던 방식은 이하와 같았다. ('더보기') 더보기 내 경우 처음 생각한 방식은, 우선 입력값 N 이하의 모든 소수를 구해두고, 소수 리스트를 순회하며 찾는 방식이었다. 예를들어 N이 60이라면 60 이하의 모든 소수를 우선 구해둔다. 그 후 작.. 2024. 2. 23.
CCW를 이용한 선분 교차 여부 판정 (2023-05-12 업데이트) 업데이트 : 2023-05-12 - 코드 잘못된 부분 수정 ( min(p1,p2) ≤ max(q1,q2) && min(q1,q2) ≤ max(p1,p2) 라고 설명은 잘 적어뒀으나, 올린 코드가 잘못됬었음.) line1.p1.compareTo(line2.p2) 2023. 5. 12.
브루트포스 알고리즘 (Brute force 알고리즘) 목차 브루트포스란? 복잡한 알고리즘을 굳이 생각하지않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 다 살펴보는 것을 의미합니다. brute force, BF, 완전탐색(exhaustive search), 완탐 정도로 불립니다. 설명을 위해 코딩테스트와 비슷한 형태의 문제로 예를들겠습니다. N개의 숫자를 입력받아 이 중 임의의 3개의 수를 골랐을 때, 세 수의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N과 S가 주어진다. (3 ≤ N ≤ 20, lSl ≤ 1,000,000) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초) 예를들어 만약 입력이 아래와 같이 주어졌다면, N=10, S=0이고 3개.. 2023. 3. 15.
벡터의 외적과 CCW (Counter ClockWise) 목차 여러 글을 보면서 제가 이해할 수 있는 수준까지 공부하고 정리한 내용입니다. 따라서 수학을 파볼려는 분 보다는, 기하 알고리즘 풀이를 위한 기본적인 이해용으로 보시는게 맞을 것 같습니다. 제가 수학을 매우 못하는 편이라 제가 이해할 수준으로 정리한 내용은 아마도 쉽게 정리된 내용일 것 같습니다. 공부 이유는 백준(솔브닥) 그래프가 안이뻐서 입니다. 틀린 내용 있을 시 댓글로 알려주세요. 벡터의 외적 outer product, cross product, vector product, 벡터곱. 기하학의 사칙연산이라 불리는 CCW를 설명하기 위한 사전 지식 입니다. 이하 bold 처리된 대문자 $\textbf{A}, \textbf{B}$는 벡터를 뜻합니다. 3차원 공간에 대해 정의된 벡터를 이용한 특정 연.. 2022. 11. 15.
누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java 목차 ※ 배열의 인덱스는 알다시피 0부터 시작한다. 예를들어 N개의 데이터가 있다면 0번 인덱스부터 N-1번 인덱스까지 존재한다. 다만 구현에 있어 누적 합을 구현할 때는 인덱스 1번부터 사용하는게 훨씬 편하다. 즉, N개의 데이터가 존재할 경우, N+1크기의 배열을 만든 후 1번 인덱스부터 N번 인덱스까지를 사용하는게 구현하기 편하다. 따라서 이하 글에서는 후자의 방식을 사용해 서술한다. ※ 코드는 자바 기준으로 작성했지만, 어려운 코드가 아니므로 다른 언어 사용자도 문제없이 볼 수 있어요. 누적 합 (prefix sum) 1. 반복문으로 구간 합을 구할때의 문제점 특정 구간의 합을 구하는 경우를 생각해보자. 예를들어 백준의 구간 합 구하기 4 문제를 보자. 최대 10만개짜리 배열에서, 최대 10만개의.. 2022. 8. 9.
분할 정복을 이용한 거듭제곱 최적화 아마 다음은 이미 알고 있을 것이다. 예를들어 거듭제곱되는 수치가 짝수일 때와 홀수일 때를 예로들면 다음과 같다. A^4 = (A^2)^2 (짝수일때) A^5 = A * A^4 = A * (A^2)^2 (홀수일때) 만약 A^8이 있다면 원래는 A*A*A*A*A*A*A*A 으로 곱셈 연산을 7번 해야 하지만, A^8을 ((A^2)^2)^2 으로 변경하면 A*A=A', A'^2=A'' 이라 할 시 최종적으로 A'을 구하는데에 A*A로 곱셉 한번, A''=A'*A'을 구하는데도 마찬가지로 곱셈 한번, 최종적으로 A''*A''을 구하는데 곱셈 한 번이 들어간다. 즉 7번의 연산이 3번의 연산으로 줄어든다! 즉, 거듭제곱을 위와 같이 계산한다면 원래 N번의 연산이 O(logN)으로 줄어든다. 여기서 분할정복을 활.. 2022. 4. 5.
에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12.
백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3.
BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS (2022-08-27 업데이트) 2022-07-21 업데이트 : 글 맨 아래에 '풀어보기'로 풀어볼만한 문제 링크 추가 2022-08-27 업데이트 : '풀어보기' 좀 더 추가, 목차 추가 목차 BFS (Breadth-first Search) 명확히 검증하면서 쓴게 아니라서 틀린 부분 있으면 알려주세요! - BFS와 DFS 대충 곰처럼 생긴 섬이 바다에 떠 있다. 편의상 이 섬을 20등분해서 격자 형태로 구역을 나누었다. 이제 우측상단의 귀(곰 입장에서 왼쪽귀)부터 출발해서 섬 전체를 둘러보려 한다. 둘러보는 방법은 여러가지가 있을 수 있다. 빨간 숫자는 둘러본 순서를 뜻한다. (0 부터 19까지) A처럼 자신과 가까운 곳부터 순서대로 살펴볼수도 있다. 격자형태로 나누었으므로 Manhattan Distance (Taxicab Geome.. 2021. 9. 24.
알고리즘 시간복잡도에 대해 목차 Complexity Up & Down 게임을 해봅시다! 1~100까지의 숫자 중 하나를 생각해보겠습니다. 전 96을 생각할껍니다. 이걸 누군가에게 맞춰보라고 하고, up & down으로 대답하겠습니다. "1" ⇒ up "2" ⇒ up "3" ⇒ up .. (92번을 더 한 후) "96" ⇒ 맞았..어.. 이렇게 물어볼사람은 없을껍니다! 다들 자연스럽게 아래와 같이 물어볼꺼에요. "50" ⇒ up "75" ⇒ up "87" ⇒ up "93" ⇒ up "96" ⇒ 맞았어! 이걸 다르게 표현해보겠습니다. 우선 1부터 차례대로 물어본 전자의 경우를 보겠습니다. 1~100까지의 100개를 N개라 표현하겠습니다. 이 경우 만약 생각한 숫자가 100이라면(= 생각한 숫자가 N이라면) 최악의 경우로, 100번 물.. 2021. 9. 22.

티스토리툴바