Scat

yongmin's dev blog

[BOJ] 11723번 집합 - C++

"동적 계획법 3"

문제 집합 풀이 비트마스크에 대해 알게된 문제이다. 비트마스크는 예를 들어 {E, D, C, B, A}의 부분집합 {C, A}를 00101(2)과 같이 표현하는 것을 의미한다. 비트마스크 연산자에는 다음과 같다. AND 연산(&), OR 연산(ㅣ), XOR 연산(^) : 같으면 0을, 다르면 1 NOT 연산(~), Shi...

Posted by Yongmin on September 6, 2021

[BOJ] 1949번 우수 마을 - C++

"트리에서의 동적 계획법"

문제 우수 마을 풀이 DFS와 DP를 이용한 문제이다. 트리의 독립집합 문제와 크게 다르지 않다. dp[index][2]를 통해 index 노드를 포함한 경우와 포함하지 않은 경우를 생각하여 dfs function call을 통해 맨 아래에서부터 채워서 위로 올라가 원하는 정답을 도출하는 문제이다. 소스 코드 1 2 3 4 5 6 7 8 9 1...

Posted by Yongmin on August 31, 2021

[BOJ] 2533번 사회망 서비스(SNS) - C++

"트리에서의 동적 계획법"

문제 사회망 서비스(SNS) 풀이 DFS와 DP를 이용한 문제이다. 트리의 독립집합 문제와 크게 다르지 않다. dp[index][2]를 통해 index 노드를 포함한 경우와 포함하지 않은 경우를 생각하여 dfs function call을 통해 맨 아래에서부터 채워서 위로 올라가 원하는 정답을 도출하는 문제이다. 소스 코드 1 2 3 4 5 6 ...

Posted by Yongmin on August 31, 2021

[BOJ] 2213번 트리의 독립집합 - C++

"트리에서의 동적 계획법"

문제 트리의 독립집합 풀이 DFS와 DP를 이용한 문제이다. Reference를 참조하였다. dp[index][2]를 선언하여 dp[index][0]은 index번째 정점이 포함이 된 경우. dp[index][1]은 index번째 정점이 포한된 경우를 의미한다. 계속해서 dfs로 function call을 하고, dp[now]0는 그 전 자식노드를...

Posted by Yongmin on August 31, 2021

[BOJ] 15681번 트리와 쿼리 - C++

"트리에서의 동적 계획법"

문제 트리와 쿼리 풀이 DFS를 이용한 문제이다. 루트 번호가 주어졌기 때문에, DFS를 통해서 call이 되는 수만큼을 dp배열에 저장해준다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3...

Posted by Yongmin on August 30, 2021

[BOJ] 17472번 다리 만들기 2 - C++

"최소 신장 트리"

문제 다리 만들기 2 풀이 DFS와 MST를 이용한 문제이다. DFS를 이용하여 인접한 땅들을 하나로 묶는 작업을 하고 이 때 섬의 갯수를 counting한다. 그 이후, 상하좌우 한 방향으로만 계속 가게 하여 섬 번호가 다른것이 있으면 distance를 push하고 break를 한다. 그 이후 distance들을 오름차순으로 정렬하여 크루스칼 알...

Posted by Yongmin on August 26, 2021

[BOJ] 2887번 행성 터널 - C++

"최소 신장 트리"

문제 행성 터널 풀이 MST를 구하는 문제이다. N^2으로 각각의 dist를 모두 구해서 sort한 다음 크루스칼 알고리즘을 적용하면 메모리 초과로 인해 실패하게 된다. 이 문제에서는 단순히 x, y, z좌표 각각의 차이의 min값을 distance로 정의하고 있기에, x, y, z값들을 sort하여 각각 인접한 사이의 거리들을 edge 벡터에 넣...

Posted by Yongmin on August 25, 2021

[BOJ] 1774번 우주신과의 교감 - C++

"최소 신장 트리"

문제 우주신과의 교감 풀이 MST를 구하는 문제이다. 크루스칼 알고리즘을 이용하여 조건에 맞게 미리 집합을 형성해놓고 다른 지점들을 merge를 시켰을 때 cost를 추가해나가며 결과를 도출하면 된다. 코드는 Reference를 참조하였다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

Posted by Yongmin on August 25, 2021

[BOJ] 4386번 별자리 만들기 - C++

"최소 신장 트리"

문제 별자리 만들기 풀이 모든 정점을 잇는 최소 간선 가중치 합을 구하는 문제이다. 크루스칼 알고리즘을 사용한다. 이를 위해 모든 좌표간의 거리들을 구하여 넣은 Edge 벡터를 오름차순으로 sort한다. 제일 거리가 가까운 첫번째 간선부터 차례대로 집합 형성을 시도한다. 이 때, 사이클이 형성되는 집합은 형성하지 않으며 모든 간선에 대해 시도한다....

Posted by Yongmin on August 24, 2021

[BOJ] 9372번 상근이의 여행 - C++

"최소 신장 트리"

문제 상근이의 여행 풀이 문제에서 연결된 그래프고, 이미 지나간 경로도 다시 갈 수 있고, 최소 비행기 종류를 출력하는 문제이다. 가중치도 존재하지 않기에 MST에서는 간선의 개수는 정점의 개수 - 1 이므로, N-1을 출력해주면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #in...

Posted by Yongmin on August 24, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구