본문 바로가기

백트래킹(퇴각검색)10

[Programmers] 피로도 https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 최소 필요 피로도 또는 소모 피로도로 정렬을 통해 해결할 수 있는 방법이 마땅히 떠오르지 않고 던전 수가 크지 않으므로, 백트래킹(bactracking, 퇴각검색) 알고리즘에 기반하여 문제를 해결하고자 했다. 구현 백트래킹에 기반하여 문제를 해결하기 위해 던전의 방문 여부를 표시할 배열(played[])을 별도로 선언하여 활용하였다. [스포 주의] 아래 '더보기'를 누르면 코.. 2023. 12. 21.
[Programmers] N-Queen https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 체스판 내에서의 퀸의 이동 법칙에 따라 한 줄마다 하나의 퀸만 놓을 수 있으므로, 가장 위쪽 줄부터 시작하여 아래쪽으로 한 줄씩 퀸을 순차적으로 배치하여 문제를 해결할 수 있다. 이때, 각 줄마다 퀸을 배치할 수 있는 칸이 있는지 확인하여 배치할 수 있는 경우에는 퀸을 배치, 그렇지 않은 경우에는 현재 줄에서 배치한 퀸을 다시 회수하고 이전 단계로 되돌아가는 백트래킹(back.. 2023. 12. 12.
[Baekjoon] 2580번: 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 빈 칸에 들어갈 숫자를 구하는 과정까지는 빠르게 구현했는데, 백트래킹 알고리즘 구현에서 빈 칸에 들어갈 숫자를 실시간으로 구해서 대입했어야 하는데 그 부분을 실수해서 디버깅에 한참을 소비하고 말았당 문제 해결 과정 착안 빈 칸으로 표시된 칸마다 재귀적으로 현재 칸에 넣을 수 있는 숫자를 넣고, 넣을 수 있는 숫자가 없는 경우에는 이전 단계로 돌아가 다른 숫자를 넣도록 하는 백트래킹 알고리즘을 통해.. 2023. 12. 11.
[Baekjoon] 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 과정 착안 주어지는 연구소 모양에 대하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 빈 공간에 벽 3개를 세우면서, 바이러스 확산 예상 결과를 너비 우선 탐색(breadth-first search, BFS)을 통해 구하고자 하였다. 구현 편의상 벽의 개수를 파악하기 쉽도록 세우고자 하는 벽의 번호를 3, 4, 5로 정하여 프로그래밍 하였다. 한편 백트래킹 알고리즘에 기반하여 너비 .. 2023. 8. 15.
[Baekjoon] 14889번: 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 해결 과정 착안 총 $N$ 명의 인원을 $(N / 2)$ 명씩 두 팀으로 나누는 모든 방법에 대하여, 능력치 값을 계산해보고 능력치 차이의 최솟값을 구하고자 하였다. 이때 팀 이름에 관계 없이 점수 차이만 계산하면 되므로, 중복하여 계산할 필요 없이 가장 처음 번호의 인원(1번 사람)은 반드시 첫 번째 팀에 포함된다고 가정할 수 있다(예를 들면 1번 사람이 속한 팀을 무조건 스타트 팀이라고 가정하는 것과 같음)... 2023. 7. 2.
[Baekjoon] 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 과정 착안 백트래킹(backtracking, 퇴각검색) 알고리즘에 대한 대표적인 문제이나, 직접 풀어보는 건 처음이라 백트래킹이 아직 익숙하지 않아서 착안이 어려웠다. 생각해내기 가장 어려웠던 부분은 단계별로 배치되는 퀸에 의해 8 방향 직선으로 가려지는 체스판 상의 위치를 어떻게 표시해야 문제를 쉽게 해결할 지를 생각해내는 것이었다. 그래서 처음에는 체스판을 계속 새로 만들고 퀸의 위치마다 직선 방향.. 2023. 6. 16.

티스토리툴바