SW

0. 제목 백준 7576 토마토 BOJ 7576 토마토 C++ 7576 토마토 1. 문제 https://www.acmicpc.net/problem/7576 2. 풀이 한단계씩 뻗어나가는 것이 효율적이라 판단하여 BFS를 사용하였다. make_pair를 사용하여 좌표쌍을 큐에 push하였다. 처음에 배열 값들을 입력받음과 동시에 그 값이 1이면 큐에 push 해주었다. 큐에는 탐색할 좌표들을 담아놓는다. 큐에 있는 좌표가 더이상 주변의 탐색을 모두 끝낸 좌표일때 pop을 해준다. 지금까지 풀었던 bfs문제들은 bfs함수내부에서 매개변수로 들어온 좌표들을 큐에 push 해주었다. 그러나 이 문제는 입력과 동시에 push 를 하였다. bfs함수내에서 한번의 루프를 돌때마다 한단계씩 뻗어나가고 서로 떨어져있는 ..

0. 제목 백준 2022 사다리 BOJ 2022 사다리 C++ 2022 사다리 1. 문제 https://www.acmicpc.net/problem/2133 2. 풀이 함수 func에서는 주어진 x와 y로 mid를 구한 후 기울기와 피타고라스정리를 이용하여 c에 관해 정리하였다. 수는 소수점 여섯째 자리까지 주어지므로 범위가 0.000001보다 큰동안 반복한다. 이분탐색을 통하여 범위롤 계속 갱신해주고 소수 여섯째자리의 정확도로 mid를 구한다. 절대/상대 오차는 0.001 까지 허용하므로 소수 셋째자리까지 출력해준다. 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 34 #inclu..

0. 제목 백준 2003 수들의 합 2 BOJ 2003 수들의 합 2 C++ 2003 수들의 합 2 1. 문제 https://www.acmicpc.net/problem/2003 2. 풀이 startIdx를 이용해 합의 시작점을 저장해준다. sum이 구하고자 하는 합 M과 같아지면 가능한 경우의 수인 cnt를 1증가시켜주고 M을 넘어가면 while문을 빠져나간다. 만약 while문에서 sum이 M보다 작고 startIdx가 배열의 마지막 원소를 지나치면 즉, N+1 이 되면 while문을 빠져나온다. cnt를 출력하면 정답니다. 그런데 이러한 문제는 투포인터를 사용한다고 하면 된다. 위 방법도 그와 비슷한 방법이지만 투포인터의 내용을 살려 또 다른 코드를 첨부하겠다. 투포인터 방식을 사용하면 위 방식보다 ..

0. 제목 백준 1789 수들의 합 BOJ 1789 수들의 합 C++ 1789 수들의 합 1. 문제 https://www.acmicpc.net/problem/1789 2. 풀이 while문이 돌면서 sum에 num을 더해준다. num을 하나 더해주었으므로 cnt도 1 더해준다. 만약 sum이 구하고자 하는 값 S보다 커지면 현재 cnt 에서 1을 빼준다. 예를 들면, 18을 구하고 싶었다면 1,2,3,4,5,6 까지 가면 21로 18보다 커지고 3을 빼면 되므로 1,2,4,5,6 즉, 5개가 나온다. num은 한 loop가 지날때 마다 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 #include using names..

0. 제목 백준 1932 정수 삼각형 BOJ 1932 정수 삼각형 C++ 1932 정수 삼각형 1. 문제 https://www.acmicpc.net/problem/1932 2. 풀이 합이 최대가 되는 경로에 있는 수의 합을 출력하는 것이 문제이다. 2차원 배열 arr, dp를 할당하고 arr는 각 위치의 값이 담기고 dp는 그 위치로 갔을 때의 합이 담긴다. 그런데 합이 최대가 되어야 하므로 전 단계에서 즉, 윗 줄에서 왼쪽과 오른쪽중 큰 것을 선택해야 한다. 따라서 점화식은 다음과 같다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j] 그런데 좌표를 arr[1][1] 부터 시작하도록 설정하였으며 i-1 이 0이 나오는 dp[i][0]들은 0으로 초기화 시켜..

