In University ☆ In Bucket Place ☆ Hobby & Study Room ☆

1. 여는글 어떻게 하면 질리지 않고(똑같은 화면이 반복되지 않고), 인기순을 최대한 반영해주는 페이지를 보여줄수 있을까? 컨텐츠를 관리하는 입장에서 한번씩 막히는 부분이 위와 같은 의문일 것이다. 처음에는 사이트내에 구현해 놓은 특정 수치(ex. 좋아요 횟수)가 높은 순으로 정렬해서 보여주었을 것이다. 하지만, 컨텐츠가 쌓여갈수록 인기있는 컨텐츠는 계속 상위에 노출되어 점점 더 높은 수치를 점유하게 되어 피드가 고정되는 현상이 일어날 것이다. 이 현상을 막기 위해서는 어떻게 하면될까? 답은 시간에 있다. 2. 음원 사이트에서의 인기순 생성 간단한 인기순 알고리즘으로 넘어가기 전에, 인기순 정렬을 만드는 개념에 대해서 간단히 알아보고 넘어가보자. 인기순을 계산하는 예로 음원사이트를 생각해보았다. 인기순에..

* 지능 : 끊임없이 변하는 환경에 적응하는 능력 / 자연에 적응해가는 방법, 능력 > 이점을 이용한 인공지능 연산법이 진화 연산이다. > 진화연산 : 기계 학습에 대해서 진화론적 방법론을 사용한 유전학 계산 모델 * 진화연산 - 종류 : 유전 알고리즘, 진화 전략, 유전 프로그래밍 - 사용 기법 : 선택(Selection), 변이(Mutation), 교배(Crossover) - 최적화 과정 : 진화 적합성, 적응형 위상 개념을 사용 > 진화 적합성(evolutionary fitness) : 진화 = 특정 환경에서 집단이 생존하여 교배를 하여 재생산하고, 이를 바탕으로 집단의 능력을 유지 향상 시키는 과정 > 적응형 위상(adaptive topology) : 위에서 집단의 능력을 유지또는 향상 시킨다고 ..

* 특징 - 되추적 기법과 같이 상태공간트리를 구축하여 문제를 해경한다. - 최적의 해를 구하는 문제에 적용할 수 있다.(되추적기법은 특정해를 구하는 문제에 적용) - 최적의 해를 구하기 위해서는 모든 해를 다 고려해 보아야 하므로 트리의 노드를 순회하는 방법에 구애받지 않는다. * 분기한정 알고리즘의 원리 - 각 노드를 검색할 때마다 그 노드가 유망한지의 여부를 결정하기 위해 한계치(bound)를 계산한다. - 그 한계치는 그 노드로부터 가지를 뻗어 나가서(Branch)를 얻을 수 있는 해답의 한계치를 나타낸다. - 만약 그 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어 나가서 검색을 계속 할 필요가 없으므로 그 노드는 유망하지 않다고 할 수 있다. * 최적화 문제를..

