SW

0. 제목 백준 1325 효율적인 해킹 BOJ 1325 효율적인 해킹 C++ 1325 효율적인 해킹 1. 문제 https://www.acmicpc.net/problem/1325 2. 풀이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 것이 문제이다. dfs를 사용하여 연결되어 있는 컴퓨터의 수를 센다. 각 컴퓨터를 시작점으로 dfs를 시행하여 컴퓨터 수를 세고 그것을 depth배열에 담는다. depth배열의 원소 중 최댓값을 구한다. depth배열의 원소 값 중 최댓값과 같은 값을 가지고 있는 index들을 순서대로 출력한다. 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 28 29 30 ..

0. 제목 백준 2606 바이러스 BOJ 2606 바이러스 C++ 2606 바이러스 1. 문제 https://www.acmicpc.net/problem/2606 2. 풀이 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. dfs를 활용하여 연결되어 있는 컴퓨터들의 개수를 구한다. dfs내부에서 감염 컴퓨터 수를 세는 cnt 변수를 사용한다. 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터를 구하는 문제이기 때문에 dfs(1)을 수행하여 정답을 구할 수 있다. 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 28 29 30 31 32 33 3..

0. 제목 백준 1764 듣보잡 BOJ 1764 듣보잡 C++ 1764 듣보잡 1. 문제 https://www.acmicpc.net/problem/1764 2. 풀이 string자료형을 가지고 있는 vector를 이용한다. binarySearch를 이용하여 탐색시간을 줄인다. binarySearch로 듣도 못한 사람이 들어있는 vector v를 탐색해서 보도 못한 사람과 같은 이름이 있으면 듣도 보도 못한 사람을 넣는 vector result에 push_back으로 넣어준다. vector result를 sort를 사용해 오름차순 정렬을 한다. size()를 사용해 개수를 출력하고, 원소들을 출력해준다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

0. 제목 백준 6581 HTML BOJ 6581 HTML C++ 6581 HTML 1. 문제 https://www.acmicpc.net/problem/6581 2. 풀이 문자열이 인 경우, 인 경우, 둘다 아닌 경우로 크게 나눌 수 있다. 인 경우, 개행문자를 사용하고 sum=0을 통해 개행 후 줄의 첫부분으로 좌표를 옮긴다. 인 경우, 줄의 첫부분일 경우와 아닐 경우를 구분해서 구현한다. 둘다 아닌 경우에는, 줄의 첫부분인 경우, 입력된 문자열이 들어와서 80자 이하인 경우, 80자 넘는 경우로 나눌 수 있다. sameline을 통해서 같은 줄 여부를 확인하고 sum을 통해서 좌표를 조정하며 구현한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..

0. 제목 백준 2002 추월 BOJ 2002 추월 C++ 2002 추월 1. 문제 https://www.acmicpc.net/problem/2002 2. 풀이 추월 여부를 확인해주는 함수를 작성하였다. 인자로 들어오는 vector는 추월한 차들이 원소로 들어있는 vector이다. 그 vector와 문자열 s를 비교하여 있으면 true를, 없으면 false를 반환해준다. main함수에서 들어오는 차들이 담겨있는 v1의 인덱스를 idx1로 놓고 나가는 차들이 담겨있는 v2의 인덱스를 idx2로 놓는다. 비교를 실시하여 같으면 인덱스를 하나씩 증가시켜준다. 다르다면 v1[idx1] 값이 추월vector에 속해있는지 검사한다. 속해있으면 idx1을 1증가해주고, 속해있지 않으면 v2[idx2]를 v3에 넣어주..

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..