백준 1992, 분할 정복 문제

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 해당 문제는 분할 정복 문제이다. 배열의 크기가 N X N일때, N은 2의 제곱수이기 때문에 2배 간격으로 범위를 지정할 수 있다. N의 최소 값은 1이므로 2차원 배열의 한 칸까지 분할될 수 있다. 필자는 int형을 반환하는 메서드를 작성하였는데, 해당 문제는 숫자 뿐만 아니라 괄호까지 출력해야 하기 때문에 string을 사용하는 것이 적합하다. Key Point 괄호가 묶이는 경우..

• format_list_bulleted 알고리즘
• · 2023. 8. 12.
• textsms

백준 16234, 연결된 요소를 탐색하는 완전탐색(DFS)

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 해당 문제는 모든 지점에 대해 DFS 탐색을 진행하고, 연결된 요소에 대해서 값을 재할당한 뒤 다시 visited 배열을 초기화하여 처음부터 다시 탐색을 하는 방법을 사용해야 한다. 따라서 무한루프 내에서 DFS가 진행되며, 특정 조건이 되었을 때 빠져나올 수 있는 Flag가 필요하다. 기존 방식대로 DFS를 진행하되, 방문처리 이외에 Sum을 갱신하고, Vector에 해당 위치를 ..

• format_list_bulleted 알고리즘
• · 2023. 8. 11.
• textsms

백준 2589, 모든 지점에 대한 최단거리를 구해야 하는 완전탐색(BFS)

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 해당 문제는 두 육지에 대한 최단거리가 가장 큰 두 지점을 보물 위치로 지정하고, 그 두 곳의 최단거리를 구하는 문제이다. 따라서 필자는 해당 문제를 풀기 위한 전략을 다음과 같이 정했다. DFS(재귀)를 통해 각 육지마다 최단거리를 구한 뒤, 최대 값으로 갱신한다. 갱신할 때마다, 해당 좌표 값을 저장한다. 구한 보물의 위치에 대해서 최단거리를 구하는 BFS 탐색을 진행한다. 필자는 처음에 보물의 ..

• format_list_bulleted 알고리즘
• · 2023. 8. 8.
• textsms

백준 15686, 2차원 좌표에 대한 조합을 활용한 완전탐색 문제

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해당 문제는 주어진 치킨 집 좌표 중에서 M개를 골라 도시의 치킨 거리를 구한 다음 최소값을 구해야 한다. 이전에 배웠던 그래프 탐색 문제와는 달리 많은 경우에 대해 탐색하고 계산해야 한다. 따라서 이는 완전탐색 문제로 분류할 수 있다. 먼저 완전탐색으로 풀 시 시간복잡도를 확인한다. 해당 문제에서 치킨 집의 최대 개수가 13개이므로 조합으로 나올 수 있는 최대 개수는 13C..

• format_list_bulleted 알고리즘
• · 2023. 8. 7.
• textsms

백준 1620, 두 개의 자료구조를 사용(+ 문자열을 숫자로 바꾸기)

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 해당 문제는 문자열을 입력받으면 숫자를 출력하고, 숫자를 입력받으면 문자를 출력하는 문제이다. 따라서 문자(String)와 숫자(Integer)가 매핑된 자료구조를 사용해야 한다. 만약, String을 Key로 갖고 Integer가 Value인 Map을 활용하면, 문자를 입력받았을 때 숫자를 출력할 수 있다. 하지만 Integer를 입력받았을 경우, 이 자료구조로 문자..

• format_list_bulleted 알고리즘
• · 2023. 7. 26.
• textsms

백준 1012, DFS 연결된 요소 찾기(+ 테스트 케이스 : 배열 초기화하기)

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해당 문제는 1로 연결된 연결 요소의 개수를 찾는 문제이다. 따라서 DFS 알고리즘을 통해 탐색한다. (물론 BFS도 가능하다. 필자는 DFS 재귀 로직을 통해 작성하는 것이 더 간편하다고 생각해서 DFS를 사용하였다.) Key Point 맵이 주어져 있다. -> 2차원 배열을 통해 맵을 구현하고, ny[] / nx[]를 사용한다. DFS 혹은 BFS를 통해 연결되어 있는 노드들을 방문처리 한다. 맵을 방문하..

• format_list_bulleted 알고리즘
• · 2023. 7. 26.
• textsms