전체 글 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (JAVA)

백준 4256번: 트리 (Java)

접근 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 전위 순회, 중위 순회가 주어진 트리를 후위 순회 방식으로 표시하는 문제였습니다. 전위 순회의 경우 트리에서 루트 노드를 가장 먼저 표시합니다. 이 점을 이용하여 다음과 같이 재귀적으로 문제를 해결할 수 있습니다. 전위 순회에서 가장 앞의 숫자를 꺼냅니다. 꺼내진 숫자를 중위 순회에서 찾습니다. 해당 인덱스를 기준으로 앞쪽은 왼쪽 자식 중위 순회, 뒤쪽은 오른쪽 자식 중위 순회입니..

2022. 8. 16. 22:10
코딩/백준 (JAVA)

백준 2632번: 피자판매 (Java)

접근 https://www.acmicpc.net/problem/2632 피자를 판매할 때 연속하는 피자의 조각들로 판매할 수 있습니다. 따라서 m 조각으로 나뉜 피자 A가 1번 조각부터 m번 조각까지 있다고 했을 때 다음과 같이 경우의 수를 확인할 수 있습니다. 1, 1~2, 1~3, 1~4, ... , 1~(m-1), 1~m, 2, 2~3, 2~4, 2~5, ... , 2~m, 2~1 3, 3~4, 3~5, 3~6, ... , 3~1, 3~2 ... m, m~1, m~2, m~3, ... , m~(m-2), m~(m-1) 총 m*m 경우의 수로 보이지만, 1~m, 2~1, 3~2, ... , m~(m-1) 은 모두 피자 전체를 나타내는 조각을 의미하여 중복이고, 추가적으로 피자를 선택하지 않는 0이 더..

2022. 8. 15. 16:11
코딩/백준 (JAVA)

백준 18428번: 감시 피하기 (Java)

접근 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 단순한 dfs 문제였습니다. X가 표시된 위치 중 3군데를 선택하여 장애물을 놓고, 선생님의 위치에서 4방향으로 탐색하여 학생을 만나는지를 체크해주기로 합니다. 추가적으로 시간을 아끼기 위해 모든 X 위치에 장애물을 놓지 않고, 장애물을 놓았을 때 적어도 선생님의 시야를 막는 위치를 장애물의 후보군으로 놓기로 하였습니다. 이 위치는 탐색 전에 선생님의 위치에서 네방향으로 뻗어나가면서..

2022. 8. 14. 17:33
코딩/백준 (JAVA)

백준 3109번: 빵집 (Java)

접근 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net dfs 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 시작점을 0, 0 부터 r - 1, 0 까지 위에서 부터 아래로 탐색하므로, 해당 위치에서 최대한 효율적인 순서대로 탐색하기 위해 오른쪽 위, 오른쪽 중앙, 오른쪽 아래 순으로 탐색하게 해주었습니다. 탐색을 진행하면서 파이프가 놓아진 위치는 파이프가 놓아졌기 때문에 다시 탐색할 필요가 없습니다. 그리고 탐색에 실패한 위치는 탐색이 완료되었는데도 불구하..

2022. 8. 13. 11:45
코딩/백준 (JAVA)

백준 17182번: 우주 탐사선 (Java)

접근 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 행성의 수가 작고, 이미 방문한 행성을 다시 방문할 수 있으므로 플로이드 와샬 알고리즘을 사용하기로 했습니다. 추가적으로 백트래킹 알고리즘과 dp를 이용하였고, 행성의 수가 작으므로 dp에 비트마스크를 추가적으로 이용하기로 합니다. 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 다익스트라와는 달리, 플로이드 와샬 알고리즘은 한번의 탐색으로 모든 노드 간 최단거리를 구할 수 있습..

2022. 8. 9. 22:39
코딩/백준 (JAVA)

백준 16967번: 배열 복원하기 (Java)

접근 https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 처음 문제를 보고서는 0, 0부터 H + X, W + Y 까지 모두 탐색 후 중간에 겹치는 부분을 다시 한번 탐색하면서 이미 구해진 숫자를 가지고 유추해야하나 생각했지만 조금 더 생각해보니 그냥 0, 0 부터 H, W 까지 한번만 탐색해도 전체 배열의 모습을 구할 수 있었습니다. 다음과 같이 배열 A를 세부분으로 나누어 문제를 해결할 수 있습니다. r ..

2022. 8. 7. 17:13
반응형