본문 바로가기

3. 알고리즘 공부

 (51)
[136] 서로소 집합(Disjoint set)과 유니온 파인드(Union-Find) 1. 서로소 집합(Disjoint set)그림과 같이 공통 원소가 없는 두 집합을 서로소 집합 또는 분리 집합이라고 합니다.https://ko.wikipedia.org/wiki/서로소_집합 서로소 집합 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 서로소인 두 집합 집합론에서 서로소 집합(-素集合, 영어: disjoint sets)는 공통 원소가 없는 두 집합이다.[1] 예를 들어서 1, 2, 3}과 4, 5, 6}은 서로소이며 1, 2, 3}과 3,ko.wikipedia.org이 서로소 집합을 자료구조로 나타내는 방법은 다양합니다.그 중 그래프를 이용하면 다음과 같이 나타낼 수 있습니다.(한 집합 내에 원소들이 연결만 되어 있으면 됩니다.)만약 1이 속해 있는 집합과 5가 속해 있..
[132] 매개변수 탐색(parametric search) 1. 매개변수 탐색이란? 영어로 parametric search라고도 부르는 이 탐색 알고리즘은 이진 탐색과 유사합니다. 이진 탐색을 하기 위해서는 데이터가 정렬되어 있어야 가능한데, 매개변수 탐색도 마찬가지로 데이터 안에서 한 요소를 기준으로 어느 한 쪽의 결과가 일정해야 합니다. 이런 상황에서 조건을 만족하는 최대값 혹은 조건을 만족하지 않는 최소값을 찾을 때 유용하게 사용됩니다. https://en.wikipedia.org/wiki/Parametric_search Parametric search - Wikipedia From Wikipedia, the free encyclopedia Algorithmic optimization method In the design and analysis of alg..
[129] 미니맥스 알고리즘을 사용하여 틱택토 게임 만들기 1. 틱택토 게임 3 X 3 판에 빈 칸을 골라, 플레이어가 번갈아가며 O와 X를 적습니다. 먼저 가로, 세로, 대각선 상에 3개를 연달아 놓으면 이기는 게임입니다. 오목의 간단한 버전이라고 생각해도 좋습니다. https://ko.wikipedia.org/wiki/틱택토 틱택토 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 틱택토(tic-tac-toe)는 두 명이 번갈아가며 O와 X를 3×3 판에 써서 같은 글자를 가로, 세로, 혹은 대각선 상에 놓이도록 하는 놀이이다. m,n,k-게임으로, (3,3,3)-게임이 ko.wikipedia.org 2. 미니맥스 알고리즘 미니맥스 알고리즘은 상대방과 자신의 모든 경우의 수를 탐색해서 최선의 수를 찾아내는 알고리즘입니다. 기본적인 아이디어..
[77] 최단거리탐색 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜) 1. 다익스트라 알고리즘사용 조건시작점이 있다.간선의 가중치에 음수가 없다.과정먼저, 출발 정점을 설정하고 해당 정점의 거리를 0으로 설정합니다.나머지 정점들의 거리를 무한대로 초기화 합니다.아직 방문하지 않은 정점들 중에서 하나를 선택합니다. 이때, 출발 정점에서 가장 짧은 거리를 가진 정점을 선택합니다.모든 정점에 방문할 때까지 세 번째 과정을 반복합니다.예제A가 출발 정점일 때, A에서 연결되는 간선의 정보를 우선 순위 큐(최단 거리 우선)에 넣습니다.우선 순위 큐에서 원소를 하나 꺼낼 때, 가장 짧은 거리인 B로 가는 1이 나옵니다.이제 B에서 연결되는 간선의 정보를 수정(거리 추가)하여, 그 정보를 우선 순위 큐에 넣습니다.우선 순위 큐에서 원소를 하나 꺼내면, 가장 짧은 거리인 C로 가는 4가..
[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) 길이만큼의 반복 코드 예시 ..

티스토리툴바