BOJ (326) 썸네일형 리스트형 [BOJ] 백준 2166 다각형의 면적 (Swift) 문제 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 풀이 신발끈 공식을 사용하여 풀이하였습니다. 소스코드 후기 신발끈 공식이라는게 있는지도 몰랐습니다. 공식만 안다면 쉽게 풀 수 있는 문제였습니다. [BOJ] 백준 2213 트리의 독립집합 (Swift) 문제 https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 풀이 트리에서 DP를 사용하는 문제입니다. 독립 집합을 만들 때, 최대 가중치를 구하기 위해 다음과 같이 작성할 수 있습니다. 현재 노드를 선택헀다면, 다음 노드를 선택 못함 (현재노드의 가중치를 더함) 현재 노드를 선택하지 않았다면, 다음 노드를 선택하거나 안하거나. max(다음 노드를 선택한 값, 다음 노드 선택 안한 값) 점화식은 다음과 같이 세울 수 있.. [BOJ] 백준 2533 사회망 서비스(SNS) (Swift) 문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 풀이 트리에서 DP를 사용하는 문제입니다. 현재 노드가 얼리어답터가 아니라면, 다음 노드는 무조건 얼리어답터여야 함 현재 노드가 얼리어답터라면, 다음 노드는 얼리어답터일 수도.. 아닐 수도.. 점화식은 다음과 같이 정의할 수 있습니다. $f(n, 0) = $: n번 노드가 얼리어답터가 아님 $f(n, 1) = $: n번 노드가 얼리어답터 점화식: $f(n, .. [BOJ] 백준 1949 우수 마을 (Swift) 문제 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 풀이 트리에서 DP를 사용하는 문제입니다. 현재 마을이 우수 마을 이라면 다음 마을은 절대 우수 마을이 될 수 없습니다. 현재 마을이 우수 마을 이라면 다음 마을은 우수 마을일 수도 있고 아닐 수도 있습니다. 여기서 dp로 사용할 배열의 점화식을 다음과 같이 정의할 수 있습니다. $f(n, 0) =$: n번째 마을이 우수 마을이 아님 $f(n, 1) =$: n번째 마을이 우수 마을임.. [BOJ] 백준 15681 트리와 쿼리 (Swift) 문제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 트리에서 DFS + DP를 사용하여 풀 수 있는 문제입니다. r을 루트노드인 트리에서 탐색을 하면서, 서브트리에 속한 정점의 수를 계산할 수 있습니다. 이를 계산하면서, 모든 정점에 대해서 각 정점을 루트로 하는 서브트리에 속한 정점의 수를 DFS + DP를 사용해 계산할 수 있습니다. 소스코드 후기 트리에서 다이나믹 프로그.. [BOJ] 백준 17472 다리 만들기 2 (Swift) 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 구현할게 많았던 문제였습니다. 먼저, 저는 BFS를 사용해 섬에 번호를 부여해주었습니다. 그리고 다리를 놓는 방법에 대해서 고민을 했는데, 다리를 놓으려면 섬의 외각에 있어야 합니다. 섬에 외각에 있다는 것은 자신을 중심으로 상, 하, 좌, 우에 한 뱡향이라도 바다가 있으면 섬의 외각이라고 판별하였습니다. 섬의 좌표에서 상 하 좌 우를 확인하고, 바다가 있다면 다리.. [BOJ] 백준 6497 전력난 (Swift) 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 MST를 만드는 알고리즘으로 풀이할 수 있는 문제입니다. 저는 크루스칼 알고리즘을 사용하여 풀이하였고, 단순히 모든 길에 대한 거리를 더한 값에서, MST를 이루는 거리를 빼주는 값이 절약되는 최대 액수입니다. 소스코드 후기 MST를 만드는 방법에 대해 알고있다면 어렵지 않게 풀 수 있는 문제였습니다. [BOJ] 백준 1774 우주신과의 교감 (Swift) 문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 MST를 구하기 위해 크루스칼 알고리즘으로 풀이할 수 있는 문제입니다. 모든 우주신의 좌표와 좌표사이의 거리를 직접 구해주어야 합니다. 즉, 노드간의 간선을 구해주어야 합니다. 그 이후 통로의 개수는 합집합 연산을 통해 미리 합쳐주고, 간선의 비용을 오름차순으로 정렬을 하고, 사이클이 이루어지지 않는다면 이어줍시다. 그렇다면 최소 비용을 구할 수 있습니다. 소.. 이전 1 ··· 4 5 6 7 8 9 10 ··· 41 다음
