Algorithm

신장 트리

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도하다. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까? 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치한다. 크루스칼 알고리즘 대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류된다. 크루스칼 알고리즘..

기타 그래프 이론

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 서로소 집합 알고리즘 서로소 집합 알고리즘이란 공통 원소가 없는 두 집합을 의미한다. 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다. 합집합 - 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기 - 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기 자료구조라고 불리기도 한다. 서로소 집합 알고리즘 동작과정 합집합 연산을 확인하여 서로 연결된 두 노드 A,B를 확인한다. A와 B의 루트 노드 A,B를 각각 찾는다. A를 B의 부모 노드로 설정한다. (A가 B를 가리키도록) 모든..

최소경로 - 전보

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 문제 저작권 문제가 될 수 있어 문제는 삭제합니다. 풀이 코드 class Heap { var heapArray: [[T]] var root: T? { if isMaxHeap { maxHeapify() } else { minHeapify() } return heapArray[0].first } var count: Int { return heapArray.count } var isEmpty: Bool { return heapArray.isEmpty } var isMaxHeap: Bool init(_ n: [[T]], isMaxHeap: Bool) { heapArray = n self.isMaxHeap = isMa..

최소경로 - 미래 도시

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 문제 저작권 문제가 될 수 있어 문제는 삭제합니다. 풀이 코드 // 노드의 개수 및 간선의 개수 입력받기 let input = readLine()!.components(separatedBy: " ").map({Int($0)!}) // 노드의 개수 let n = input[0] // 간선의 개수 let m = input[1] // 2차원 배열에 모든 값을 9999999999(무한)으로 초기화 var graph = Array(repeating: Array(repeating: [9999999999], count: n+1), count: n+1) // 자기자신에서 자기자신으로 가는 비용 0으로 초기화 for a in..

최단경로 - 플로이드 워셜

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모드 계산하는 알고리즘이다. 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 2차원 테이블에 최단 거리 정보를 저장한다. 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다. 다이나믹 프로그래밍 유형에 속한다. 플로이드 워셜 알고리즘 동작 과정 step1 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다...

최단경로 - 다익스트라 알고리즘

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 최단경로 알고리즘 최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 각 지점은 그래프에서 노드로 표현된다. 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가..

다이나믹 프로그래밍 - 효율적인 화폐 구성(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 문제 저작권 문제가 될 수 있어 문제는 삭제합니다. 풀이 코드 let n = 3 // 화폐 개수 let m = 7 // 만들어야 하는 금액 let k = [2,3,5] // 계산하지 못하는 경우를 10001로 초기화해줌 var dp = Array(repeating: 10001, count: m+1) // 0원인경우는 화폐를 사용하지 않았을때 만들수 있으므로 0으로 초기화 dp[0] = 0 // 화폐단위 개수만큼 반복 for i in 0..

다이나믹 프로그래밍 - 바닥 공사(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 문제 저작권 문제가 될 수 있어 문제는 삭제합니다. 풀이 코드 let n = 3 var dp = Array(repeating: 0, count: 1000 + 1) // n = 1일때 경우의 수 dp[1] = 1 // n = 2일때 경우의 수 dp[2] = 3 for i in 3.. 1 n = 2 일때 경우의 수 => 3 n = 3 일때 경우의 수 => 5 덮개중 제일 큰 사이즈가 2x2이기 때문에 N - 2 미만의 길이에 대해서는 고려할 필요 없음 점화식을 구해보면 i-1 길이까지 덮개가 채워져 있을때 남은 바닥을 채울수 있는 경우의 수는 2x1 사이즈의 덮개 하나밖에 없으므로 경우의 수가 1개가 된다. i-..