Coding_Test_C++
BaekJoon 1389번: 케빈 베이컨의 6단계 법칙(C++)
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이법 1) DFS를 활용하여 최소를 구하는 문제이다. 2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다. 3) sort를 활용하여 비교를 진행하여 케빈 베이컨의 수가 가장 작은 사람을 출력 시에 가장 작은 값이 여러 명일 경우에는 번호가 가장 작은 사람을 출력하였다. 4) tmpt 배열을 통해 시..
BaekJoon 11724번: 연결 요소의 개수(C++)
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이법 1) DFS를 활용하면 쉽게 풀 수 있는 문제이다 2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다. 3) 연결된 Node가 총 몇 덩이인지 파악하기 위해 cnt 변수를 두어 개수를 셀 수 있게 하였다. #include #include #include #include #incl..
LeetCode 1669번: Merge In Between Linked Lists(Python3)
https://leetcode.com/problems/merge-in-between-linked-lists/ Merge In Between Linked Lists - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 해당 문제는 위 링크를 클릭하면 볼 수 있다. 문제 설명 1) 사이즈가 n인 list1과 사이즈가 m인 list2가 주어진다. 2) list1의 a번째 node부터 list1의 b번째 node까지를 제거한다. 3) list1의 a-1번째 node 이후에..
BaekJoon 2644번: 촌수계산(C++/DFS/BFS)
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 풀이법 1) BFS와 DFS를 이용하면 쉽게 풀 수 있는 문제이다. 2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다. #include #include #include #include #include #include using namespace std; int n; int a, b; int m; int arr[101][101]; b..
BaekJoon 7562번: 나이트의 이동(C++)
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이법 1) BFS를 이용하여 최단 거리를 구하는 문제이다. 2) 여러 개의 test case가 있다는 점을 유의한다면 쉽게 풀 수 있는 문제이다 3) 매 test case 마다 visited를 초기화 하는 것을 잊지 말자. 4) 나이트가 움직일 수 있는 총 8개의 패턴을 배열로 만들어 둔다면 직관적인 코드를 짤 수 있다. #include #include #include #include #inclu..
BaekJoon: 7569번 토마토(C++)
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이법 1) BFS를 활용하여 최단거리를 찾는 문제이다. 2) x,y,z를 둘 때 값이 헷갈릴 수 있으니 이 부분을 조심해야 한다. 필자의 경우 아래와 같은 방식으로 x,y,z 값을 두었다. (0,0,0) (0,1,0) (0,2,0) (1,0,0) (1,1,0) (1,2,0) 3) tomato 배열 내에 0이 남아있는지 확인하는 별도의 함수를 활용하여 익지 못한 토마토를 찾..
BaekJoon 1012번: 유기농 배추(C++ DFS/BFS)
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이법 1) DFS와 BFS를 이용해서 풀 수 있는 문제이다. 2) 최소의 벌레의 개수를 찾아야 하니, visited 배열을 이용한다면 쉽게 문제를 해결할 수 있다. 3) 한번 방문한 노드를 다시 방문하지 않으므로 시간 복잡도는 O(nm)이 될 것이다 재귀를 이용한 DFS를 이용한 풀이 #include #include #include #include using namespace std; int t; int a..
BaekJoon 2667번: 단지번호붙이기(C++)
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) DFS와 BFS 어떤 걸로 풀어도 성공할 수 있는 문제이다. 연결되어 있는 것이 있는지가 핵심이고, 공부를 위해 둘다 구현해 보는 것을 추천한다 2) 구현에 어려움이 있는 문제기 보다는, 빠르게 이게 무슨 문제구나를 파악하는 것이 중요한 문제이다. 3) BFS와 DFS의 개념에 대해 알고 있다면, 구현 시에 BFS..
LeetCode 1368번: Minimum Cost to Make at Least One Vaild Path in a Grid(C++)
leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/ Minimum Cost to Make at Least One Valid Path in a Grid - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 해당 문제는 위 링크를 클릭하면 볼 수 있다. 문제 설명 1) m x n의 grid 배열이 주어진다. 해당 grid는 다음 내가 방문해야 할 cell을 가르키고 있다. 2) 각 ..
BaekJoon 1260: DFS와 BFS (C++)
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 및 장단점 1) DFS -장점: 현 경로 상의 노드를 기억하기 때문에, 적은 메모리를 사용한다. -장점: 찾으려는 노드가 리프에 가까울 수록 BFS보다 빠르게 찾을 수 있다. -단점: 해가 없는 경로를 탐색할 경우 단계가 끝날 때 까지 탐색하기에 최단 경로라는 보장이 없다. 2) BFS -장점:..