3. 알고리즘 공부 (47) 썸네일형 리스트형 [60] 유클리드 거리 vs 맨해튼 거리 1. 두 물체 사이의 거리는 어떻게 나타낼까요? 최단 거리를 찾는 문제를 풀다보면 보다 근본적인 궁금증이 생깁니다. 두 물체 사이의 거리는 무엇일까요? 아마 쉽게 두 물체를 연결한 직선의 길이를 떠올렸을 것입니다. 그러나 실제 현실에서는 조금 달라집니다. 서울에서 부산까지 차를 타고 가는데 필요한 거리는 서울과 부산을 직선으로 연결한 길이보다 길어질 것 입니다. 이렇게 거리를 나타낼 수 있는 서로 다른 두 가지 방법을 알아봅시다. 2. 유클리드 거리(Euclidean distance) 우리가 두 점 사이의 거리를 구하라고 했을 때 쉽게 떠올리는 방식입니다. 쉽게 생각해봅시다. 두 물체 사이에 가로 막는 것이 없고 두 물체 사이의 거리를 구하라고 하면 어떻게 하는게 제일 편할까요? 아마 줄자를 가지고 두 .. [58] Knuth's Optimization(커누스 최적화) Dynamic Programming을 공부하다보니 문제 해결을 최적화하는 여러 가지 방법이 있다는 것을 알게 되었습니다. 커누스 최적화는 이런 DP 문제를 최적화하는 방법 중에 하나입니다. 특정 조건이 충족되면 사용할 수 있으며, \(O(n^{3})\)의 시간 복잡도를 \(O(n^{2})\)으로 최적화할 수 있습니다. 저는 아직 이 방법에 대해서 충분히 이해하진 못하였으나, 의외로 간단하기 때문에 잘 기억해두었다가 필요할 때에 다시 사용해보면 좋을 것 같습니다. 혹시 오류가 있다면 댓글로 남겨주시면 참고하여 수정하도록 하겠습니다. 커누스 최적화를 사용하기 위한 조건은 세 가지이며 다음과 같습니다. 첫째, 점화식의 형태가 다음과 같아야 합니다. \(dp(i,j)=\displaystyle\min_{i\leq k [57] 모듈러? 모듈로? 나머지와 관련된 이야기 1. 계산 결과를 1,000,000,007로 나눈 나머지를 출력하세요. 알고리즘 문제를 풀다보면 가끔 이런 문장을 만나곤 합니다. 주로 큰 수를 결과로 출력하기 위한 문제들에서 보입니다. 그 이유는 컴퓨터가 표현할 수 있는 숫자형에는 한계가 있기 때문입니다. 참고로 32비트 정수형의 최대값은 2,147,483,647입니다. 따라서 큰 수를 표현해야하는 알고리즘 문제에서는 특정 수의 나머지를 출력하라는 조건이 달려있곤 합니다. 2. 계산을 다하고 나누면 한 번만 나누면 될까? 정답은 '아니오.'입니다. 계산을 하다보면 컴퓨터가 인식할 수 있는 범위를 넘어선 수가 만들어지기도 합니다. 그게 아니더라도 큰 수를 너무 많이 계산하다보면 시간이 너무 오래 걸리거나, 메모리를 초과할 수도 있습니다. 따라서 계산 중.. [28] [프로그래머스] 완주하지 못한 선수 - 나만의 풀이(Javascript) * 주의! 비전공자의 내 맘대로 식 풀이입니다. 잘못된 점이나 조언이 있다면 댓글로 가르쳐주시면 잘 배우겠습니다! ^^ 첫 번째 방법: 정렬하여 풀기 접근 방법 가. [참가자] 명단과 [완주자] 명단을 오름차순으로 정렬한다. 나. 순서대로 한 명씩 비교하면서 달라졌을 때, 그 [참가자]의 이름을 출력한다. 내 생각과 느낌 가. 생각하기 쉬우면서도 심플한 방법인 것 같다. 나. 다양한 정렬 방법을 배울 수 있는 기회였다. 다. 비효율적인 정렬 방법은 시간 초과로 통과하지 못한다. 라. Array.prototype.sort() 메서드를 사용하면 쉽다.(각종 메서드를 잘 알고 활용하는 것이 중요!) 마. 배열(길이: n)의 정렬 + 배열(길이: n-1)의 정렬 + 배열(길이: n) 길이만큼의 반복 코드 예시 .. [25] 삽입 정렬(Insertion Sort) * 주의! 비전공자가 독학한 내용입니다. 틀린 내용이 있을 수 있으면 댓글로 남겨주세요! 1. 2항부터 시작하여 바로 앞의 항과 비교하여 작은 게 앞으로 오게 한다. 2. 다음 항으로 이동하여 1의 과정을 반복한다. 3. 다음 항이 앞으로 왔는데도 그 앞의 항이 더 크면 한 번 더 앞으로 오게 한다. 4. 반복한다. 장점: 쉽다. 버블 정렬, 선택 정렬보다 빠르다. 단점: 역시 느리다. 시간복잡도는 버블 정렬, 선택 정렬과 마찬가지로 O(n^2)이다. https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC 삽입 정렬 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 프로그래머스 > 코딩테스트 > 해시 > 완주하지 못한 선수.. [24] 선택 정렬(Selection Sort) * 주의! 독학한 내용이므로 틀린 내용은 댓글로 남겨주세요! 배열을 한 번 훑을 때 최소값을 찾아서 맨 앞으로 보낸다. 다시 훑을 때는 두 번째 요소부터 훑으며 최소값을 두 번째 요소 자리로 보낸다. 이걸 (배열의 길이 - 1) 만큼 반복한다. 장점: 버블 정렬보다 항상 빠르다!(그리고 쉽다!) 단점: 역시 느리다!(시간복잡도가 버블 정렬과 마찬가지로 O(n^2)이다!) 이중선택정렬도 있다. 한 번 훑을 때 최소값과 최대값을 찾아서 맨 앞과 맨 뒤로 보낸다. 다시 훑을 때는 두 번째 요소부터, 끝에서 두 번째 요소까지 훑으며 최소값과 최대값을 움직인다. 이걸 (배열의 길이 / 2) 만큼 반복한다. https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%E.. [23] 버블 정렬(Bubble Sort) * 주의! 독학한 내용으로 틀린 내용이 있을 수 있으며, 댓글로 알려주세요! 앞에서 두 개를 비교해 뒤에 있는 것이 작을 경우 바꿔준다. 다음 칸으로 가서 두 개를 비교해 뒤에 있는 것이 작을 경우 바꿔준다. 끝까지 실행한 다음 다시 처음부터 반복한다. 바뀌는 것이 없을 때까지(최악의 경우 배열의 길이 - 1 번) 반복한다. 장점: 쉽다! 단점: 느리다!(시간복잡도가 O(n^2)이다.) https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC 거품 정렬 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 프로그래머스 > 코딩테스트 > 해시 > 완주하지 못한 선수 Bubble Sort로 풀어보기! function bubbleSo.. 이전 1 ··· 3 4 5 6 다음
