백준 (329) 썸네일형 리스트형 [BOJ] 백준 1991 트리 순회 (Swift) 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 재귀를 사용하여 풀 수 있습니다. 저는 Node라는 구조체 하나를 선언하여, left와 right 프로퍼티를 선언해주었습니다. 이는 자식노드의 왼쪽, 오른쪽을 표현합니다. 입력을 받아서 [String: Node] 의 딕셔너리 컬렉션에 값을 추가하였습니다. 모든 순회가 "A" 노드부터 시작됩니다. preorder의 경우 루트 -> 왼쪽 -> 오른쪽 순으로 탐색을 진행합니다. 함.. [BOJ] 백준 1967 트리의 지름 (Swift) 문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 https://dev-mandos.tistory.com/291 [BOJ] 백준 1167 트리의 지름 (Swift) 문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정 d.. [BOJ] 백준 1167 트리의 지름 (Swift) 문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 DFS를 사용해서 풀 수 있습니다. 임의의 노드에서 출발하여 가장 먼 거리에 있는 노드를 탐색해줍시다. 임의의 노드에서 출발하여 가장 먼 거리에 있는 노드는 트리의 지름에 포함되는 노드입니다. 가장 먼 거리에 있는 노드를 찾았다면 그 노드에서 부터 가장 깊은 곳이 트리의 지름이 됩니다. 소스코드 후기 처음에는 모든 노드에 대해 DFS나 다익스트라를 해봐야하나... 생각이.. [BOJ] 백준 11725 트리의 부모 찾기 (Swift) 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 문제 그대로 트리에서 각 노드의 부모를 찾는 문제입니다. 루트노드를 1로 정하였으므로, 입력에서 주어진 간선들을 연결시켜 줍시다. 1에서부터 BFS, DFS를 사용해서 노드들에 대해서 탐색한다면, 다음 탐색할 노드가 현재 노드의 자식노드가 됩니다. 트리의 부모를 찾기 위해 parent라는 Int 배열을 사용하였고, 값을 -1로 초기화하였습니다. 인덱스를 현재 노드, 값을 부모 노드의 번호로 사용하려고 합니다. parent[4] = 3 이라면, 4의 .. [BOJ] 백준 11780 플로이드 2 (Swift) 문제 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드워셜 알고리즘으로 풀이할 수 있는 문제입니다. 경로를 확인하기 위해 routes[1][5] = [1, 3, 5]와 같이 3차원 Int 배열을 사용하였습니다. 1에서 5로 가는 루트는 1 -> 3 -> 5 를 나타낸 것입니다. 초기의 버스와 버스 사이의 비용은 임의로 큰 수를 넣어주었고, A 도시와 B 도시의 비용을 입력받을 때, 비용을 갱신해주었습니다. 다만 주의해야할 점으로.. [BOJ] 백준 11779 최소비용 구하기 2 (Swift) 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘으로 풀이할 수 있는 문제입니다. 기본적인 다익스트라 알고리즘으로 최소 비용을 구할 수 있습니다. 배열의 인덱스와 값을 갖고 경로를 추적할 수 있도록 routes라는 Int 배열을 선언해주었습니다. routes[5] = 4 라면 4번노드에서 5번노드로 이동하였다는 방식으로 사용했습니다. A -> B로 이동할 때, 최소 비용으로 갱신 된다.. [BOJ] 백준 9019 DSLR (Swift) 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 이 문제는 BFS로 풀 수 있는 문제입니다. A에서 B로 변환하는 4가지 과정에 대해 모두 수행해서 최소의 연산을 출력해주는 문제입니다. 저는 DSLR 연산을 Int의 extension으로 작성을 하였습니다. BFS를 수행하면서, queue에 명령어를 String으로 넣어줬는데 시간초과 판정을 받았습니다. String 값을 더해주는 것도 $O(1)$이지만, 일반적으로 정수 .. [BOJ] 백준 13913 숨바꼭질 4 (Swift) 문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 X에서 X - 1, X + 1, 2 * X 의 방향으로 이동하는 경우 모두 1초가 걸리기 때문에, BFS로 최단비용를 구할 수 있습니다. 최단거리로 간 루트를 구하기 위해 visited라는 Int 배열을 선언하였습니다. 이 Int 배열의 index를 현재 위치, 값을 이전 위치로 사용하려고 합니다. 예를들어 visited[10] = 9 라면, 9에서 출.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 42 다음
