백준 문제풀이(16)
-
백준 #1992 쿼드트리
백준 1992번 쿼드 트리 문제이다. 그래프를 활용한 문제로, 재귀를 이용하면 해결할 수 있는 문제이다. 처음 문제를 보면 문제가 잘 이해가 가지 않는데, 위에 그림으로 준 예시와, 예제를 잘 들여다 보면 쉽게 파악할 수 있다. 정사각형을 한 뭉텅이로 보고 문제 해결을 시도하면 된다. 첫 번째 입력에서 전체 행의 개수를 주기 때문에, 행의 개수를 점차 적으로 줄여나가면서 문제를 해결할 수 있다. #include #include using namespace std; int n; string s; char a[101][101]; string quard(int y, int x, int size ){ if(size == 1) return string(1,a[y][x]); char b = a[y][x]; stri..
2022.01.15 -
#1697 백준 숨바꼭질 코드 C++
1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 백준 1697번 숨바꼭질 문제이다. 백준에는 숨바꼭질 시리즈의 문제가 많은데, 이전 문제는 그리디, DP등 다양한 알고리즘으로 해결이 가능했다. 이 문제 역시 여러 해결 방안이 있지만 타겟 알고리즘은 너비우선탐색(BFS)이다. 문제에서 주어진 예시를 보면 수빈이의 위치는 5이고 동생의 위치는 17이다. 수빈이는 1초후에 위치-1, 위치+1, 위치*2 의 위치로 이동할 수 있다. 5의 경우, 4, 6, 10 으로 이동할 수 있는 것이다...
2021.07.20 -
#7662 백준 이중 우선순위 큐 C++
백준 7662 번 이중 우선순위 큐 문제이다. 우선순위 큐의 성질을 문제에 적용시킨 것인데, 우선순위 큐와 다른 것은 가장 큰 값과, 가장 작은 값이 모두 손쉽게 삭제가 가능 하다는 점이다. 이 문제에서 주어지는 k값의 범위가 10000정도만 되어도 list를 고려해 볼 수 있었지만, 범위가 넓은 관계로 다른 컨테이너를 사용해야한다. 여기서 사용할 수 있는 컨테이너는 map과 multiset을 사용할 수 있다. map을 사용하면, 첫 번째 인자는 값 자체를 넣어주고, 두 번째 인자는 값의 개수로 설정해서 동일한 key값이 삭제될 경우 두 번째 인자의 값을 줄이는 식의 풀이를 할 수 있다. multiset을 사용하면 key값의 개수를 일일이 줄여줄 필요가 없기 때문에 map으로 구현하는 것 보다 쉽게 구현..
2021.07.20 -
백준 #17087 숨바꼭질6 문제 풀이 C++
백준 17087 숨바꼭질 6, 실버 1 문제이다. 문제의 기본적인 이해는 금방되리라 생각한다. X-D와 X+D의 위치로 이동할 수 있고, D를 구하는 문제이다. 첫 번째 예제를 보면 위치 3에서 위치 1로 이동하려면 2만큼의 이동이 필요하고 1에서 7로 이동하려면 6만큼의 이동이 필요하다 또한 위치 7에서 위치 11로 이동하려면 4만큼의 이동이 필요하다. 수빈이는 1초마다 같은 거리를 움직여야 하기 때문에 한점에서 다른 한점으로 이동한 거리는 모두 가장 작은 이동거리의 배수일 수 밖에 없다. 그렇기 때문에 이동한 거리들의 최대공약수를 구하면 그것이 바로 정답이 된다. 처음에 문제를 풀때는 단순히 수빈이의 위치와 동생의 위치 차의 절댓값 중에서 가장 작은 값을 출력했는데, 이 풀이 방법이 잘 못된 이유는 ..
2021.05.24 -
백준 #2675 문자열 반복 c, python
백준 2675번 문자열 반복 문제이다 뭐 별로 어렵지도 않은 문제라고 생각할 수 있다.(실제로도 그렇다) 이 문제를 소개하는 이유는 파이썬의 장점을 부각함과 동시에 C의 불편함을 소개하고 싶어서이다. 아래 코드를 보자. #include #include int main() { int numOfTestCase = 0; int lenOfString = 0; char string[20] = {0}; scanf("%d", &numOfTestCase); for(int i = 0; i < numOfTestCase; i++) { scanf("%d %s", &lenOfString, string); for(int j =0; j < strlen(string); j++) { for(int k = 0; k < lenOfStri..
2021.05.10 -
백준 #1158 요세푸스 문제 c++
백준 1158번 요세푸스 문제이다. 이 문제는 이해하기만 하면 원형큐를 활용해서 구현하는데는 크게 어렵지 않다. 7 3을 입력 받았다면 1 2 3 4 5 6 7 에서 항상 세번째 숫자를 제거하는 것이다. 원형큐이기 때문에 세번째 숫자인 3을 제거하면 다음에 오는 세번째 숫자는 4 5 6 7 1 2 중에서 6이 될것이고 6이 제거된 그 다음에는 7 1 2 4 5 중에서는 2가 될것이다. 위의 과정을 큐가 빌때까지 진행하면 된다. 아래는 C++로 구현한 코드 전문이다. #include #include using namespace std; queue q; queue temp; int main() { int n; int k; scanf("%d %d", &n, &k); for(int i = 1; i
2021.05.03