0. 제목 백준 1735 분수 합 BOJ 1735 분수 합 C++ 1735 분수 합 1. 문제 https://www.acmicpc.net/problem/1735 2. 풀이 유클리드 호제법을 사용하였다. 유클리드 호제법은 두 정수의 최대 공약수를 구하는 방법이다. 먼저 최대 공약수가 아닌 분모의 곱을 사용하여 합을 구한다. 그 후 분모와 분자의 최대공약수를 유클리드 호제법을 사용하여 구하고 분자와 분모를 최대공약수로 나누어준다. 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 #include using namespace std; int gcd(int x, int y){ int z = 1; while(y !..

0. 제목 백준 7562 나이트의 이동 BOJ 7562 나이트의 이동 C++ 7562 나이트의 이동 1. 문제 https://www.acmicpc.net/problem/7562 2. 풀이 dfs가 아닌 bfs를 이용한다. bfs를 활용했을 때 목적지에 도착했을 당시 최소 이동 횟수이기 때문이다. dfs는 목적지에 도착했을 때 최소 이동 횟수가 아니기 때문이다. 최소 이동 횟수를 구할 때는 bfs로 구해야 할 것같다.(내 생각) 배열 arr은 출발지로부터 해당 좌표(i, j)까지의 최소 이동 횟수를 담아 놓은 것이다. bfs방식으로 큐를 이용하여 출발 좌표부터 탐색을 시작하고 출발지 좌표가 나오면 그 때 arr배열의 값을 출력해주고 탈출하면 된다. 테스트케이스도 입력을 받으니 테스트케이스를 하나 실행할때 ..

0. 제목 백준 2252 줄 세우기 BOJ 2252 줄 세우기 C++ 2252 줄 세우기 1. 문제 https://www.acmicpc.net/problem/2252 2. 풀이 Topological Sort(위상 정렬)을 사용하는 문제이다. 위상 정렬은 indegree 즉, 자신에게 들어오는 노드 수를 계산하고 indegree가 0이 되면 먼저 정렬해 주는 것이다. 위상 정렬의 특징 중 하나는 사이클이 생기면 안된다는 것이다. indegree가 모두 0보다 크면 사이클이 생긴다는 의미이다. 따라서 위상 정렬은 indegree가 0인 것이 하나 이상 존재할 때 가능하다. 이 문제에서 1 3 이 주어졌을 때 1 다음에 3이 줄을 서야 한다. 방향을 나타내면 1 -> 3 으로 나타낼 수 있고 이 상황에서 3의..

0. 제목 백준 9935 문자열 폭발 BOJ 9935 문자열 폭발 C++ 9935 문자열 폭발 1. 문제 https://www.acmicpc.net/problem/9935 2. 풀이 입력 문자열의 길이가 1000000까지 될 수 있기 때문에 O(N)으로 탐색을 해야 시간 내에 통과할 수 있다. 처음부터 탐색하는 것을 반복하면 시간이 오래 걸리기 때문에 처음부터 비교해가면서 즉각 제거 하는 방식으로 풀어야 한다. 예를 들어보겠다. 문자열 abcde가 주어지고 폭발 문자열로 cd가 주어졌다고 하자. 문자열이 폭발 문자열의 마지막 문자인 d와 같을 때 역으로 비교해주어야 한다. result라는 배열은 폭발하지 않는 문자열을 담는 배열이다. 문자열에서 d가 나오는 순간 문자열의 d 전에 나오는 문자가 c인지 확..

0. 제목 백준 1717 집합의 표현 BOJ 1717 집합의 표현 C++ 1717 집합의 표현 1. 문제 https://www.acmicpc.net/problem/1717 2. 풀이 Union-Find방식을 사용하는 문제이다. Find를 통해 root를 찾아주고 Union을 통해 합쳐준다. union은 merge로 구현하였다. 0과 1이 입력되는 케이스를 구분하여 적절히 find, union을 수행해주면 된다. 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 34 35 36 37 38 39 40 41 42 43 44 #include using namespace std; int par..