본문 바로가기
728x90

전체 글205

[BOJ/백준] 11724 연결 요소의 개수 ● [문제번호 11724] 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ● 알아야 할 것 : BFS : DFS : vector 자료구조와 메소드 ● 풀이 과정 : 다음 조건을 만족하면 연결 요소가 될 수 있다. (참고) 조건 1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다. 조건 2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된.. 2021. 9. 13.
[BOJ/백준] 1260 DFS와 BFS ● [문제번호 1260] DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ● 알아야 할 것 : DFS(재귀, 비재귀), BFS : vector 자료구조와 메소드 : stack 자료구조와 메소드 : queue 자료구조와 메소드 ● 풀이 과정 : 아래 코드는 구현방법3 을 적용했다. (코드는 구현방법1, 2, 3 모두 있다) 구현방법1 (오름차순 → DFS 선택1 → 방문기록 초기화 → BFS).. 2021. 9. 13.
[BOJ/백준] 13023 ABCDE ● [문제번호 13023] ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ● 알아야 할 것 : 그래프 : DFS : 재귀 ● 풀이 과정 : 앞서 풀었던 DFS와 비슷하지만, 그래프에 적용하여 구현된 DFS이다. : 문제를 이해하기 조금 헷갈릴 수 있는데 이해한 바로는 주어진 친구 관계도에서 5명을 한번에 이어질 수 있는가 를 확인하면 된다. : BFS보다 DFS를 이용하여 구현해야겠다는 생각이 들었다. DFS는 재귀와 반복문을 이용하여 구현할 수 있는데 반복문으로 계속 시도하려다 친구 관계 5명을 확인하는 부분이 복잡하게 구현될 것 같아.. 2021. 9. 13.
[BOJ/백준] 14391 종이 조각 ● [문제번호 14391] 종이 조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net ● 알아야 할 것 : 비트마스크 : 브루트 포스 (Brute Force) ● 풀이 과정 : 주어진 문제를 읽고 조각의 최대 총합이라면, 행렬의 가로로만 자른 것과 행렬의 세로로만 자른 것을 비교하면 되는 거 아닌가? 왜 중간에 잘라야하지? 싶어서 구현했더니 채점중의 %가 나오기도 전에 '틀렸습니다.' 가 나왔다. 중간에 자를 필요가 있는 반례가 무엇일지 아무.. 2021. 9. 9.
[BOJ/백준] 14889 스타트와 링크 ● [문제번호 14889] 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : [530 - 브루트 포스 - 재귀] 문제집에 있는 동일한 문제 : DFS의 기본 구현 형식에서 크게 벗어나지 않지만, {N/2 명 까지 선택} + {조합} 을 고려하여 구현하면 된다. : bool로 이루어진 team이라는 1차원 배열을 만들어 각 사람(index)이 스타트 팀(true)인지 링크 팀(false)인지를 구분한.. 2021. 9. 9.
[BOJ/백준] 1182 부분수열의 합 ● [문제번호 1182] 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : 구현을 계속 해도 '시간 초과', '틀렸습니다' 를 반복해서 문제를 다르게 이해했나 생각해서 구글링을 했다. : {기존 배열에서 1개라도 선택했는가} + {부분수열의 원소 총합 = S} 인 경우 부분 수열의 갯수(cnt)를 올린다. 그리고 index가 기존 수열의 끝까.. 2021. 9. 9.
728x90

티스토리툴바