반응형 분류 전체보기584 [C/C++] 백준 #2589 보물섬(너비 우선 탐색) 이번 문제는 너비 우선 탐색을 이용해서 풀었습니다. 플로이드 워샬을 이용해서 풀 수도 있겠지만, 모든 노드가 다 이어진 것이 아니기 때문에 같은 알고리즘 효율이라는 관점에서 너비 우선 탐색을 이용했습니다. https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제는 섬안에서 최단거리로 가장 먼 두 점을 찾는 것입니다. 한칸의 거리가 모두 같기 때문에 다익스트라 알고리즘을 사용하지 않고, 너비 우선 탐색을 통해서도 충분합니다. 너비 우선 탐색의 깊이가 가.. 2024. 1. 22. [C/C++] #2583 영역 구하기(깊이 우선 탐색) 이번 문제는 복합 문제입니다. 색종이 붙이기 문제와, 섬의 갯수 구하기 문제가 결합된 문제라고 생각하시면 편합니다. https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 색종이 붙이기 문제는 캔버스를 생성한다음, 색칠하기만을 하시면 됩니다. \(O(MNK)\) 알고리즘이긴 하지만, 조금 더 개선을 하시면, \(O(MN+K)\) 알고리즘으로도 하실 수 있습니다. https://sdev.tistory.com/1547 [C/C++] 백.. 2024. 1. 2. [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. 이전 1 ··· 11 12 13 14 15 16 17 ··· 98 다음 728x90
