본문 바로가기

전체 글282

[최단경로 알고리즘 - 3] 벨만 포드 알고리즘 * 벨만 포드 알고리즘이란? 시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 벨만 포드 알고리즘의 특징은 다음과 같다. 1. 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 2. 음수 사이클의 존재 여부를 알 수 있다. 음수 사이클 안에서 무한루프를 도는 경우를 알 수 있는 방법은, 그래프 정점의 개수를 V라고 할 때 인접 간선을 검사하고 거리 값을 갱신하는 과정을 V-1 번으로 제한하면 가능해진다. 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거쳐 가는 최대 간선 수는 V-1개이기 때문에 V번째 간선이 추가되는 순간 사이클이라고 판단할 수 있게 된다. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)이다. 매번 모든 간선을 전부 확인하기.. 2021. 11. 14.
11404. 플로이드 (Swift, Python) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 적용하는 문제. 모든 도시에서 다른 모든 도시까지의 최단거리를 구해준다. 간단하게 플로이드 워셜 알고리즘을 적용하면 되는데 문제에서 주어진 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.'만 주의하면 된다. a에서 b로 가는 도시의 노선이 여러개 주어질 수 있는데 그 중 가장 적은 비용이 드는 노선을 배열에 설정해줘야 한다. 코드 [Swift] 1 .. 2021. 11. 12.
[LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance (swift, python) Find the City With the Smallest Number of Neighbors at a Threshold Distance - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 각 도시에서 distanceThreshold 이하의 거리를 갖고 있는 도시의 개수를 카운트 해야 한다. 즉, '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 해당한다. 그렇기 때문에 최단 경로 알고리즘에서 플로이드 워셜 알고리즘을 사용해서 풀 수.. 2021. 11. 12.
[최단경로 알고리즘 - 2] 플로이드 워셜 알고리즘 * 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 이번에 알아볼 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점에서 다익스트라 알고리즘과 다르다. 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜의 총 시간 복잡도는 O.. 2021. 11. 11.
[LeetCode] 743. Network Delay Time (swift, python) Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 다익스트라 알고리즘을 활용해서 풀 수 있는 문제. 시작점 k에서 모든 노드까지의 최단거리를 구해준다. distance 배열에 k에서 각 노드 까지의 최단거리가 구해진다. 문제에서 모든 노드에 신호를 보내기까지 걸리는 시간을 구하라 했으므로 distance 배열에서 가장 큰 값(걸리는 시간이 가장 큰 경우)이 문제의 답이 된다. 만약 k에서 시작해서 도달할 수 없는 노드가 있.. 2021. 11. 3.
[최단 경로 알고리즘 - 1] 다익스트라 알고리즘 * 최단 경로 알고리즘이란? 최단 경로 알고리즘이란 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로를 찾는 경우에는 다양한 종류가 있는데, 각 종류 별로 효율적인 알고리즘이 존재한다. '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 사례가 존재한다. 최단 경로 문제는 보통 그래프를 이용해서 표현하며 각 지점은 그래프에서 '노드'로 표현하고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 최단 경로 알고리즘에는 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 존재한다. 이 중 다익스트라에 대해서 먼저 알아보자. * 다익스트라(Dijkstra) 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 .. 2021. 10. 31.
[Swift] Chapter 30. 불명확 타입 반환 타입에 불명확 타입(Opaque Types)을 사용하면 반환할 타입의 정확한 타입을 알려주지 않은채로 반환하겠다는 것을 의미한다. 프로퍼티나 서브스크립트의 선언 혹은 함수의 반환 타입 위치에 프로토콜을 쓰면서 앞에 some을 붙이면, '이 프로토콜을 준수하는 어떤 타입 중에 하나일 것은 분명하다'는 뜻이다. 언뜻 보면 제네릭과 비슷해 보이지만 많이 다르다. 제네릭은 정의해 줄 때 정확히 어떤 타입이 들어올지 모르는 상태로 플레이스 홀더를 만들어 준다. 불명확 타입은 반대로 외부에서는 어떤 타입이 나에게 반환될지 모른다. 다시 말해서 제네릭은 외부에서 타입을 지정해 주는 것이고, 불명확 타입은 내부에서 타입을 정해서 내보내게 되는데, 밖에서는 정확히 어떤 타입인지는 몰라도 쓸 수 있는 것이다. 그래서.. 2021. 10. 24.
[Swift] Chapter 29. 메모리 안전 스위프트는 안전을 중요시하는 언어이다. 그래서 컴파일러가 코드에서 위험을 줄일수 있도록 많은 장치를 두었다. 그 중 큰 부분을 차지하는 것이 메모리의 안전한 접근이다. 변수를 사용하기 전에 초기화를 강제하고, 해제된 메모리에 접근할 수 없도록 설계된 것들이 그 대표적인 예다. 스위프트는 메모리를 자동으로 관리하기 때문에 특별한 경우가 아니라면 프로그래머가 메모리의 접근에 대해 크게 신경쓸 필요가 없다. 스위프트 컴파일러는 메모리 접근 충돌이 생길만한 코드를 미연에 알려준다. 이번 장에서는 이에 대해 알아보자. 29.1 메모리 접근 충돌의 이해 프로그래머가 변수에 값을 할당한다던가 함수의 전달인자로 변수의 값을 전달하는 등 다양한 경우에 코드를 통해 메모리에 접근하게 된다. /* 코드 29-1. 코드를 통.. 2021. 10. 24.
[Swift] Chapter 28. 오류처리 스위프트가 제공하는 오류처리 기능에 대해 알아보자. 28.1 오류처리란 오류처리(Error Handling)는 프로그램이 오류를 일으켰을 때 이것을 감지하고 회복시키는 일련의 과정이다. 오류처리 기능을 통해 프로그램 자체적으로 오류를 해결할 수도 있고, 사용자와 상호작용을 통해 오류를 어떤 방향으로 풀어나갈지 제어할 수도 있다. 28.2 오류의 표현 스위프트에서 오류는 Error라는 프로토콜을 준수하는 타입의 값을 통해 표현된다. Error 프로토콜은 사실상 요구사항이 없는 빈 프로토콜일 뿐이지만, 오류를 표현하기 위한 타입(주로 열거형)은 이 프로토콜을 채택한다. 스위프트의 열거형은 오류의 종류를 나타내기에 아주 적합한 기능이다. 연관 값을 통해 오류에 관한 부가 정보를 제공할 수도 있다. [코드 28.. 2021. 10. 24.

티스토리툴바