반응형 분류 전체보기509 [C/C++] 백준 #2608 로마 숫자(구현) 로마숫자 표기법은 아라비아 숫자 대신 제일 많이 사용되는 숫자 표현법이죠. 그래서 대략 100 미만의 숫자들은 표기할 줄 알지만, 그 이상 숫자들은 잘 모릅니다. 아라비아 숫자들은 숫자들의 위치에 따라서 숫자의 단위가 크게 달라지지만, 로마 숫자는 영문자에 따라서 단위가 정해져 있습니다. 하지만 여기에 빼기 개념도 있어서 IV = 5 - 1 = 4 와 같이 단위 문자의 위치에 따라서 빼기가 성립합니다. IIII 라고 표현하면, 문자길이가 4이지만 IV라고 표현하면 문자길이가 2이기 때문에 두번째 방식을 택합니다. IIV 와 같은 개념은 존재하지 않기 때문에 로마 숫자를 십진법으로 변환하기 위해서는 하나 앞이라는 개념만 이해하면 됩니다. VX와 같이 5단위 문자인 V가 10단위 문자인.. 2024. 4. 26. [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. 이전 1 2 3 4 ··· 85 다음 728x90
