백트래킹 알고리즘3 [Algorithm] 백준 2580 스도쿠 Node.js 스도쿠는 18세기 스위스의 수학자 레온하르트 오일러가 창안한 라틴방진(Latin Square)를 기초로 합니다. 미국의 건축가 하워드 간즈(Howard Garns)가 넘버플레이스라는 이름으로 1979년 소개했습니다. 대중화 된 계기는 1984년 일본 니코리사 에서 스도쿠라는 이름을 붙여 판매하면서 알려지기 시작했습니다. 스도쿠를 푸는 방법은 간단합니다. 3가지 규칙에 부합하는 숫자를 찾아 빈칸에 입력하면 됩니다. 가로줄 중 1~9가 중복없이 들어가야 합니다. 세로줄 중 1~9가 중복없이 들어가야 합니다. 3x3 칸 중 1~9가 중복없이 들어가야 합니다. 백준 2580 스도쿠 문제 문제 스도쿠 문제를 푼 최종 모습을 출력하세요 입/출력 입력 아홉줄에 걸쳐 한줄에 9개씩 숫자가 입력됩니다. 숫자가 채워져야 .. 2022. 7. 18. [Backtracking] 백준 15651 N과 M 3단계 Node.js 구현하기 문제 문제링크 백준 15651 N과 M 3단계 이전 백트래킹 문제의 경우 중복되는 경우의 수를 모두 제거했지만, 이번 문제는 주옥을 허용한 모든 경우의 수를 표현합니다. 백트래킹은 DFS와 BFS 알고리즘과 같이 트리 구조상에 위치한 데이터를 검색할 수 있는 알고리즘입니다. 만약 특정 조건을 만족하는 경우 상위 노드로 이동하면서 검색을 계속 진행하게 됩니다. 백준 15651 문제의 경우 트리 구조의 모든 노드를 탐색한 완전탐색 백트래킹 알고리즘을 사용합니다. 추가적으로 문제를 제출할 때 배열의 요소별로 출력을 진행하면 시간초과 오류가 뜨게 됩니다. JAVA에서는 StringBuilder를 사용해서 출력하지만 Node.js 환경에서는 string에 담아 한번에 출력해줘야 시간초과 오류를 해결하게 됩니다. .. 2022. 6. 12. [Algorithm] 백준 15649, 15650 JS 구현 ( 백트래킹 DFS 차이 ) 백트래킹 알고리즘 백준 15649 N과 M 문제 링크 https://www.acmicpc.net/problem/15649 백트래킹을 이해하는 기본적인 알고리즘이다. 백트래킹 알고리즘이란 모든 경우의 수를 모두 고려하는 알고리즘이다. 문제를 트리 구조로 표현할 때 적합한 방식이다. 구현하는 방식에 따라 DFS, BFS로 구분될 수 있다. 문제에서 출력값을 사전 순으로 출력해야 하기에 BFS보다는 DFS 알고리즘을 사용하는게 맞다. DFS 알고리즘과 백트래킹의 차이점은 DFS는 리프노드까지 무조건 탐색을 진행하지만 백트래킹은 특정 조건값을 통해 복귀 로직이 포함된다. DFS는 루트 노드에서 리프 노드까지 한번에 내려가는 방식이다. 예를 들어 미로 길 찾기 문제에서 막다른길 까지 도달한 후 길이 막히는 경우 .. 2022. 6. 11. 이전 1 다음
