PS (321) 썸네일형 리스트형 [BOJ] 백준 20040 사이클 게임 (Swift) 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 유니온 파인드 알고리즘을 활용하여 풀이할 수 있는 문제입니다. 사이클이 완성되는 경우는 어떠한 경우일까요? 현재 1, 2, 3이 다음과 같이 연결되어있다고 가정해봅시다. 현재 2와 3의 부모노드는 1로 같습니다. 2와 3을 연결하면 사이클을 발생시킵니다. 즉, 같은 부모노드를 가진 것 끼리 연결하게 된다면 사이클이 생성되게 됩니다. 그러므로, 연결을 하기 전에 같은 두 노드가 같은.. [BOJ] 백준 4195 친구 네트워크 (Swift) 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온 파인드로 풀이할 수 있는 문제입니다. 노드가 Int가 아닌 String 값이기 때문에, [String: String] 의 딕셔너리로 선언해주었습니다. 관계의 노드 수를 구하기 위해 level이라는 [String: Int]의 딕셔너리를 선언해주었습니다. 초기 입력받을 때, 부모노드를 자기 자신으로 초기화 해주고, level도 1로 초기화 해주었습니다. 부모 노드를 찾는 .. [BOJ] 백준 1976 여행 가자 (Swift) 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 유니온 파인드 알고리즘으로 풀이할 수 있는 문제입니다. https://dev-mandos.tistory.com/296 [알고리즘] 유니온 파인드(Union-Find) (Swift) 유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음.. [BOJ] 백준 1717 집합의 표현 (Swift) 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드로 풀이할 수 있는 문제입니다. https://dev-mandos.tistory.com/296 [알고리즘] 유니온 파인드(Union-Find) (Swift) 유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Un.. [BOJ] 백준 4803 트리 (Swift) 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 무방향 그래프에서 사이클이 있는 지 판별해야 하는 문제입니다. 여러 방법이 있겠지만 저는 DFS를 사용하였습니다. 무방향 그래프이기 때문에 1번 노드와 2번 노드가 연결되어 있다면, 1 -> 2, 2 -> 1 로 가능하기에 사이클이 존재한다고 할 수 있지만, 이러한 점을 제외하기 위해서, 직전의 노드로 탐색하는 것은 제외하고 이미 방문한 노드를 또 방문한다면 사이클이 .. [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나 다익스트라를 해봐야하나... 생각이.. 이전 1 ··· 4 5 6 7 8 9 10 ··· 41 다음
