CS24 에라토스테네스의 체를 활용한 소인수분해 어떠한 수 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. [디자인 패턴] 프록시 패턴 (Proxy Pattern) 스터디 메인 페이지 목차 - ☆ 표시가 붙은 부분은 스터디 중 나온 얘기 혹은 제 개인적인 생각이나 제가 이해한 방식을 적어놓은 것으로, 책에 나오지 않는 내용입니다. 따라서 책에서 말하고자 하는 바와 다를 수 있습니다. 또한 책에는 따로 Step으로 나오지 않습니다. 설명의 편의를 위해 임의로 나눈 것 입니다. - 모든 이미지의 출처는 헤드퍼스트 디자인패턴 개정판(한빛미디어) 입니다. 프록시 패턴 (Proxy Pattern) 코드 링크 : github GitHub - nahwasa/study-design-patterns: 헤드퍼스트 디자인패턴 스터디 진행하면서 각 패턴별 문제점이 있 헤드퍼스트 디자인패턴 스터디 진행하면서 각 패턴별 문제점이 있는 코드부터 개선되는 코드까지 짜보기 위한 레포 - GitH.. 2023. 6. 18. [디자인 패턴] 전략 패턴 (Strategy Pattern) 스터디 메인 페이지 목차 - ☆ 표시가 붙은 부분은 스터디 중 나온 얘기 혹은 제 개인적인 생각이나 제가 이해한 방식을 적어놓은 것으로, 책에 나오지 않는 내용입니다. 따라서 책에서 말하고자 하는 바와 다를 수 있습니다. 또한 책에는 따로 Step으로 나오지 않습니다. 설명의 편의를 위해 임의로 나눈 것 입니다. - 모든 이미지의 출처는 헤드퍼스트 디자인패턴 개정판(한빛미디어) 입니다. 전략 패턴 (Strategy Pattern) 코드 링크 : github GitHub - nahwasa/study-design-patterns: 헤드퍼스트 디자인패턴 스터디 진행하면서 각 패턴별 문제점이 있 헤드퍼스트 디자인패턴 스터디 진행하면서 각 패턴별 문제점이 있는 코드부터 개선되는 코드까지 짜보기 위한 레포 - Gi.. 2023. 6. 17. 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 처리된 대문자 A,B는 벡터를 뜻합니다. 3차원 공간에 대해 정의된 벡터를 이용한 특정 연.. 2022. 11. 15. 자바 싱글톤 패턴의 변화 (다양한 싱글톤 패턴 구현 방법) 목차 싱글톤 패턴은 어떠한 클래스에 대한 객체(=인스턴스)를 해당 프로그램에서 단 하나만 가지도록 강제하는 구현 패턴 입니다. 단 하나만 있지 않으면 문제가 생기거나, 하나만 있어도 문제가 없을 때 사용하면 됩니다. 자바로 싱글톤 패턴을 구현하는 방법들을 점차 이전의 단점을 해결하면서 변화하는 코드들로 짧게 얘기해보려 합니다. 주관적 견해도 들어가 있으므로 정답은 아닙니다. 1. 가장 기초가 되는 구현 방법 class ConnectionManager { private final static ConnectionManager instance = new ConnectionManager(); private ConnectionManager() {} public static ConnectionManager getI.. 2022. 11. 15. 펜윅 트리(Fenwick tree, BIT) - 기본, 2D, lazy propagation(range update - point query, range update - range query) 목차 ※ References에 적어둔 여러 글을 보며 공부한걸 나중에 까먹지 않기 위해 제가 이해한 내용을 제가 이해한 방식으로 필기 해두는식으로 적은 글 입니다. 그러니 개념을 더 제대로 살펴보시려면 References의 잘써둔 글들을 참고해주세요. 그나마 이 글의 장점이라면 제가 수학에 매우 약하기 떄문에 제가 이해한 방식으로 적어두면 다른 분들은 훨씬 금방 이해하심. 틀린거 있으면 알려주세요! ※ 용어 : 이하 글에서 구간합은 'A부터 B까지의 합', 누적합은 '1부터 N까지의 합', 누적합 알고리즘은 prefix sum 알고리즘을 뜻합니다. ※ 기본적으로 중간 중간에 있는 코드 예시는 c++, java 모두 통용되는 코드로 작성했습니다. 어차피 구현이 간단한 부분들이므로 어떤 언어를 사용하던지 이.. 2022. 8. 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. [자료구조] C언어 - 이진 탐색 트리(BST , binary search tree) 구현 - 객체지향 - C언어로 구현한 이진 탐색 트리(BST, binary search tree) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 재귀를 사용한 버전과, 그렇지 않은 버전 두 가지 종류가 함께 들어있다.(각각 따로 빼내도 된다.) 사용예시처럼 구분해서 사용할 수 있다. 덕분에 코드가 좀 길다. binary_search_tree.c만 600줄정도.. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) - 이하 코드에서 사용된 node.h, list.h, list.c, stack.h, stack.c, queue.h, queue.c는 '[자료구조] C언.. 2022. 4. 9. 이전 1 2 3 다음