목록대학교/Algorithm (105)
차근차근
0. 제목 백준 1094 막대기 BOJ 1094 막대기 C++ 1094 막대기 1. 문제 https://www.acmicpc.net/problem/1094 2. 풀이 처음에 길이가 64인 막대기를 가지고 있다. 현재 막대기가 만들고자 하는 막대기보다 길면 가지고 있는 막대기를 반 자른다. 짧다면 만들고자 하는 막대기에서 현재 막대기 길이를 뺀 후 갱신기킨다. 또한 막대기 한 개를 사용했으므로 cnt값을 1 증가시켜준다. X가 0이 되면 루프가 종료되고 cnt값이 필요한 막대기의 수가 된다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main(int argc, const cha..
0. 제목 백준 1065 한수 BOJ 1065 한수 C++ 1065 한수 1. 문제 https://www.acmicpc.net/problem/1065 2. 풀이 어떤 양의 정수 X의 자리수가 등차수열을 이루면 그 수를 한수라고 한다. 1부터 99까지는 모두 한수이다. 문제에서 1000이하의 수를 입력 받는다고 하였으니 100이상, 1000이하 인 수들을 처리해주면 된다. 1의 자리, 10의 자리, 100의 자리를 각각 구해서 각 자리수 사이의 공차가 같으면 한수여부를 판단하는 배열 arr의 해당 index 값을 true로 설정해준다. 마지막에 총 한수의 개수를 구할 때 1부터 입력받은 N까지 루프를 실행하여 배열 arr의 해당 index값이 true이면 개수를 센다. 그 개수가 한수의 개수이다. 3. 코..
0. 제목 백준 1922 네트워크 연결 BOJ 1922 네트워크 연결 C++ 1922 네트워크 연결 1. 문제 https://www.acmicpc.net/problem/1922 2. 풀이 Union-Find 방식을 사용하였다. find는 root를 찾아주는 함수이고 merge는 서로 다른 집합에 있을 때 하나의 집합으로 합쳐주는 함수이다. comp는 가중치를 기준으로 하여 오름차순으로 정렬되도록 설정하는 함수이다. main함수에서는 edge들 정보를 입력받고 가중치를 기준으로 오름차순 정렬을 한다. 그 후 입력받은 노드들이 같은 집합에 있는지를 판단하여 같은 집합에 있지 않으면 하나의 집합으로 합쳐주며 길이를 더해준다. 그 과정을 반복하면 모든 컴퓨터를 연결하는데 필요한 최소비용이 나온다. 3. 코드 1..
0. 제목 백준 4195 친구 네트워크 BOJ 4195 친구 네트워크 C++ 4195 친구 네트워크 1. 문제 https://www.acmicpc.net/problem/4195 2. 풀이 서로소 집합(Disjoint Set)으로 해결할 수 있다. Union-find 방식을 사용한다. 기존 union방식과는 다르게 각 집합에 포함에 있는 원소 개수를 구하고 반환해준다. key값과 value값을 쌍으로 사용하는 map 을 사용한다. num을 통해 노드번호를 부여한다. 처음에는 시간초과가 떴지만 ios_base~cin 이 부분으로 속도를 향상시켜주어서 정답처리가 되었다. 3. 코드 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 ..
0. 제목 백준 1010 다리 놓기 BOJ 1010 다리 놓기 C++ 1010 다리 놓기 1. 문제 https://www.acmicpc.net/problem/1010 2. 풀이 mCn을 묻는 문제이다. dp방식을 이용하여 값을 저장해놓는다. dp[i][j]의 값은 왼쪽에 i개, 오른쪽에 j개가 있을 때 연결 방법의 개수이다. 왼쪽에 3개, 오른쪽에 5개가 있다고 가정해보자. 왼쪽의 가장 위에 것이 오른쪽 가장 위로 가면 나올 수 있는 방법 수는 dp[i-1][j-1] 이 된다. 왼쪽의 가장 위에 것이 오른쪽 두번 째로 가면 나올 수 있는 방법 수는 dp[i-1][j-2] 이 된다. 이렇게 쭉 반복하면 2차원 인덱스의 값은 j-1, j-2, ..., i-1 가 가능하다. 점화식을 써보면 다음과 같다. dp..
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 구조를 사용한다. 사이클이 생기지 않는 조건..
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[]) {..
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..
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이 홀수이면 넓..