Algorithm

Gale-Shapley 알고리즘 (게일-섀플리 알고리즘, GSA)N명의 남성 & N명의 여성의 선호도를 기반으로 N개의 쌍으로 엮어줌로직에서 선택권이 여성에게 있어서 여성에게 유리한 알고리즘으로 보일 수 있지만,실제로 수학적인 증명과정을 거치면 고백을 하는 남성에게 더

1. 다익스트라 알고리즘 그래프 상에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나 이외에도 최단경로 구하는 알고리즘 : 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등 도착 정점 뿐만 아니라 다른 모든 정점까지 최단 경로로 방문하며 각

1. 추천 시스템 & 추천 알고리즘이란? 📌 추천 시스템 : 아이템 바탕으로 어떤 추천을 할지, 플랫폼 상에서 유저에게 추천 결과를 어떻게 보여줄지 전체 시스템을 총괄하는 것 📌 추천 알고리즘 : 아이템 pool(전체) -> 특정 후보군 추출 -> 후보군을 바탕으

: 가중치 그래프의 임의의 출발점에서 다른 도착점까지의 최단 경로를 찾는 문제모든 정점을 경로가 확정된 점들 & 미확정된 점들로 구분알고리즘의 1단계 수행 시 경로가 미확정된 점 1개 선택하여 그 점의 경로를 확정업로드중..선택된 점을 m이라 하자프림 MST 알고리즘에

그리디 알고리즘에 초점을 두어 파일 압축 알고리즘 => 허프만 코딩문자별로 다른 크기의 코드를 부여해야함!빈도수가 높을수록 짧은 코드 부여코드가 이진수 => 이진 트리를 연관 지어보자왼쪽 자식으로 내려갈 때 : 0오른쪽 자식으로 내려갈 때 : 1코드(010100...)

동적 계획 알고리즘작은 문제 = "부분 문제": 원래 문제의 일부분임숫자가 일렬로 나열됐을 때 가장 긴 증가 순서 찾기가장 긴 증가 순서 = 그래프에서 가장 긴 경로각 점에서 오른쪽에 위치한 점에 대해 자신보다 큰 숫자를 가진 점을 간선으로 연결그래프의 간선 방향 :

다익스트라 : 음수 가중치 가진 그래프에서 최단 경로 못 찾음확정된 점 & 미확정된 점으로 구분 짓지 않고 간선완화해야 함음수 사이클 : 사이클 상의 간선의 가중치의 합이 음수인 사이클경로상에서 음수 사이클 반복할수록 거리 더 짧아짐=> 최단 경로 찾는 입력 그래프엔

각 동아리가 미팅에 필요한 시간만 제시1개의 미팅룸에 특정 시간 동안 가능한 한 미팅룸이 비어 있지 않도록 동아리들을 배정선택된 동아리 수 or 동아리의 미팅 순서는 중요 X물건을 1개씩 늘려가며 부분 문제의 크기를 증가시킴트럭의 용량을 1부터 K까지 1씩 증가시키어

여왕 말 - 8방향(상하좌우 및 대각선상)으로 이동 가능: Q가 같은 열 & 행 & 대각선상에 서로 놓이지 않도록 nxn 장기판에 n개의 Q를 배치하는 문제 (단 n>3)Q를 (0,0)부터 놓기 시작하여 다음 말을 서로 위협하지 않도록 배치배치 불가능이면, 직전 말의

앞에서 동적 계획 알고리즘으로 해결했음but 수행시간이 O(nK)인데,K = 2^n 지수형태 처럼 매우 크면 수행시간 엄청 오래걸림이제 백트래킹 알고리즘을 이용하자가지치기로 해가 될 수 없는 노드들을 탐색 안 함\-> 모든 조합을 검사하는 것보다 훨씬 빠름주어진 숫자들

앞에 5.5장에서 배낭 문제를 동적 계획 알고리즘으로 해결했음=> 배낭 DP알고리즘의 수행 시간 : O(nK)if K = 2^n이라면 DP 알고리즘은 모든 조합을 하나씩 차례로 검사해보는 방법보다도 성능 떨어짐배낭 문제 : n개의 물건의 무게 & 가치 주어짐배낭의 용량

지수 시간의 시간 복잡도를 가진 알고리즘으로 해결되는 문제 집합문제 A가 NP-완전 문제가 되려면A가 NP-문제모든 NP-문제가 다항식 시간에 문제 A로 변환돼야 함NP- 문제는 NP-알고리즘을 가진 문제들의 집합NP-알고리즘 : '추측된' 해를 다항식 시간에 확인하는

n개의 물건, 통의 용량이 C주어진 모든 물건을 가장 적은 수의 통에 채우는 문제(물건의 크기는 C보다 작음)응용 : 용량 C인 1개의 통만 주어지고, 물건들을 통에 남는 부분 없이 채우는 문제 = 합이 K되는 숫자 문제용량 C인 1개의 통만 주어지고, 물건들을 통에

6. 되돌아가며 풀어보기 문제의 해를 탐색하는 방식 📌 백트래킹(Backtracking) 알고리즘 : 해를 찾는 과정에서 해를 더 이상 얻지 못하면 바로 직전 상태로 되돌아가서 다른 것을 시도하며 해를 찾음 최적화 문제 & 결정 문제 해결 결정 문제 : 문제에 대한