import java.util.Scanner; public class hamiltonian { private boolean W[][]; private int nodeCount; private int vindex[]; hamiltonian(int n){ nodeCount = n; W = new boolean[nodeCount][nodeCount]; vindex = new int[nodeCount]; vindex[0] = 0; Scanner sc = new Scanner(System.in); char isTrue; for ( int i = 1 ; i

import java.util.*; public class mColoring { private int n; private int m; private int W[][]; private int vcolor[]; mColoring(int count, int colornumber){ int i, j; // for loop char isTrue; Scanner sc = new Scanner(System.in); n = count; m = colornumber; W = new int[n][n]; vcolor = new int[n]; vcolor[0] = 1; for ( i = 1 ; i

* 해밀토니안 회로 - 연결된 비방향성 그래프에서 어떤 한 정점에서 출발하여 그래프사으이 각 정점을 정확히 한번씩만 경유하여 다시 출발 정점으로 돌아오는 경로 ex) * 해밀토니안 회로문제 - 연결된 비방향성 그래프에서 해밀토니안 회로를 찾아라 - 상태공간트리 > 시작 정점을 트리의 수준(level) 0에 놓는다. > 수준 1에 시작 정점이 아닌 정점들을 놓는다. > 다른 수준에도 같은 방식으로 시작 정점이 아닌 정점들을 놓는다. > 마지막 수준에는 시작 정점을 놓는다. - 되추적 방법을 적용하기 위해서 다음 사항을 고려해야한다. > 경로상의 i번째 정점은 그 경로상의 (i-1)번째 정점과 반드시 인접해야한다.(인접하지 않으면 패스) > (n-1)번째 정점은 반드시 시작 정점과 인접해야한다.(마지막(n번..

* m - 색칠하기 문제 비방향 그래프에서 서로 인접한 종점들이 같은 색을 갖지 않도록 하면서 최대 m개의 다른 색으로 칠하는 모든 방법을 찾아라. * 평면그래프(Planar graph) - 평면 상에서 연결선들이 서로 교차하지 않는 그래프 옆 그래프는 연결선이 서로 교차하지 않으므로 평면 그래프라고 할 수 있다. 위 그래프에서 두개의 연결선 (v1,v5)와 (v2,v3)를 추가하면 연결 선중 일부는 교차하게 되고, 이에 따라 평면 그래프가 될 수 없다. * 지도와 평면 그래프 - 지도에서 각 지역을 그래프의 정점으로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는 정점들 사이에 연결선을 그으면, 모든 지도는 그에 상응하는 평면 그래프로 표시할 수 있다. * m - 색칠하기 되추적..

* 상태 공간 트리(State Space Tree) - 미로 찾기에서 입구에서 출구까지 가는 경로를 찾기 위해서 선택할 수 있는 모든 경로를 트리로 만들 수 있다. 막다른 곳이나 출구가 종단 노드(leaf node)에 위치하게 된다. 이 트리가 상태공간 트리이다. - 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들 중에서 해답을 찾을 수 있다. > 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들을 모두 순회하면서 해답을 찾을 수 있다. 그러나 이방법은 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율 적이다. * 되추적 기술 - 노드의 유망성 > 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다고 판단을 한다.(non-promising) 이와 반대로 가능성이 ..

* 되추적이란? - 미로에서 출구를 찾다보면 막다른 곳에 도달 할 수 있다. 이때 마지막 분기점으로 되돌아 가서 다른 길로 갈 수 있다. 이처럼 되추적은, 어떤 집합에서 특정 기준을 만족하면서 그 집합에 속한 대상의 순서를 손택하는 문제를 푸는데 사용한다. 되추적의 기본은 상태 공간 트리로 깊이 우선 검색과 밀접한 관련이 있다. 일단 깊이 우선 검색을 먼저 알아보도록 하자. * 깊이우선 검색 - 한 그래프의 정점들을 방문하는 하나의 방법 - 슈도코드 void DFSEARCH(v){ 정점 v를 "방문함"으로 표시한다. v에 인접한 모든 정점 w에 대해서 다음을 수행한다. > w가 방문하지 않은 상태면 DFSEARCH(w)를 수행 > w가 이미 방문했던 상태면 수행을 종료한다. } // 처음 모든 정점들은 ..

* 단일 출발점 최단 경로 문제 - 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 것. * 단일 출발점 최단 경로 문제 알고리즘 - 특정 정점에서 모든 정점들로 가는 최단 경로를 찾는다. - 아이디어 : 트리를 만들어서 사용한다. * 슈도코드 V = 모든 노드의 집합 Y = {v1};// 시작하는 노드 F = null; // 트리내의 화살표들의 집합 while(최종해답을 얻을 때까지) - "V-Y"에 속한 정점들중에서 V에서 Y에 속한 정점들만을 거쳐서 최단경로가 되는 정점을 선택한다. - 그 정점을 Y에 추가한다. - V에서 F로 이어지는 최단 경로상의 연결선을 F에 추가한다. - Y = V이면 T=(V,F)가 최단 경로를 나타내는 트리이다. >> 소스코..