자료구조 & 알고리즘 & cs/알고리즘 (18) 썸네일형 리스트형 [TIL] 백트래킹 - N-Queen 문제 백트래킹(Backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위해 답이 될 수 있는 후보군의 제약 조건을 체크하다가 만족할 수 없는 경우 즉시 backtrack하고 다른 후보군으로 넘어간다. 고려할 수 있는 경우의 수를 상태공간트리(State Space Tree)를 통해 표현한다. DFS 방식으로 확인한다. promising (해당 루트가 조건에 맞는지를 검사하는 기법) pruning(가지치기 : 조건에 맞지 않으면 포기하고 다른 루트로 돌아서서 탐색의 시간을 절약하는 기법) N-Queen 문제 백트래킹의 대표적인 문제 - N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다. - 퀸은 수직, 수평, 대각선으로 이동 가능하다. ex)N이 4일 경우 다음과 같이.. [TIL] 최단 경로 알고리즘 - 벨만 포드 알고리즘 벨만 포드 알고리즘 최단 경로 알고리즘 중 하나로 가중치가 음수인 경우 적용 가능하다. 다익스트라보다 시간복잡도가 느리다. 음수 사이클 존재의 여부를 파악할 수 있다. 관련문제 11657번: 타임머신 (acmicpc.net) 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음 문제를 접근 할 때 벨만 포드 알고리즘을 몰랐기 때문에 다익스트라 알고리즘으로 접근하였다. 3개의 테스트 케이스를 분석한 뒤에 나름대로(?) 가중치가 음수인 경우를 따로 분리하.. [TIL] - 유클리드 호제 - 최소공배수와 최대공약수 유클리드 호제 (Euclidean algorithm) - 2개의 자연수 혹은 정식의 최대공약수(gcd)를 구하는 알고리즘의 하나이다. - 2개의 자연수 a,b에 대하여 r을 a%b (a>b) 라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. - 결론적으로 b%r 인 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수가 된다. - 최소공배수는 두 자연수 (a*b)/gcd(a,b) 이다. 관련 문제 코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기.. [TIL] 플로이드-워셜 - Floyd-Warshall 플로이드-워셜 알고리즘(Floyd-warshall) 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘 2차원 테이블에 최단 거리 정보를 저장한다. 다이나믹 프로그래밍 유형에 속한다. 각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인하여 a-b의 최단 거리보다 a-k-b가 짧은지 검사한다. 플로이드-워셜 알고리즘 문제 1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net import sys #플로이드 워셜 input .. [TIL] 최소 신장 트리(MST) 2 - 프림(prim) 알고리즘 프림 알고리즘(Prim's algorithm) 시작 정점을 선택한 후 정점에 인접한 간선 중 최소 가중치의 간선이 연결된 정점을 선택한다. 선택한 정점에서 위의 과정을 반복하며 최소 신장 트리를 확장해 나간다. 프림 알고리즘 구현 노드의 연결을 확인하기 위한 집합과 연결된 간선들을 관리하기 위한 간선 리스트를 사용한다. 임의의 정점을 선택 후 노드 집합에 삽입한다. 해당 정점에 연결된 간선들을 간선 리스트에 삽입한다. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출한다. -> heapq 사용 만약, 해당 간선에 연결된 정점이 위의 노드 집합에 들어 있다면 다른 간선을 찾는다. (사이클 x) 그렇지 않다면 그 간선을 선택하고 mst를 리스트에 삽입한다. 추출된 간선은 간선 리스트에서 제거한다. 간선 리.. [TIL] 최소 신장 트리(MST) 1 - 크루스칼(kruskal) 알고리즘 최소 신장 트리(MST : Minimum Spanning Tree) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 신장 트리 최소 신장 트리를 찾을 수 있는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있음. 두 알고리즘 모두 탐욕 알고리즘을 기반으로 한다. 신장 트리란? - 그래프의 모든 노드를 포함하면서 모든 노드가 서로 연결 되어 있고 트리의 속성을 만족시키는 트리 (사이클 x) 크루스칼 알고리즘(Kruskal's algorithm) 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 가중치를 기준으로 정렬하고, 가중치가 가장 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점의 최상위 정점(루트 노드)을 확인하고 서로 다르다면 연결한다. (같을 경우 사이클이 생기므로 x) Un.. [TIL] knapsack 알고리즘 (배낭 문제) knapsack problem - 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값은 정해져 있고 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 넣을 짐을 고르는 방법을 찾는 문제 냅색 알고리즘은 물건 분할 유무에 따라 분할 가능한 문제와 0-1 문제로 나뉜다. 여기서 다룰 문제는 0-1 냅색 알고리즘으로 백준 12865 문제를 풀다가 접하게 되었다. 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,0.. [TIL] LCS 알고리즘 (최장 공통 부분 수열) 최장 공통 부분 수열(LCS, Longest Common Subsequence) - 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 수열 LIS 문제와 비슷한데 LCS는 수열 2개가 주어진다. 9251번: LCS (acmicpc.net) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 위 문제를 예시로 들어 수열 ACAYKP와 CAPCAK를 가지고 표를 만들어 보았다. 이 때, 두 가지 경우를 고려해야 하는데 1. 같은 알파벳인 경우 2. 알파벳.. 이전 1 2 3 다음
