본문 바로가기

분류 전체보기166

[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.
[Programmers] 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 요구하는 결과값이 최소 신장 트리(minimum spanning tree)의 간선의 가중치의 총합이므로, 최소 신장 트리 알고리즘을 활용하여 문제를 해결하고자 하였다. 구현 간선 데이터가 주어지므로, 유니온-파인드(union-find) 연산을 구현한 다음 크루스칼 알고리즘(Kruskal's algorithm)을 통해 최소 신장 트리를 만들어 가중치의 총합을 구하였다... 2023. 12. 11.
[Baekjoon] 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 해결 과정 착안 $N^2$ 개의 동전의 초기 상태로부터 뒷면(T)인 동전의 갯수가 최소가 되도록 행 또는 열을 뒤집는 경우를 찾기 위해서는 가능한 모든 경우를 확인해보아야 한다. 이때, 행이나 열을 뒤집는 동작을 수행할 때 선택된 행과 열 중에서 어느 것을 먼저 뒤집더라도 결과가 동일하므로, 편의상 항상 행을 먼저 다 뒤집은 다음에 열을 뒤집는 경우만 살펴볼 수 있다. 행 또는 열을 뒤집.. 2023. 12. 9.
[Programmers] 마법의 엘리베이터 https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 10의 거듭제곱에 해당하는 만큼씩 층을 올라가거나 내려갈 수 있으므로 0층에 도착하기 위해 모든 자릿수의 숫자를 0으로 만들도록 이동하며, 이때 이동 횟수를 줄이기 위해 각 자릿수 별로 층을 오르는 것과 내려가는 것 중에서 어느 것이 유리한지를 판단하면 문제를 해결할 수 있다. 단, 자릿수 별로 이동할 때 층을 올라가서 해당 자릿수를 0으로 만드는 경우는 현재 자릿수보다 큰.. 2023. 12. 8.
[Baekjoon] 9084번: 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 서로 다른 $n$ 가지 동전의 가치를 $c_1, c_2, \cdots, c_n$, 특정한 금액 $m$을 만들기 위한 경우의 수는 1) $c_1$ 짜리 동전만 사용하여 만드는 경우 (가능하다면) 2) $c_2$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) 3) $c_3$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) $\cdo.. 2023. 12. 7.

티스토리툴바