분류 전체보기692 [알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘 Sweeping Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다. 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다. 이처럼 알고리즘의 구조 자체는 간단합니다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 대표적인 문제로 백준의 선 긋기 문제가 있습니다. 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [Java] 자바 함수형 프로그래밍 함수형 프로그래밍이란 무엇일까? 스스로의 궁금증에 답하기 위해 공부하며 기록해 본다. 함수형 프록래밍이 엄청 특별하고 그런것은 아니다. 우리가 일반적으로 익숙한 절차지향적 프로그래밍과 같은 프로그래밍 패러다임중 하나이다. 보통 객체지향 패러다임 에서는 객체 스스로가 상태를 가지고 있고, 객체간에 메시지를 전달하면서 협력하게 된다. 하지만 함수형 패러다임 에서는 작은 단위의 함수들이 모여 처리된다. 함수들은 외부와의 관계는 없고 단지 함수 자신만으로 존재한다. 객체지향 프로그래밍의 경우, 클래스 디자인과 객체들의 관계를 중심으로 코드 작성이 이루어진다. 따라서 상태, 멤버변수, 메서드 등이 긴밀한 관계를 가지고 있다. 특히 멤버변수가 어떤 상태를 가지고있는가에 따라 결과가 달라진다. 함수형 프로그래밍의 경.. BackEnd/Java 2022. 1. 21. [서평] 객체지향의 사실과 오해 저의 돈으로 직접 사서 직접 완독 해본 후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할 것이며, 단점은 단점대로 언급할 것입니다. 객체지향의 사실과 오해 저자 : 조영호 출판 : 위키북스 발매 : 2015.06.17 2021/01/17 ~ 2021/02/09 1) 책의 표지 2) 단원별 요약 3) 읽은 소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 객체지향의 사실과 오해를 읽기 전에 필요한 수준/ 지식은? => 이 책은 코드가 없는 책이다. 물론 7장에서 JAVA코드가 아주 일부분(다 합치면 2장 정도?) 나오지만, JAVA를 몰라도 다른 객체지향 언어를 안다면 무리가 없는 내용이다. 이런 면에서 범용성이 좋은 책이 분명하다. 하지만 객체지향 .. Life/Book Record 2022. 1. 21. [알고리즘] Counting inversions Counting inversions " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 예를들어 배열A에 1, 2, 3, ... n 의 수가 무작위 순서로 들어있다고 해보자. 이 수들에서 2개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는지를 구해보자. 예를 들어 A {2, 3, 6, 4, 1, 7}이 있을때, 크기가 역전된 쌍은 (2, 1), (3, 1), (6, 4), (6, 1), (4, 1) 이 있다. 따라서 Inversion 된 쌍의 수는 5개 이다. 이런 Inversion된 쌍의 수를 어떻게 구해야 할까? 직관적으로 떠오르는 직접다 for문 돌면서 확인하는 방식은 O(n^2)이 걸릴것이 눈에 훤하다... 이럴때 Merge.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [백준][C++] 14852번: 타일 채우기 3 <177> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 맨 처음 생각했던 방식은 DP[N]을 만들기 위해 끝부분에 2*1 채우는 방식과, 2*2 즉, 다음 그림과 같은 방식이 끝이라고 생각했다. 따라서 점화식이 DP[N] = DP[N-1]*2 + DP[N-2]*3 이라 생각했다. 하지만 예외가 있었다. 길이가 3, 4, 5 ... 등 다음과 같은 추가적인 case가 존재했다. 각각 길이가 3, 4인 case 이다. 즉 DP[N] = DP[N-1]*.. Algorithm/백준 2022. 1. 21. [알고리즘] lower_bound, upper_bound : C++ ⭐ 조건 : 탐색을 진행할 array, vector는 오름차순으로 정렬되어 있어야 한다. lower_bound " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 lower_bound(3)을 진행하고 싶다. 배열 arr의 첫 시작지점 부터 탐색하면서 처음으로 3이 나오는 배열의 위치(Iterator)를 반환한다. 즉, 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 용도이다. 위치를 반환한다고 한 이유는 lower_bound의 반환형은 Iterator 이기 때문이다. 실제로 몇 번째 인덱스인지 알고 싶다면, 아래 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다. #include #incl.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [서평] 명품 C++ 저의 돈으로 직접사서 직접 완독해본후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할것이며, 단점은 단점대로 언급할 것 입니다. 명품 C++ Programming 저자 : 황기태 출판 : 생능출판사 발매 : 2018.03.05. 2020/12/28 ~ 2021/02/01 (홍정모 교수님의 따배씨쁠쁠과 병행하여 공부한 교제) 1) 책의 표지 2) 단원별 구성 3) 읽은소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 명품C++을 공부하기 전에 필요한 수준/ 지식은? => 최소한 C언어 문법은 기초정도는 알고있으셔야 합니다. 저자또한 C언어의 기초를 아는 독자를 대상으로 하는 책임을 도입부에서 명시해 주었다. 하지만 다행이도 기본프로그래밍 지식에 .. Life/Book Record 2022. 1. 21. [알고리즘] 에라토스테네스의 체 : 소수 판별법 에라토스테네스의 체 (Sieve of Eratosthenes) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 방식은 지정됨 범위네에서 대량의 소수를 한번에 구할때 유용하다. 예를 들어 121 이하의 소수를 모두 구해야 한다고 해보자. 어떻게 해결해야 할까? 결론부터 말하면 121의 제곱근, 즉 11 이하의 소수 n에 대하여 n의 배수들은 전부 제외시키면 된다. n의 배수라는 말 자체가 소수가 아니다. 아직 이해가 잘 안갈 수 있다. 다시 설명해 보자. 121의 제곱근인 11이하의 수 들을 생각해보자. 일단 2는 소수니 제거하지 않는다. 2를 제외한 모든 2의 배수 4, 6, 8, 10, ..., 120 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다. .. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] 최대공약수(GCD), 최소공배수(LCM), 유클리드 호제법 최대공약수 GCD(Greatest Common Divisor) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최대공약수는 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값을 의미한다. 예를들어 24와 18 있다고 해보자. 최대공약수는 6이 된다. 최소공배수 LCM(Least Common Multiple) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최소공배수는 두 자연수들의 배수들 중에서 공통된 가장 작은수를 말한다. 참고로 최소공배수는 최대공약수를 통하여 바로구할 수 있다. 최소공배수 = 두 자연수의 곱 / 최대공약수 가 적용된다. 예를 들어 24와 18의 최소공배수는 72 이다. 유클리드 호제법 (Euclidean Algorit.. 카테고리 없음 2022. 1. 20. [알고리즘] 트리의 지름 : Diameter of Tree 트리의 지름 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함수로 나타낼 수 있으며, 최장거리(지름)는 이러한 d(u, v) 값들중 최대인 Max d(u, v)라고 할 수 있다. 트리의 지름을 찾는 알고리즘 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 BFS(node) 를 통하여 node로 부터 가장 멀리있는 node를 구한다고 해보자. 이 방식은 greedy 방식에 해당된다. 1. 임의의 시작 정점 s로부터 가장 멀리있는 정점인 u를 BFS(s)로 구한다. (DFS도 가능) 2. 이렇게.. Algorithm/PS 알고리즘 정리 2022. 1. 20. WoowaCon 2021 [우아콘 후기] 2021 우 아이콘을 선택적으로 들은 후, 기록 겸 가볍게 남기는 글입니다. 0. 짧은 후기 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 2020 우아콘 의 경우 영한 님의 마이크로 서비스 여행기만 봤었는데, 이번에는 좀 더 다양한 분들의 컨퍼런스를 보았다. 2021 우아콘은 총 3일간 진행되었으며, 대략적으로 영상당 25~30분 정도 되는 길이었다. 우선적으로 흥미 있는 개발 관련 내용부터 살펴봤으며, 이후 개발 외(예를 들면 베트남 진출기, 초기 배민 스토리, 이력서 팁) 내용을 보았다. 10편을 주면 1만원을 준다길래 10편은 채워서 들었다! (근데 아직도 쿠폰 같은 거 안 들어 왔다... 이거 어디로 사라진거지??...) 일반인들이 생각하기에 단순한 배달 대행 .. Life/컨퍼런스 2022. 1. 20. [알고리즘] Bipartite Graph : 이분 그래프 이분 그레프 (Bipartite Graph) 란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 학교에서 공부할때 필기한 내용을 먼저 보인후, 이를 내가 설명하여 보겠다. 이분 그레프란 정점의 집합을 2개의 독립적인 집합으로 나눌 수 있으며, 나눠진 집합에서는 서로다른 집합 사이에만 간선이 존재하는 그레프를 의미한다. 즉 같은 집합 내부의 정점간에는 간선이 있으면 안된다. 이를 그림으로 표현하면 다음과 같음 그레프를 의미한다. 집합이 오른쪽(V)과 왼쪽(U) 2개의 집합으로 나뉘어 졌다. 간선들의 양끝 정점(u와 v) 또한 서로다른 집합에 포함되어있다. 정점 u는 집합 U에, 정점 v는 집합 V에 포함되어야 하는 것! 추가적으로 그림에는 없지만, 한쪽 집합에 그냥 .. Algorithm/PS 알고리즘 정리 2022. 1. 20. 이전 1 ··· 46 47 48 49 50 51 52 ··· 58 다음
