반응형 Programming400 [C/C++] 백준 #2580 스도쿠 (백트래킹) 스도쿠는 머리를 많이 사용하는 퍼즐로 유명합니다. 기본적으로 문제를 풀기 위해서 여러가지 경우를 머리속에 담고서 진행해야 하기 때문에 쉽게 풀지를 못 하지만, 컴퓨터 프로그램의 경우는 모든 경우를 살펴볼 수 있는 알고리즘 중 대표적인 백트래킹으로 이 문제를 손쉽게 풀 수 있습니다. 대중교통을 이용해서 여행을 다닐 때, 버스 터미널 등에서 손쉽게 살 수 있는 스도쿠 문제지가 있었죠. 지금은 귀찮아서라도 잘 안 풀게 되지만요. 백준 사이트에서 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각.. 2023. 12. 5. [C/C++] 백준 #2579 계단 오르기(동적 계획법) 계단 오르기 조건들이 주어지면서, 계단에 적힌 값을 최대, 또는 최소가 되도록 하는 문제들이 꽤 많습니다. 보편적으로 이러한 문제들은 동적 계획법을 이용해서 풀 수 있습니다. 백준 사이트에서 주어진 문제 링크입니다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르기의 조건은 1) 한계단 내지 두계단을 밟을 수 있다. 2) 연속된 3개의 계단을 밟을 수 없다. 3) 도착 계단을 반드시 밟아야 한다. 입니다. 이것을 동적 계획법으로 풀기 위해서는 최.. 2023. 11. 9. [C/C++] 백준 #2578 빙고(구현) 이번 문제는 알고리즘적으로 특별한 것이 없고, 스도쿠, 노노그램 등에서 사용할만한 기법을 소개하도록 하겠습니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 이러한 문제를 풀 때에는 플래그를 사용하면 편합니다. 플래그를 이용해서 현재의 상황을 요약을 하는 기술입니다. 빙고의 각 줄과 각 열, 두개의 대각선을 각각 하나의 플래그로 놓고서, 몇개가 맞는지 계속 기록하는 방식입니다. (r, c) 위치가 맞았다고 한다면, rowC.. 2023. 8. 18. [C/C++] 백준 #2573 빙산(깊이 우선 탐색) 이번 문제는 보다 좋은 알고리즘을 택하기 보다는 구현을 위주로 하였습니다. 깊이 우선 탐색은 섬의 개수가 몇개인지 판단하기 위해서 사용을 하였습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제는 빙하가 같은 높이만큼 녹을 때, 한덩어리의 빙하가 두덩어리 이상이 되는 최소 녹는 높이를 구하는 것입니다. 구현 자체는 간단합니다. 빙하가 녹는 높이에 따라서 빙하가 두개가 될 때의 높이를 출력하게 하였습니다. 제가 구.. 2023. 7. 30. [C/C++] 백준 #2567 색종이-2(구현) 이번 문제는 색종이를 붙였을 때, 차지하는 둘레를 구하는 것으로 구현을 하면 됩니다. https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 색종이를 아무 방향이나 붙인다면 아주 어려운 문제가 되겠지만, 축에 평행하게만 붙이고 눈금에 맞추어 붙이기 때문에 색칠하기 문제로 전환해서 풀 수 있습니다. 색종이를 붙일 판을 배열로 설정하고, 색종이를 붙이면 그 영역만큼 색칠하면 됩니다. 물론 트리형태로 만들면 더 빠른 속도로 색칠할 수 있겠지만, 여기서는.. 2023. 7. 23. [C/C++] 백준 #2565 전깃줄(가장 긴 증가하는 부분수열) 이번 문제는 백준내에서도 아주 자주 나오는 가장 긴 증가하는 부분수열(LIS; Longest Incremental Sub-sequence) 문제입니다. 전깃줄이 꼬이지 않게 배열하기 위해서 몇개의 전깃줄을 없애야 하는 문제입니다. https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 그동안 제가 작성했던 가장 긴 증가하는 부분 수열 문제들을 모아두면 다음과 같습니다. https://sdev.tistory.com/1384 https://sdev.tistory.. 2023. 7. 19. 이전 1 2 3 4 5 ··· 67 다음 728x90
