목록대학교/Algorithm (100)
SW
[백준 1197] 최소 스패닝 트리
0. 제목 백준 1197 최소 스패닝 트리 BOJ 1197 최소 스패닝 트리 C++ 1197 최소 스패닝 트리 1. 문제 https://www.acmicpc.net/problem/1197 2. 풀이 최소 스패닝 트리 = MST(Minimum Spanning Tree) MST를 구하는 방법은 Kruskal Algorithm과 Prim Algorithm이 있다. 이번 문제는 Kruskal Algorithm을 이용해서 풀어보겠다. Kruskal 알고리즘은 가중치가 가장 작은 간선부터 하나씩 이어나가며 모든 정점을 방문하는 방법이다. 이때 주의할 점은 사이클이 발생하면 안된다는 점이다. 사이클 발생 유무를 체크하기 위해서 Kuruskal 알고리즘은 Union-Find 구조를 사용한다. 사이클이 생기지 않는 조건..
[백준 1476] 날짜 계산
0. 제목 백준 1476 날짜 계산 BOJ 1476 날짜 계산 C++ 1476 날짜 계산 1. 문제 https://www.acmicpc.net/problem/1476 2. 풀이 모든 경우의 수를 탐색한다. 완전 탐색(Brute-force)이라고도 한다. 각각 년도가 15, 28, 19를 초과 할 수 없다. 초과하면 다시 1로 갱신이 된다. 나눗셈의 나머지를 이용해서 문제를 풀 수 있다. 현재 년도에서 각각의 수를 뺀 후 나머지가 모두 0일때 반복문을 탈출한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int E, S, M, year; int main(int argc, const char * argv[]) {..
[백준 15953] 상금 헌터
0. 제목 백준 15953 상금 헌터 BOJ 15953 상금 헌터 C++ 15953 상금 헌터 1. 문제 https://www.acmicpc.net/problem/15953 2. 풀이 조건문으로 범위를 지정하는 방식으로 구현하는 것도 가능하다. 아래 풀이는 다른 방식이다. 처음에는 각 등수별로 지정되는 인원들을 vector에 담으려고 하였으나 풀다보니 vector가 필요없었다. 상금을 배열에 담아두고 등수와 등수에 할당 된 인원수에 대한 반복문을 이용하였다. 입력받은 등수에 해당하는 등수와 상금배열의 인덱스의 관계를 이용해 같으면 변수 firstGet, secondGet에 담았다. 합에 10000을 곱해주면 상금의 합이 구해진다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
[백준 2133] 타일 채우기
0. 제목 백준 2133 타일 채우기 BOJ 2133 타일 채우기 C++ 2133 타일 채우기 1. 문제 https://www.acmicpc.net/problem/2133 2. 풀이 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 것이다. 앞서 풀었던 타일 채우기 문제와는 살짝 달랐다. 앞에서 풀었던 타일 문제들은 N의 값이 늘어날 때 새로운 종류의 타일 모양이 나오지 않았다. 그러나 이 문제는 N이 2씩 늘어날때마다 새로운 모양 2개가 추가적으로 생겼다. 먼저 끝 2칸을 제외하면 3가지 방법이 나온다. 그리고 4칸, 6칸, 8칸.... 제외하면 2가지씩 추가적으로 생긴다. 그리고 3xN의 크기의 벽을 2x1, 1x2로 채우기 위해서는 N이 짝수이어야 한다. N이 홀수이면 넓..
[백준 4963] 섬의 개수
0. 제목 백준 4963 섬의 개수 BOJ 4963 섬의 개수 C++ 4963 섬의 개수 1. 문제 https://www.acmicpc.net/problem/4963 2. 풀이 백준 2667 단지번호붙이기 문제와 비슷한 문제이다. 2667번은 상하좌우를 따지는 것이었다면 이 문제에서는 대각선까지 고려해야한다. dfs에서는 여덟 방향 모두 탐색을 하면서 좌표가 0보다 작아지거나 주어진 넓이나 높이보다 같거나 커지면 넘어가면서 탐색한다. 재귀적으로 코드를 작성했으므로 여덟방향 중 이어진 부분이 있으면 그 덩어리를 전부 탐색완료 할 것이다. main함수에서 탐색을 할 때 값이 1이면서 방문하지 않은 부분을 반복문 내에서 탐색한다. 한 덩어리를 탐색완료 할 때마다 덩어리개수를 1씩 증가시켜준다. 탐색을 모두 마..
[백준 1966] 프린터 큐
0. 제목 백준 1996 프린터 큐 BOJ 1996 프린터 큐 C++ 1996 프린터 큐 1. 문제 https://www.acmicpc.net/problem/1966 2. 풀이 중요도에 따라 출력되는 순서가 다르므로 우선순위 큐를 사용한다. C++ STL의 queue와 priority_queue를 사용한다. 먼저 q의 원소들을 입력받을 때 pair를 이용하여 인덱스와 중요도 값을 쌍으로 입력 받고 q에 push 해준다. 그리고 prioirity_queue pq; 와 같이 우선순위 큐를 선언한다. 우선순위 큐에는 중요도 값만 push 해준다. q의 원소가 0개가 아닌동안 루프를 돈다. q의 가장 먼저 들어온 원소 즉, 가장 앞에 있는 원소의 인덱스와 중요도 값을 변수 nowidx, nowval에 저장한다...
[백준 2170] 선 긋기
0. 제목 백준 2170 선 긋기 BOJ 2170 선 긋기 C++ 2170 선 긋기 1. 문제 https://www.acmicpc.net/problem/2170 2. 풀이 먼저 from, to N쌍을 입력받는다. 그 후 from을 기준으로 정렬을 한다. 그럼 선끼리 겹치는 선들이 있을 것이고 겹치지 않는 선들이 있을 것이다. 겹치지 않는 경우에는 현재 길이에 l-r 만큼 더해주면 되고 겹치는 경우에는 오른쪽 끝을 다음 번 오른쪽 끝으로 갱신시켜주면 된다. 반복문이 끝난 후에는 마지막으로 갱신된 l-r을 더해주면 답이 나온다. 주의할 점은 이 문제에서 N과 선택한 지점의 범위가 크다. 따라서 main함수의 첫 세줄을 추가 하지 않았을 때는 시간초과로 떴다. 저 세줄을 추가하면 정답처리가 된다. 3. 코드 ..
[백준 1699] 제곱수의 합
0. 제목 백준 1699 제곱수의 합 BOJ 1699 제곱수의 합 C++ 1699 제곱수의 합 1. 문제 https://www.acmicpc.net/problem/1699 2. 풀이 dp방식을 사용하였다. 먼저 dp의 각 원소들을 1로만 이루어진 개수로 초기화시켰다. 이중반복문에서 i와 j는 1부터 시작할 필요가 없다. 이유는 dp[i] = i 여기서 초기화를 했는데 모두 1로 이루어진 경우를 나타낸 것이다. 따라서 2부터 시작해도 상관이 없다. 오히려 더 빠르다. dp[i] = min(dp[i], dp[i-j*j] + 1); 이 부분은 dp[i] 즉, 초기에 설정했던 값과 dp[i-j*j]+1 중 최솟값을 고르는 것이다. dp[i-j*j] 에 1을 더해주는 이유는 j*j에서 항이 1개 나오기 때문이다...
[백준 1149] RGB거리
0. 제목 백준 1149 RGB거리 BOJ 1149 RGB거리 C++ 1149 RGB거리 1. 문제 https://www.acmicpc.net/problem/1149 2. 풀이 이웃끼리는 같은 색을 칠할 수 없다. RGB를 각각 0번, 1번, 2번 색이라 하겠다. 0번색을 칠하면 이웃집은 1, 2가 가능하고 1번색을 칠하면 이웃집은 0, 2가 가능하고 2번색을 칠하면 이웃집은 0, 1이 가능하다. arr[i][j]은 i번째 집에 j번 색으로 칠하는 비용이다. dp배열의 초기값으로 첫번째 집의 비용을 설정해주었다. 그 다음부터 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0] 와 비슷한 방식으로 1이면 0,2, 2이면 0,1로 설정하여 실행하였다. 그렇게 마지막 N..