프로그래밍 공부

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 언어 : C++17 환경 : VSCode gcc 8.1.0 아이디어 BFS를 활용하여 해결할 수 있을 거 같아서 BFS를 사용해서 해결했다 처음에는 모든 점에 대해서 BFS를 할까 생각했으나 잘 생각해보니 서로 다른 값을 가진 한 개의 인덱스에서 BFS를 돌린 후 배열이 같지 않다면 백신일 가능성이 없으니 서로 다른 값을 가진 한 개의 인덱스에 대해서만 ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 언어 : C++17 환경 : VSCode gcc 8.1.0 1697번 숨바꼭질과 비슷하다 하지만 여기서는 순간이동을 할 때는 0초 만에 이동하기 때문에 현재 dist의 내용에서 +1을 하지 않고 계속 BFS를 돌려주면 된다. 이때 순간이동이 이동시간이 더 빠르기 때문에 순간이동부터 먼저 계산해준다. 코드 #include using namespace std; int..

https://www.acmicpc.net/problem/15921 15921번: 수찬은 마린보이야!! 기댓값 E(X)의 정의는 ‘각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값’이다. 다시 말해, 어떤 수 x가 수열에 등장할 확률 P(x) = (x의 등장 횟수) / www.acmicpc.net 언어 : C++14 환경 : Visual Studio 2019 이 문제를 푸는 방법은 2가지가 있다 하나는 문제의 힌트를 사용해서 또는 평균값과 기댓값은 일반적으로 같다는 것을 이용하는 방법. 문제의 힌트를 사용해서 일일이 계산을 해주는 방법. #include using namespace std; struct Record { // 점수를 저장할 구조체 double s..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 언어 : C++14 환경 : ideone.com - https://ideone.com Parametric Search를 이용한 문제입니다. 아이디어는 입력받는 값 중 최솟값은 1, 최댓값을 end 변수에 넣고 중앙값을 구해준 다음 배열의 원소를 중앙값으로 나눈 값을 cnt 변수에 더해줘서 몇 개의 랜선을 만들 수 있는지 계산했다. cnt 값이 n값 즉 필요한 랜선의 개..

https://www.acmicpc.net/problem/1547 1547번: 공 첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것 www.acmicpc.net 언어 : C++14 환경 : Visual Studio 2019 간단한 구현 문제입니다. 배열의 인덱스를 컵의 위치, 값을 컵의 번호로 생각하고 풀었습니다. 아이디어는 x, y를 입력받고 그 값을 이용해서 바꿔줘야 할 컵의 위치를 구한 후 서로 바꿔주었습니다. 이때 공은 움직이지 않는다는 말이 있는데 그 말은 계산이 끝난 후 0번 인덱스를 출력하면 된다고 판단했습니다. 코드 #include us..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 언어 : C++ 환경 : Visual Studio 2019 이 문제는 BFS나 DFS로 풀 수 있는 있는 문제입니다. 설명은 코드에 주석으로 달려있습니다. BFS 풀이 #include #include #include #include #include using namespace std; #define X first #define Y second int dx[4] = { 1,0,-1,0 }; // 아래..