전체 글

[알고리즘] 3. 최근접 점의 쌍 찾기 알고리즘 (3)

▶ 최근점 점의 쌍을 찾는 문제? 최근접 점의 쌍(Closest Pair)을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제입니다. 바로 그 문제를 해결하기 위한 방법은 효율적인 분할 정복을 이용하는 것입니다. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 쌍을 찾고, 2개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾습니다. 여기서 주의할 점! 취합할 때 중간 영역을 고려해야합니다. 이게 무슨 말이냐면, 분할된 왼쪽 점 중에 하나, 오른쪽 점 중에 하나가 최근접점 쌍이 될 수 있습니다. 그래서 중간 영역도 왼쪽 부분과 오른쪽 부분의 최단 거리인 10과 15중에 더 짧은 거리 10이내에 있는 각각 왼쪽과 오른쪽 점들만 거리 ..

[알고리즘] 3. 선택 문제 알고리즘 (2)

▶ 선택문제(Selection)란? ※ 선택 정렬(Selection Sort)과는 다른 알고리즘입니다. 선택(Selection) 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제입니다. 이 문제를 해결하기 위한 단순한 방법은 다음과 같습니다. 1) 최소 숫자를 k번 찾는다. → 숫자 n개가 들어있는 배열 중에서 최소 숫자를 찾고, 찾을 때마다 입력에서 그 숫자를 제거합니다. 시간복잡도는 O(kn), k번째 숫자를 찾을 때까지 반복하는 과정마다 항상 n, n-1, n-2....(최소 숫자는 제거되므로) 개의 숫자들을 탐색하기 때문입니다. 2) 숫자들을 정렬한 후, k번째 숫자를 찾는다. → 시간복잡도는 O(nlogn), 즉 정렬하는 과정에서 걸리는 시간에 따라 다를 것입니다. (k번째 숫자를 찾..

[알고리즘] 3. 분할 정복 알고리즘 (1)

1. 분할 정복 알고리즘 분할정복알고리즘이란? 분할과 정복이라는 이름에 걸맞게, 해결하려고 하는 문제를 작은 문제로 분할하여 큰 문제를 정복하는 알고리즘이다. 분할정복의 3단계 1. Divide -> 기존 문제를 작은 부분 문제들로 나눈다. 2. Conquer -> 각 부분 문제를 해결(정복) 3. Combine -> 부분문제들의 솔루션을 통해 기존 문제를 해결 이 때 2. Conquer 과정은 다시 Divide, Conquer, Combine의 과정을 거쳐 풀기도 한다. -> 재귀적 Base Case vs Recursive Case Divide 단계에서 기존 문제를 작은 부분으로 나눌 때 무조건 나누는 것이 아니라, Base Case인지, Recursive Case 인지를 판단해야 한다. - Base ..

기하 알고리즘

기하학 좌표를 사용하여 점, 선, 다각형, 다면체 등의 기본 요소를 어떻게 표현할 것인가 결정 기하학의 문제 - 간단한 문제: 선분 교차, 직각 삼각형, 내접 다각형 - 복잡한 문제: 순환 외판원, CAD, 최소 신장 나무 1. 선분 교차 - 두 선분이 주어졌을 때, 이 둘이 서로 교차하는지 아닌지 검사하는 알고리즘 - 두 선분이 교차한다는 것은 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다. 두 선분의 교차 여부를 검사하는 방법 - 각 선분의 무한 연장선을 긋고 두 연장선의 일차방정식을 구한 후 교점을 계싼한다. 2. 단순 폐쇄경로 찾기 임의의 기준점으로부터 다른 각각의 점까지의 각도를 구한 후, 올림차순으로 정렬한 다음 기준점부터 정렬한 순서대로 이으면 그것이 단순 폐쇄 경로가 된다. 기준점..

동적 계획 알고리즘

동적 계획법이란? - 복잡한 문제를 푸는 알고리즘의 한 종류 - 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결한 뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다. - 이 때 계산한 작은 문제의 값을 저장해 두는 메모리를 캐시(cache)라고 부른다. 동적 계획법의 조건 Overlapping Subproblem : 겹치는 부분(작은) 문제 (중복되는 부분문제) 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있음 재귀 알고리즘 피보나치 수열이 대표적인 예시 Optimal Substructure : 최적 부분구조 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 설계될 수 있음 문제의 정답을 작은 문제의 정답에서부터 구할 수 있다. 그리디 알고리즘의 유용성을 판별하는데 사용되기도 한다...

[알고리즘/개념정리] 2. 알고리즘이란?

2-1 알고리즘이란 알고리즘이란? 알고리즘의 일반적 특성 정확성 알고리즘은 입력값에 대해 항상 올바른 로직을 거쳐 올바른 해를 주어야 한다. 수행성 컴퓨터 내에서 모든 단계가 수행 가능해야 한다. 코드로 바꿀 수 없다면 컴퓨터에서 수행 가능한 알고리즘이 아니다. 유한성 너무 오래 걸린다면 알고리즘으로써의 가치가 없다. 일정 시간 내에 종료되어야 한다. 효율성 커지면 커질수록 더 오래 걸린다면 효율적이라고 볼 수 없다. 입력값이 크면 클수록 점점 적은 시간이 걸리는 것이 효율적이다. 시간복잡도 2-2 최초의 알고리즘 유클리드의 최대공약수 알고리즘 곱셈을 통해 푸는 방법 12 → 12 x 1 , 6 x 2, 4 x 3 30 → 30 x 1, 15 x 2, 10 x 3, 6 x 5 공약수 중 가장 큰 것이 최..

[서버] CI/CD 그리고 Jenkins (젠킨스)

앱 자체를 만들고 최적화 시키는 것에만 관심을 가지고 있었습니다. 그런데 제가 서버를 멘토링을 하고 있는 멘티가 CI/CD와 젠킨스에 대해 관심을 갖더라구요. 저는 아는 바가 없어서 해줄 얘기를 찾기 위해 구글링을 하다보니 젠킨스를 사용해보고 싶다는 생각이 격렬히 들었습니다. 그동안 로컬에서 API를 빌드하고 테스트하고 테스트가 완료된 API를 서버에 올려주는 과정이 매우 귀찮다고는 생각하고 있었는데 역시 이런 귀찮음은 역사가 오래된 귀찮음이었나 봅니다. 사설은 줄이고 CI/CD와 젠킨스에 대해 알아봅시다! CI/CD CI(Continuous Integration) : 여러 개발자들의 코드를 계속해서 통합하는 것. CD(Coutinuous Delivery) : 개발자들이 코드를 계속 작성하면, 사용자 및..

[TI/SPRING] IOC, DI 정의/ 장점

[Tech Interview] IoC, DI는 무엇이고 어떠한 장점이 있을까요? IOC 란 무엇인가? IOC 는 SPRING 용어가 아닙니다.SPRING 이전에도 존재했던 용어죠. IOC는 Inversion of Control 의 약자입니다. 단어를 좀 뜯어볼까요? Inversion 역전 Control 제어 즉, IOC는 제어의 역전입니다. 그럼 뭘 제어하고 뭘 역전했다는 것일까요? 이전 포스팅에서 SPRING 을 EJB 와 비교해서 설명할 때 제어에 대해서는 많이 이야기를 했습니다. 원래는 제어는 개발자가 구현해야 했습니다. 하지만 EJB와 SPRING 모두 편리한 개발, 즉 개발자가 복잡하고 실수하기 쉬운 로우레벨의 기술에 많이 신경쓰지 않고도, 애플리케이션의 핵심인 사용자의 요구사항, 즉 비지니스 ..