댕우의 개발 일지

대각 공식을 몰라 애먹은 문제.. 남겨두고 다시 풀어보면 좋을 것 같아서 포스팅합니다! https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹으로 풀어야 한다는걸 알면서도 대각체크를 어떻게 해줘야할지 몰라 해설을 보고 풀었습니다. 스스로 푼게 아니기에 또 까먹을까봐 블로그 포스팅을 남기고 추후에 제가 보고 쉽게 이해하기 바라며 포스팅합니다! 우선 이 문제를 보고 처음 풀이 접근 방법을 떠올려보자면 많은 사람들이 이렇게 추측하겠죠! 퀸은 가로로 또는 세로로 공..

백트래킹을 공부하면서 다시 한 번 풀어보는 문제입니다. 아직 백트래킹이 머리로는 이해 되는데 구현할 땐 헷갈려서 블로그 포스팅을 통해 저도 더 자세히 풀어 쓰면서 습득하고 보시는 분들도 이해되시길 바라며 작성하겠습니다! https://www.acmicpc.net/status?from_mine=1&problem_id=15649&user_id=sangu522 채점 현황 www.acmicpc.net 이게 제가 처음에 DFS인 줄 알고 풀었는데 백트래킹 문제인가봐요! 백준 알고리즘 분류에도 백트래킹이고 백트래킹을 공부하면서 예제로 나와서 다시 풀게 됐거든요.. 그래서 백트래킹과 DFS의 차이를 확실히 알기위해 검색해봤어요. DFS: 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로를 순회한다. ..

이번엔 백준 1697번 문제 숨바꼭질을 풀어보겠습니다. https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS로 풀어야 한단것을 안다면 그렇게 어려운 문제 같진 않은데 정답 비율이 생각보다 낮네요. 일반적으로 BFS문제는 2차원 배열에서 최단거리를 찾는 문제가 많았습니다. 근데 이번 문제는 2차원 배열이 보이지 않아 BFS인지 잘 모를 수 있는데요! 2차원 배열에서 상 하 좌 우로 최단거리를 체크하듯이 여기서는 x-1..

코딩테스트를 준비해야하는 시기라서 매일 여러 문제를 풀고 있는데요! 이 문제는 블로그 포스팅해두면 저도 보고 다른 분들도 도움 받을 수 있겠다 생각해서 작성해보려고합니다! https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 네 이런 문제이구요 BFS로 해결할 수 있는 문제입니다. 지훈이가 탈출할 수 있는 최단시간(경로)을 구하는 문제이니까요! 그런데 여기서 주의할 점은 불의 최단시간(경로)도 구해야한다는 겁니다! 지훈이도 탈출하려할..