반응형 Programming399 [C/C++] 백준 #2607 비슷한 단어(구현) 이번 문제는 문제의 뜻을 잘 이해할 필요가 있습니다. 같은 구성이라는 것은 문자의 종류와 그 개수가 동일한 경우를 말합니다. GOD와 DOG는 문자의 종류와 그 개수가 동일하기 때문에 같은 구성이 됩니다. 그런데 비슷한 단어는 문자를 하나 추가하거나 뺌으로써 같은 구성이 되는 단어를 뜻합니다. 순서와는 상관없다는 것이죠. DOG와 GOOD는 비슷한 단어가 됩니다. 이것만 잘 이해하시면 문제를 푸는데 있어서 어려움은 없습니다. 난이도는 현재 실버 2등급 문제이지만, 문제만 잘 이해하셨다면 구현 난이도는 더 낮습니다. https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문.. 2024. 4. 19. [C/C++] 백준 #2606 바이러스(너비 우선 탐색) 이번 문제는 깊이 우선 탐색(DFS)나 너비 우선 탐색(BFS)를 이용해서 첫번째 노드와 연결된 노드들의 갯수를 찾으면 됩니다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 그래프 탐색을 이용하기 위해서는 인접 행렬이나 인접 리스트를 구성해주어야 합니다. 가변 리스트를 생성할 수 있다면, 인접 리스트를 사용하는 것이 편합니다. 인접 행렬은 간선의 개수가 \(O(N^2)\)에 이르는 경우에 구성하면 좋습니다. 그 외에는 인접 리스트를 사용한다고 보.. 2024. 4. 19. [C/C++] 백준 #2591 숫자카드(동적계획법) 일반적으로 경우의 수를 판단할 때에는 많이 사용되는 알고리즘 기법이 동적계획법(Dynamic Programming)입니다. 이 문제는 1부터 34까지의 숫자 중 일부를 나열했을 때 나온 결과를 보고서 어떤 카드가 사용될 수 있는지 알아보는 방법입니다. 카드가 개수가 한정되어 있다면, 동적계획법을 사용할 때 보다 복잡하겠지만, 여기서는 카드의 개수가 한정되어 있지 않으니 계산하기가 편하죠. 단지 숫자 범위가 34라는 것만 문제가 될 뿐입니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2591 2591번: 숫자카드 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 .. 2024. 3. 22. [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. 이전 1 2 3 4 ··· 67 다음 728x90
