알고리즘 문제풀이
-
[백준/BOJ] 1167번 트리의 지름 (C++)알고리즘 문제풀이/백준 2020. 12. 30. 15:53
www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 트리 유형의 문제 (다시 풀기) 트리에서의 지름이란 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다고 합니다. 지름을 구하는 유명한 공식(?)이 있다는 것을 처음으로 알게 되었는 데, 트리에서 지름을 구하는 방법은 다음과 같습니다. 1. 트리에서 임의의 정점 v1을 잡는다. 2. 정점 v1에서 가장 먼 정점 v2를 찾는다. 3. 정점 v2에서 가장 먼 정점 v3를 찾는..
-
[백준/BOJ] 1238번 파티 (C++)알고리즘 문제풀이/백준 2020. 12. 30. 11:45
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 이용하면 해결할 수 있는 문제 (다시 풀기) 새롭게 알게된 점 pair형에서 sort함수를 쓰면 first를 기준으로 적용된다. (default) 다익스트라를 이용해 1번부터 n번 정점까지 target으로 갈 수 있는 최소 비용을 dist배열에 갱신한 후, res배열에 복사합니다. dist배열을 초기화하고, 이번에는 target에서 1번부터 n번 정점까지 갈 ..
-
[백준/BOJ] 1929번 소수 구하기 (C++)알고리즘 문제풀이/백준 2020. 12. 29. 21:30
www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 입력값이 최대 1,000,000 이므로 단순 소수를 찾는 방법은 시간 초과가 발생합니다. 따라서 에라토스테네스의 체라는 방법을 이용해서 해결해야합니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int m, n; cin>>m>>n; vector v(n + 1); for(int i = 2; i
-
[백준/BOJ] 1260번 DFS와 BFS (C++)알고리즘 문제풀이/백준 2020. 12. 29. 21:20
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를 연습할 수 있는 좋은 문제입니다. 인접 행렬 혹은 인접 리스트를 이용해서 그래프를 만들 수 있는데, 저는 인접 리스트를 이용했습니다. ※ 인접 행렬과 인접 리스트의 차이점이 궁금했었는데 잘 설명한 블로그 글이 있어 주소를 남겨봅니다! seohyun0120.tistory.com/entry/C-BFS%EC%99%80-DFS-%EC%9D%B8%EC%..
-
[프로그래머스/Level 2] 삼각 달팽이 (C++)알고리즘 문제풀이/프로그래머스 2020. 12. 29. 16:16
programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 위의 그림에서 숫자가 채워지는 방향이 위/오른쪽/왼쪽 위 대각선 총 3가지인 것을 확인할 수 있습니다. 또한 방향의 전환은 n번 이루어지는 것을 확인할 수 있습니다. 이러한 규칙을 이용해서 2차원 배열에 값을 저장하고, 저장이 끝난 후 배열 전체를 탐색해 0보다 큰 경우만 벡터에 집어넣어 리턴하였습니다. #include #include using namespace std; int m..
-
[백준/BOJ] 9095번 1, 2, 3 더하기 (C++)알고리즘 문제풀이/백준 2020. 12. 28. 17:08
www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 브루트 포스(완전 탐색) 또는 DP 둘다 이용해서 풀 수 있는 문제 브루트 포스로 해결할 경우 DFS를 통해 1, 2, 3을 이용하여 n을 나타내는 모든 경우의 수를 구하면 됩니다. DP를 통해 해결할 경우 다음과 같은 규칙을 찾아내면 됩니다. 1을 표현할 수 있는 경우 : 1 -> 1가지 2를 표현할 수 있는 경우 : 1+1, 2 -> 2가지 3을 표현할 수 있는 경우 : 1+1+1, 1+2, 2+1, 3 -> 4가지 따라서 다음과 같은 점화식을 도출해낼 수 있습니다 dp[n] = dp[n - 2] + dp..
-
[백준/BOJ] 1182번 부분수열의 합 (C++)알고리즘 문제풀이/백준 2020. 12. 28. 16:51
www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제 현재 누적합과 현재 인덱스 값을 더한게 s와 같은지 확인해서 같으면 answer를 증가시키고, 그게 아니라면 현재 인덱스 값을 더하거나, 더하지 않고 그대로 재귀함수를 호출합니다. 이때 sum + v[idx]의 값과 s의 비교를 기저조건에서 하지 않는 이유는 입력값의 조건이 음수가 포함이므로 이를 기저조건에 두면 답인 경우가 더해지지 않는..
-
[백준/BOJ] 6603번 로또 (C++)알고리즘 문제풀이/백준 2020. 12. 28. 16:20
www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제입니다. k개의 수에서 6개를 뽑는 조합을 DFS를 이용해 구현하였습니다. #include #include #include using namespace std; int res[6]; void DFS(int idx, int cnt, vector v) { if(cnt == 6) { for(int i = 0; i < 6; i++) { cout