wonseok.log wonseok.log

백트래킹

• [Programmers] Lv2. N-Queen(kotlin)

  SW Test/Programmers 2022. 7. 26. 19:08

  문제 예시 풀이 N-Queen은 백트래킹의 대표적인 문제로 y축을 하나씩 내려가면서 x축을 한번 순회하여 Queen이 놓아질 수 있는 곳을 찾는 문제입니다. 하나씩 탐색하면서 찾아도 되지만 수학적으로 좌표를 활용하여 문제를 풀면 빠르게 풀 수 있습니다. 대각선끼리도 같은 라인에 Queen이 있으면 안되는데 좌표의 기울기나 규칙을 통해서 같은 대각선인지 아닌지 알 수 있습니다. 오른쪽 아래로 향하는 대각선에서 y-x 값이 동일한 좌표는 같은 대각선 상에 존재합니다. 마찬가지로 왼쪽 아래로 향하는 대각선끼리는 y+x 값이 동일합니다. 따라서 y좌표는 하나씩 내려가면서 x좌표만 0부터 n-1까지 순회하여 dlist (down list), rdlist(right down list) , ldlist(left do..

  Read More
• [BaekJoon] 15649번 : N과 M

  SW Test/BaekJoon 2020. 12. 14. 22:36

  이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 간단하게 백트래킹을 생각해서 풀었지만 뜬금없는 곳에서 시간초과가 났다. 출력하는 부분에서 endl과 \n의 시간차이로 인한 문제였다. endl는 출력버퍼를 비우는 과정(flush)로 인해 \n과 차이가 발생합니다. #include using namespace std; void sequence(bool check[10],int vec[10],int cnt, int n, int m){ if(cnt == m){ for(int i=0;i

  Read More
• [Programmers] Lv3. N-Queen

  SW Test/Programmers 2020. 9. 7. 03:41

  이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.

  Read More