Algorithm/백준22 7562 나이트의 이동 (C++) BFS로 풀면되는 문제였다. 그.. 근데 조금 다른거라면, 종료되는 조건이 있다라는 것이다. 보통의 BFS 문제들은 미로통과하기, 다 채워질때의 최솟값 등을 물어보는데, 이건 목적지가 정해져 있고, 나이트가 그 지점으로 이동했을 경우의 수를 리턴하는 문제였다. 구조는 기존의 BFS 문제와 같다. 조건문만 추가 해주고 리턴할 수 있게 해주면 된다. (함수로 나누지 않았다. 일단 구현이 먼저라고 생각해서.. 나중에 시간이 된다면 나누는 작업을 진행하겠다. 코드에 나오는 X,Y 는 pair의 기능인 first, second 의 단축어이다. #define으로 설정해놨으니 헷갈리지 말길 바란다. 그리고 pair에 추가하는 x,y 좌표는 솔직히 x를 먼저 추가하든 y를 먼저 추가하든 상관없는 것 같다. 일단 내가 .. 2021. 4. 25. 2583. 영역 구하기 (C++) www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 전형적인 BFS구현 문제였다. 문제를 한줄로 요약하자면 이거다. 모눈종이에 직사각형이 그려진다. 그려진 직사각형 이외에 박스들이 몇개, 크기가 어떤지를 출력하면 되는 문제다. 각 배열을 돌아가며 그려진 직사각형 이외에 곳을 발견하면 박스 카운트를 추가하고 BFS를 돌리며 크기를 잰다. 아, 그리고 입력에 각 왼쪽 아래 꼭짓점 좌표와 오른쪽 위 꼭짓점 좌표를 주는데, 그 좌표를 이용하여 배열에.. 2021. 4. 23. 1074. Z (C++) Z 시간 제한메모리 제한제출정답맞은 사람정답 비율 0.5 초 (추가 시간 없음) 512 MB 29008 9427 7002 36.800% 문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을.. 2021. 4. 21. 11729. 하노이 탑 이동 순서 (C++) 문제는 딱히 모르겠고, 하노이 탑은 너무나 유명해서 모두가 잘 알거라고 생각한다. 하노이 탑은 재귀적으로 푸는 문제들 중 가장 유명하다고 생각한다. 근데 유명한데 그 만큼 어려운 듯 싶다. (물론 내 기준이다.) (알린이..) 하노이탑의 옮기는 구조를 생각해보자. n-1개의 원판을 기둥 1에서 기둥 2로 옮긴다. n번 원판을 기둥 1에서 기둥 3으로 옮긴다. n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다. -> 원판이 n-1개일 때 옮길 수 있으면 원판이 n개 일때에도 옮길 수 있다. (기존의 뇌 구조를 파괴한다.) 원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다. 원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다. 라는 결론에 도달해 재귀를 이용하여 문제를 풀 수 .. 2021. 4. 21. 1629. 곱셈(C++) 재귀를 이용하여 푸는 문제다. 처음에는 정말 어려웠다. 우리가 아는 상식대로 그냥 제곱해서 풀면 안됨? 이라면서 그냥 풀어보려고 했으나.. 수의 크기가 어마어마 해서 그걸로는 턱없이 부족했다. 강의에서 문제를 푸는 사고를 설명해줬다. a^n * a^n = a^2n 이다. (??????????????) (뭐 어쩌라고) 그러니까 그 다음 공식을 보면 굳이 주어진 식 그대로 풀지 않고서도 반으로 나누어서 푸는 식으로도 문제의 답을 구할 수 있다라는 의미이다. 그 아래의 1번 도미노가 쓰러진다. 그러면 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다라는 공식이 성립이 된다라는 뜻이다. 그럼 1승을 계산할 수 있다라는건, k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다라는 결과에 도달한다. 이.. 2021. 4. 21. 2178. 미로 탐색 (C++) 개인적으로는 이 문제가 그림 문제보다 쉬웠다. 미로의 최소칸 수를 구하는 문제다. BFS를 이용하여 지나간 곳이 아니거나 0이 아닌곳만 열심히 이동하다보면 나오는 문제다. #include using namespace std; #define X first #define Y second string board[102]; int dist[102][102]; int n,m; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > board[i]; } for(int i = 0; i < n; i++) fil.. 2021. 4. 18. 이전 1 2 3 4 다음 IT_learning's Commit
